1 /* Predictive commoning.
2 Copyright (C) 2005-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file implements the predictive commoning optimization. Predictive
21 commoning can be viewed as CSE around a loop, and with some improvements,
22 as generalized strength reduction-- i.e., reusing values computed in
23 earlier iterations of a loop in the later ones. So far, the pass only
24 handles the most useful case, that is, reusing values of memory references.
25 If you think this is all just a special case of PRE, you are sort of right;
26 however, concentrating on loops is simpler, and makes it possible to
27 incorporate data dependence analysis to detect the opportunities, perform
28 loop unrolling to avoid copies together with renaming immediately,
29 and if needed, we could also take register pressure into account.
31 Let us demonstrate what is done on an example:
33 for (i = 0; i < 100; i++)
35 a[i+2] = a[i] + a[i+1];
41 1) We find data references in the loop, and split them to mutually
42 independent groups (i.e., we find components of a data dependence
43 graph). We ignore read-read dependences whose distance is not constant.
44 (TODO -- we could also ignore antidependences). In this example, we
45 find the following groups:
47 a[i]{read}, a[i+1]{read}, a[i+2]{write}
48 b[10]{read}, b[10]{write}
49 c[99 - i]{read}, c[i]{write}
50 d[i + 1]{read}, d[i]{write}
52 2) Inside each of the group, we verify several conditions:
53 a) all the references must differ in indices only, and the indices
54 must all have the same step
55 b) the references must dominate loop latch (and thus, they must be
56 ordered by dominance relation).
57 c) the distance of the indices must be a small multiple of the step
58 We are then able to compute the difference of the references (# of
59 iterations before they point to the same place as the first of them).
60 Also, in case there are writes in the loop, we split the groups into
61 chains whose head is the write whose values are used by the reads in
62 the same chain. The chains are then processed independently,
63 making the further transformations simpler. Also, the shorter chains
64 need the same number of registers, but may require lower unrolling
65 factor in order to get rid of the copies on the loop latch.
67 In our example, we get the following chains (the chain for c is invalid).
69 a[i]{read,+0}, a[i+1]{read,-1}, a[i+2]{write,-2}
70 b[10]{read,+0}, b[10]{write,+0}
71 d[i + 1]{read,+0}, d[i]{write,+1}
73 3) For each read, we determine the read or write whose value it reuses,
74 together with the distance of this reuse. I.e. we take the last
75 reference before it with distance 0, or the last of the references
76 with the smallest positive distance to the read. Then, we remove
77 the references that are not used in any of these chains, discard the
78 empty groups, and propagate all the links so that they point to the
79 single root reference of the chain (adjusting their distance
80 appropriately). Some extra care needs to be taken for references with
81 step 0. In our example (the numbers indicate the distance of the
84 a[i] --> (*) 2, a[i+1] --> (*) 1, a[i+2] (*)
85 b[10] --> (*) 1, b[10] (*)
87 4) The chains are combined together if possible. If the corresponding
88 elements of two chains are always combined together with the same
89 operator, we remember just the result of this combination, instead
90 of remembering the values separately. We may need to perform
91 reassociation to enable combining, for example
93 e[i] + f[i+1] + e[i+1] + f[i]
95 can be reassociated as
97 (e[i] + f[i]) + (e[i+1] + f[i+1])
99 and we can combine the chains for e and f into one chain.
101 5) For each root reference (end of the chain) R, let N be maximum distance
102 of a reference reusing its value. Variables R0 up to RN are created,
103 together with phi nodes that transfer values from R1 .. RN to
105 Initial values are loaded to R0..R(N-1) (in case not all references
106 must necessarily be accessed and they may trap, we may fail here;
107 TODO sometimes, the loads could be guarded by a check for the number
108 of iterations). Values loaded/stored in roots are also copied to
109 RN. Other reads are replaced with the appropriate variable Ri.
110 Everything is put to SSA form.
112 As a small improvement, if R0 is dead after the root (i.e., all uses of
113 the value with the maximum distance dominate the root), we can avoid
114 creating RN and use R0 instead of it.
116 In our example, we get (only the parts concerning a and b are shown):
117 for (i = 0; i < 100; i++)
129 6) Factor F for unrolling is determined as the smallest common multiple of
130 (N + 1) for each root reference (N for references for that we avoided
131 creating RN). If F and the loop is small enough, loop is unrolled F
132 times. The stores to RN (R0) in the copies of the loop body are
133 periodically replaced with R0, R1, ... (R1, R2, ...), so that they can
134 be coalesced and the copies can be eliminated.
136 TODO -- copy propagation and other optimizations may change the live
137 ranges of the temporary registers and prevent them from being coalesced;
138 this may increase the register pressure.
140 In our case, F = 2 and the (main loop of the) result is
142 for (i = 0; i < ...; i += 2)
159 TODO -- stores killing other stores can be taken into account, e.g.,
160 for (i = 0; i < n; i++)
170 for (i = 0; i < n; i++)
180 The interesting part is that this would generalize store motion; still, since
181 sm is performed elsewhere, it does not seem that important.
183 Predictive commoning can be generalized for arbitrary computations (not
184 just memory loads), and also nontrivial transfer functions (e.g., replacing
185 i * i with ii_last + 2 * i + 1), to generalize strength reduction. */
189 #include "coretypes.h"
194 #include "tree-flow.h"
196 #include "tree-data-ref.h"
197 #include "tree-scalar-evolution.h"
198 #include "tree-chrec.h"
200 #include "gimple-pretty-print.h"
201 #include "tree-pass.h"
202 #include "tree-affine.h"
203 #include "tree-inline.h"
205 /* The maximum number of iterations between the considered memory
208 #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
210 /* Data references (or phi nodes that carry data reference values across
213 typedef struct dref_d
215 /* The reference itself. */
216 struct data_reference
*ref
;
218 /* The statement in that the reference appears. */
221 /* In case that STMT is a phi node, this field is set to the SSA name
222 defined by it in replace_phis_by_defined_names (in order to avoid
223 pointing to phi node that got reallocated in the meantime). */
224 tree name_defined_by_phi
;
226 /* Distance of the reference from the root of the chain (in number of
227 iterations of the loop). */
230 /* Number of iterations offset from the first reference in the component. */
233 /* Number of the reference in a component, in dominance ordering. */
236 /* True if the memory reference is always accessed when the loop is
238 unsigned always_accessed
: 1;
242 /* Type of the chain of the references. */
246 /* The addresses of the references in the chain are constant. */
249 /* There are only loads in the chain. */
252 /* Root of the chain is store, the rest are loads. */
255 /* A combination of two chains. */
259 /* Chains of data references. */
263 /* Type of the chain. */
264 enum chain_type type
;
266 /* For combination chains, the operator and the two chains that are
267 combined, and the type of the result. */
270 struct chain
*ch1
, *ch2
;
272 /* The references in the chain. */
275 /* The maximum distance of the reference in the chain from the root. */
278 /* The variables used to copy the value throughout iterations. */
281 /* Initializers for the variables. */
284 /* True if there is a use of a variable with the maximal distance
285 that comes after the root in the loop. */
286 unsigned has_max_use_after
: 1;
288 /* True if all the memory references in the chain are always accessed. */
289 unsigned all_always_accessed
: 1;
291 /* True if this chain was combined together with some other chain. */
292 unsigned combined
: 1;
296 /* Describes the knowledge about the step of the memory references in
301 /* The step is zero. */
304 /* The step is nonzero. */
307 /* The step may or may not be nonzero. */
311 /* Components of the data dependence graph. */
315 /* The references in the component. */
318 /* What we know about the step of the references in the component. */
319 enum ref_step_type comp_step
;
321 /* Next component in the list. */
322 struct component
*next
;
325 /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */
327 static bitmap looparound_phis
;
329 /* Cache used by tree_to_aff_combination_expand. */
331 static struct pointer_map_t
*name_expansions
;
333 /* Dumps data reference REF to FILE. */
335 extern void dump_dref (FILE *, dref
);
337 dump_dref (FILE *file
, dref ref
)
342 print_generic_expr (file
, DR_REF (ref
->ref
), TDF_SLIM
);
343 fprintf (file
, " (id %u%s)\n", ref
->pos
,
344 DR_IS_READ (ref
->ref
) ? "" : ", write");
346 fprintf (file
, " offset ");
347 dump_double_int (file
, ref
->offset
, false);
348 fprintf (file
, "\n");
350 fprintf (file
, " distance %u\n", ref
->distance
);
354 if (gimple_code (ref
->stmt
) == GIMPLE_PHI
)
355 fprintf (file
, " looparound ref\n");
357 fprintf (file
, " combination ref\n");
358 fprintf (file
, " in statement ");
359 print_gimple_stmt (file
, ref
->stmt
, 0, TDF_SLIM
);
360 fprintf (file
, "\n");
361 fprintf (file
, " distance %u\n", ref
->distance
);
366 /* Dumps CHAIN to FILE. */
368 extern void dump_chain (FILE *, chain_p
);
370 dump_chain (FILE *file
, chain_p chain
)
373 const char *chain_type
;
380 chain_type
= "Load motion";
384 chain_type
= "Loads-only";
388 chain_type
= "Store-loads";
392 chain_type
= "Combination";
399 fprintf (file
, "%s chain %p%s\n", chain_type
, (void *) chain
,
400 chain
->combined
? " (combined)" : "");
401 if (chain
->type
!= CT_INVARIANT
)
402 fprintf (file
, " max distance %u%s\n", chain
->length
,
403 chain
->has_max_use_after
? "" : ", may reuse first");
405 if (chain
->type
== CT_COMBINATION
)
407 fprintf (file
, " equal to %p %s %p in type ",
408 (void *) chain
->ch1
, op_symbol_code (chain
->op
),
409 (void *) chain
->ch2
);
410 print_generic_expr (file
, chain
->rslt_type
, TDF_SLIM
);
411 fprintf (file
, "\n");
414 if (chain
->vars
.exists ())
416 fprintf (file
, " vars");
417 FOR_EACH_VEC_ELT (chain
->vars
, i
, var
)
420 print_generic_expr (file
, var
, TDF_SLIM
);
422 fprintf (file
, "\n");
425 if (chain
->inits
.exists ())
427 fprintf (file
, " inits");
428 FOR_EACH_VEC_ELT (chain
->inits
, i
, var
)
431 print_generic_expr (file
, var
, TDF_SLIM
);
433 fprintf (file
, "\n");
436 fprintf (file
, " references:\n");
437 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
440 fprintf (file
, "\n");
443 /* Dumps CHAINS to FILE. */
445 extern void dump_chains (FILE *, vec
<chain_p
> );
447 dump_chains (FILE *file
, vec
<chain_p
> chains
)
452 FOR_EACH_VEC_ELT (chains
, i
, chain
)
453 dump_chain (file
, chain
);
456 /* Dumps COMP to FILE. */
458 extern void dump_component (FILE *, struct component
*);
460 dump_component (FILE *file
, struct component
*comp
)
465 fprintf (file
, "Component%s:\n",
466 comp
->comp_step
== RS_INVARIANT
? " (invariant)" : "");
467 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
469 fprintf (file
, "\n");
472 /* Dumps COMPS to FILE. */
474 extern void dump_components (FILE *, struct component
*);
476 dump_components (FILE *file
, struct component
*comps
)
478 struct component
*comp
;
480 for (comp
= comps
; comp
; comp
= comp
->next
)
481 dump_component (file
, comp
);
484 /* Frees a chain CHAIN. */
487 release_chain (chain_p chain
)
495 FOR_EACH_VEC_ELT (chain
->refs
, i
, ref
)
498 chain
->refs
.release ();
499 chain
->vars
.release ();
500 chain
->inits
.release ();
508 release_chains (vec
<chain_p
> chains
)
513 FOR_EACH_VEC_ELT (chains
, i
, chain
)
514 release_chain (chain
);
518 /* Frees a component COMP. */
521 release_component (struct component
*comp
)
523 comp
->refs
.release ();
527 /* Frees list of components COMPS. */
530 release_components (struct component
*comps
)
532 struct component
*act
, *next
;
534 for (act
= comps
; act
; act
= next
)
537 release_component (act
);
541 /* Finds a root of tree given by FATHERS containing A, and performs path
545 component_of (unsigned fathers
[], unsigned a
)
549 for (root
= a
; root
!= fathers
[root
]; root
= fathers
[root
])
552 for (; a
!= root
; a
= n
)
561 /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the
562 components, A and B are components to merge. */
565 merge_comps (unsigned fathers
[], unsigned sizes
[], unsigned a
, unsigned b
)
567 unsigned ca
= component_of (fathers
, a
);
568 unsigned cb
= component_of (fathers
, b
);
573 if (sizes
[ca
] < sizes
[cb
])
575 sizes
[cb
] += sizes
[ca
];
580 sizes
[ca
] += sizes
[cb
];
585 /* Returns true if A is a reference that is suitable for predictive commoning
586 in the innermost loop that contains it. REF_STEP is set according to the
587 step of the reference A. */
590 suitable_reference_p (struct data_reference
*a
, enum ref_step_type
*ref_step
)
592 tree ref
= DR_REF (a
), step
= DR_STEP (a
);
595 || TREE_THIS_VOLATILE (ref
)
596 || !is_gimple_reg_type (TREE_TYPE (ref
))
597 || tree_could_throw_p (ref
))
600 if (integer_zerop (step
))
601 *ref_step
= RS_INVARIANT
;
602 else if (integer_nonzerop (step
))
603 *ref_step
= RS_NONZERO
;
610 /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
613 aff_combination_dr_offset (struct data_reference
*dr
, aff_tree
*offset
)
615 tree type
= TREE_TYPE (DR_OFFSET (dr
));
618 tree_to_aff_combination_expand (DR_OFFSET (dr
), type
, offset
,
620 aff_combination_const (&delta
, type
, tree_to_double_int (DR_INIT (dr
)));
621 aff_combination_add (offset
, &delta
);
624 /* Determines number of iterations of the innermost enclosing loop before B
625 refers to exactly the same location as A and stores it to OFF. If A and
626 B do not have the same step, they never meet, or anything else fails,
627 returns false, otherwise returns true. Both A and B are assumed to
628 satisfy suitable_reference_p. */
631 determine_offset (struct data_reference
*a
, struct data_reference
*b
,
634 aff_tree diff
, baseb
, step
;
637 /* Check that both the references access the location in the same type. */
638 typea
= TREE_TYPE (DR_REF (a
));
639 typeb
= TREE_TYPE (DR_REF (b
));
640 if (!useless_type_conversion_p (typeb
, typea
))
643 /* Check whether the base address and the step of both references is the
645 if (!operand_equal_p (DR_STEP (a
), DR_STEP (b
), 0)
646 || !operand_equal_p (DR_BASE_ADDRESS (a
), DR_BASE_ADDRESS (b
), 0))
649 if (integer_zerop (DR_STEP (a
)))
651 /* If the references have loop invariant address, check that they access
652 exactly the same location. */
653 *off
= double_int_zero
;
654 return (operand_equal_p (DR_OFFSET (a
), DR_OFFSET (b
), 0)
655 && operand_equal_p (DR_INIT (a
), DR_INIT (b
), 0));
658 /* Compare the offsets of the addresses, and check whether the difference
659 is a multiple of step. */
660 aff_combination_dr_offset (a
, &diff
);
661 aff_combination_dr_offset (b
, &baseb
);
662 aff_combination_scale (&baseb
, double_int_minus_one
);
663 aff_combination_add (&diff
, &baseb
);
665 tree_to_aff_combination_expand (DR_STEP (a
), TREE_TYPE (DR_STEP (a
)),
666 &step
, &name_expansions
);
667 return aff_combination_constant_multiple_p (&diff
, &step
, off
);
670 /* Returns the last basic block in LOOP for that we are sure that
671 it is executed whenever the loop is entered. */
674 last_always_executed_block (struct loop
*loop
)
677 vec
<edge
> exits
= get_loop_exit_edges (loop
);
679 basic_block last
= loop
->latch
;
681 FOR_EACH_VEC_ELT (exits
, i
, ex
)
682 last
= nearest_common_dominator (CDI_DOMINATORS
, last
, ex
->src
);
688 /* Splits dependence graph on DATAREFS described by DEPENDS to components. */
690 static struct component
*
691 split_data_refs_to_components (struct loop
*loop
,
692 vec
<data_reference_p
> datarefs
,
695 unsigned i
, n
= datarefs
.length ();
696 unsigned ca
, ia
, ib
, bad
;
697 unsigned *comp_father
= XNEWVEC (unsigned, n
+ 1);
698 unsigned *comp_size
= XNEWVEC (unsigned, n
+ 1);
699 struct component
**comps
;
700 struct data_reference
*dr
, *dra
, *drb
;
701 struct data_dependence_relation
*ddr
;
702 struct component
*comp_list
= NULL
, *comp
;
704 basic_block last_always_executed
= last_always_executed_block (loop
);
706 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
710 /* A fake reference for call or asm_expr that may clobber memory;
714 dr
->aux
= (void *) (size_t) i
;
719 /* A component reserved for the "bad" data references. */
723 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
725 enum ref_step_type dummy
;
727 if (!suitable_reference_p (dr
, &dummy
))
729 ia
= (unsigned) (size_t) dr
->aux
;
730 merge_comps (comp_father
, comp_size
, n
, ia
);
734 FOR_EACH_VEC_ELT (depends
, i
, ddr
)
736 double_int dummy_off
;
738 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
743 ia
= component_of (comp_father
, (unsigned) (size_t) dra
->aux
);
744 ib
= component_of (comp_father
, (unsigned) (size_t) drb
->aux
);
748 bad
= component_of (comp_father
, n
);
750 /* If both A and B are reads, we may ignore unsuitable dependences. */
751 if (DR_IS_READ (dra
) && DR_IS_READ (drb
)
752 && (ia
== bad
|| ib
== bad
753 || !determine_offset (dra
, drb
, &dummy_off
)))
756 merge_comps (comp_father
, comp_size
, ia
, ib
);
759 comps
= XCNEWVEC (struct component
*, n
);
760 bad
= component_of (comp_father
, n
);
761 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
763 ia
= (unsigned) (size_t) dr
->aux
;
764 ca
= component_of (comp_father
, ia
);
771 comp
= XCNEW (struct component
);
772 comp
->refs
.create (comp_size
[ca
]);
776 dataref
= XCNEW (struct dref_d
);
778 dataref
->stmt
= DR_STMT (dr
);
779 dataref
->offset
= double_int_zero
;
780 dataref
->distance
= 0;
782 dataref
->always_accessed
783 = dominated_by_p (CDI_DOMINATORS
, last_always_executed
,
784 gimple_bb (dataref
->stmt
));
785 dataref
->pos
= comp
->refs
.length ();
786 comp
->refs
.quick_push (dataref
);
789 for (i
= 0; i
< n
; i
++)
794 comp
->next
= comp_list
;
806 /* Returns true if the component COMP satisfies the conditions
807 described in 2) at the beginning of this file. LOOP is the current
811 suitable_component_p (struct loop
*loop
, struct component
*comp
)
815 basic_block ba
, bp
= loop
->header
;
816 bool ok
, has_write
= false;
818 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
820 ba
= gimple_bb (a
->stmt
);
822 if (!just_once_each_iteration_p (loop
, ba
))
825 gcc_assert (dominated_by_p (CDI_DOMINATORS
, ba
, bp
));
828 if (DR_IS_WRITE (a
->ref
))
832 first
= comp
->refs
[0];
833 ok
= suitable_reference_p (first
->ref
, &comp
->comp_step
);
835 first
->offset
= double_int_zero
;
837 for (i
= 1; comp
->refs
.iterate (i
, &a
); i
++)
839 if (!determine_offset (first
->ref
, a
->ref
, &a
->offset
))
842 #ifdef ENABLE_CHECKING
844 enum ref_step_type a_step
;
845 ok
= suitable_reference_p (a
->ref
, &a_step
);
846 gcc_assert (ok
&& a_step
== comp
->comp_step
);
851 /* If there is a write inside the component, we must know whether the
852 step is nonzero or not -- we would not otherwise be able to recognize
853 whether the value accessed by reads comes from the OFFSET-th iteration
854 or the previous one. */
855 if (has_write
&& comp
->comp_step
== RS_ANY
)
861 /* Check the conditions on references inside each of components COMPS,
862 and remove the unsuitable components from the list. The new list
863 of components is returned. The conditions are described in 2) at
864 the beginning of this file. LOOP is the current loop. */
866 static struct component
*
867 filter_suitable_components (struct loop
*loop
, struct component
*comps
)
869 struct component
**comp
, *act
;
871 for (comp
= &comps
; *comp
; )
874 if (suitable_component_p (loop
, act
))
882 FOR_EACH_VEC_ELT (act
->refs
, i
, ref
)
884 release_component (act
);
891 /* Compares two drefs A and B by their offset and position. Callback for
895 order_drefs (const void *a
, const void *b
)
897 const dref
*const da
= (const dref
*) a
;
898 const dref
*const db
= (const dref
*) b
;
899 int offcmp
= (*da
)->offset
.scmp ((*db
)->offset
);
904 return (*da
)->pos
- (*db
)->pos
;
907 /* Returns root of the CHAIN. */
910 get_chain_root (chain_p chain
)
912 return chain
->refs
[0];
915 /* Adds REF to the chain CHAIN. */
918 add_ref_to_chain (chain_p chain
, dref ref
)
920 dref root
= get_chain_root (chain
);
923 gcc_assert (root
->offset
.sle (ref
->offset
));
924 dist
= ref
->offset
- root
->offset
;
925 if (double_int::from_uhwi (MAX_DISTANCE
).ule (dist
))
930 gcc_assert (dist
.fits_uhwi ());
932 chain
->refs
.safe_push (ref
);
934 ref
->distance
= dist
.to_uhwi ();
936 if (ref
->distance
>= chain
->length
)
938 chain
->length
= ref
->distance
;
939 chain
->has_max_use_after
= false;
942 if (ref
->distance
== chain
->length
943 && ref
->pos
> root
->pos
)
944 chain
->has_max_use_after
= true;
946 chain
->all_always_accessed
&= ref
->always_accessed
;
949 /* Returns the chain for invariant component COMP. */
952 make_invariant_chain (struct component
*comp
)
954 chain_p chain
= XCNEW (struct chain
);
958 chain
->type
= CT_INVARIANT
;
960 chain
->all_always_accessed
= true;
962 FOR_EACH_VEC_ELT (comp
->refs
, i
, ref
)
964 chain
->refs
.safe_push (ref
);
965 chain
->all_always_accessed
&= ref
->always_accessed
;
971 /* Make a new chain rooted at REF. */
974 make_rooted_chain (dref ref
)
976 chain_p chain
= XCNEW (struct chain
);
978 chain
->type
= DR_IS_READ (ref
->ref
) ? CT_LOAD
: CT_STORE_LOAD
;
980 chain
->refs
.safe_push (ref
);
981 chain
->all_always_accessed
= ref
->always_accessed
;
988 /* Returns true if CHAIN is not trivial. */
991 nontrivial_chain_p (chain_p chain
)
993 return chain
!= NULL
&& chain
->refs
.length () > 1;
996 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1000 name_for_ref (dref ref
)
1004 if (is_gimple_assign (ref
->stmt
))
1006 if (!ref
->ref
|| DR_IS_READ (ref
->ref
))
1007 name
= gimple_assign_lhs (ref
->stmt
);
1009 name
= gimple_assign_rhs1 (ref
->stmt
);
1012 name
= PHI_RESULT (ref
->stmt
);
1014 return (TREE_CODE (name
) == SSA_NAME
? name
: NULL_TREE
);
1017 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1018 iterations of the innermost enclosing loop). */
1021 valid_initializer_p (struct data_reference
*ref
,
1022 unsigned distance
, struct data_reference
*root
)
1024 aff_tree diff
, base
, step
;
1027 /* Both REF and ROOT must be accessing the same object. */
1028 if (!operand_equal_p (DR_BASE_ADDRESS (ref
), DR_BASE_ADDRESS (root
), 0))
1031 /* The initializer is defined outside of loop, hence its address must be
1032 invariant inside the loop. */
1033 gcc_assert (integer_zerop (DR_STEP (ref
)));
1035 /* If the address of the reference is invariant, initializer must access
1036 exactly the same location. */
1037 if (integer_zerop (DR_STEP (root
)))
1038 return (operand_equal_p (DR_OFFSET (ref
), DR_OFFSET (root
), 0)
1039 && operand_equal_p (DR_INIT (ref
), DR_INIT (root
), 0));
1041 /* Verify that this index of REF is equal to the root's index at
1042 -DISTANCE-th iteration. */
1043 aff_combination_dr_offset (root
, &diff
);
1044 aff_combination_dr_offset (ref
, &base
);
1045 aff_combination_scale (&base
, double_int_minus_one
);
1046 aff_combination_add (&diff
, &base
);
1048 tree_to_aff_combination_expand (DR_STEP (root
), TREE_TYPE (DR_STEP (root
)),
1049 &step
, &name_expansions
);
1050 if (!aff_combination_constant_multiple_p (&diff
, &step
, &off
))
1053 if (off
!= double_int::from_uhwi (distance
))
1059 /* Finds looparound phi node of LOOP that copies the value of REF, and if its
1060 initial value is correct (equal to initial value of REF shifted by one
1061 iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT
1062 is the root of the current chain. */
1065 find_looparound_phi (struct loop
*loop
, dref ref
, dref root
)
1067 tree name
, init
, init_ref
;
1068 gimple phi
= NULL
, init_stmt
;
1069 edge latch
= loop_latch_edge (loop
);
1070 struct data_reference init_dr
;
1071 gimple_stmt_iterator psi
;
1073 if (is_gimple_assign (ref
->stmt
))
1075 if (DR_IS_READ (ref
->ref
))
1076 name
= gimple_assign_lhs (ref
->stmt
);
1078 name
= gimple_assign_rhs1 (ref
->stmt
);
1081 name
= PHI_RESULT (ref
->stmt
);
1085 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1087 phi
= gsi_stmt (psi
);
1088 if (PHI_ARG_DEF_FROM_EDGE (phi
, latch
) == name
)
1092 if (gsi_end_p (psi
))
1095 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1096 if (TREE_CODE (init
) != SSA_NAME
)
1098 init_stmt
= SSA_NAME_DEF_STMT (init
);
1099 if (gimple_code (init_stmt
) != GIMPLE_ASSIGN
)
1101 gcc_assert (gimple_assign_lhs (init_stmt
) == init
);
1103 init_ref
= gimple_assign_rhs1 (init_stmt
);
1104 if (!REFERENCE_CLASS_P (init_ref
)
1105 && !DECL_P (init_ref
))
1108 /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1109 loop enclosing PHI). */
1110 memset (&init_dr
, 0, sizeof (struct data_reference
));
1111 DR_REF (&init_dr
) = init_ref
;
1112 DR_STMT (&init_dr
) = phi
;
1113 if (!dr_analyze_innermost (&init_dr
, loop
))
1116 if (!valid_initializer_p (&init_dr
, ref
->distance
+ 1, root
->ref
))
1122 /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1125 insert_looparound_copy (chain_p chain
, dref ref
, gimple phi
)
1127 dref nw
= XCNEW (struct dref_d
), aref
;
1131 nw
->distance
= ref
->distance
+ 1;
1132 nw
->always_accessed
= 1;
1134 FOR_EACH_VEC_ELT (chain
->refs
, i
, aref
)
1135 if (aref
->distance
>= nw
->distance
)
1137 chain
->refs
.safe_insert (i
, nw
);
1139 if (nw
->distance
> chain
->length
)
1141 chain
->length
= nw
->distance
;
1142 chain
->has_max_use_after
= false;
1146 /* For references in CHAIN that are copied around the LOOP (created previously
1147 by PRE, or by user), add the results of such copies to the chain. This
1148 enables us to remove the copies by unrolling, and may need less registers
1149 (also, it may allow us to combine chains together). */
1152 add_looparound_copies (struct loop
*loop
, chain_p chain
)
1155 dref ref
, root
= get_chain_root (chain
);
1158 FOR_EACH_VEC_ELT (chain
->refs
, i
, ref
)
1160 phi
= find_looparound_phi (loop
, ref
, root
);
1164 bitmap_set_bit (looparound_phis
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
1165 insert_looparound_copy (chain
, ref
, phi
);
1169 /* Find roots of the values and determine distances in the component COMP.
1170 The references are redistributed into CHAINS. LOOP is the current
1174 determine_roots_comp (struct loop
*loop
,
1175 struct component
*comp
,
1176 vec
<chain_p
> *chains
)
1180 chain_p chain
= NULL
;
1181 double_int last_ofs
= double_int_zero
;
1183 /* Invariants are handled specially. */
1184 if (comp
->comp_step
== RS_INVARIANT
)
1186 chain
= make_invariant_chain (comp
);
1187 chains
->safe_push (chain
);
1191 comp
->refs
.qsort (order_drefs
);
1193 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
1195 if (!chain
|| DR_IS_WRITE (a
->ref
)
1196 || double_int::from_uhwi (MAX_DISTANCE
).ule (a
->offset
- last_ofs
))
1198 if (nontrivial_chain_p (chain
))
1200 add_looparound_copies (loop
, chain
);
1201 chains
->safe_push (chain
);
1204 release_chain (chain
);
1205 chain
= make_rooted_chain (a
);
1206 last_ofs
= a
->offset
;
1210 add_ref_to_chain (chain
, a
);
1213 if (nontrivial_chain_p (chain
))
1215 add_looparound_copies (loop
, chain
);
1216 chains
->safe_push (chain
);
1219 release_chain (chain
);
1222 /* Find roots of the values and determine distances in components COMPS, and
1223 separates the references to CHAINS. LOOP is the current loop. */
1226 determine_roots (struct loop
*loop
,
1227 struct component
*comps
, vec
<chain_p
> *chains
)
1229 struct component
*comp
;
1231 for (comp
= comps
; comp
; comp
= comp
->next
)
1232 determine_roots_comp (loop
, comp
, chains
);
1235 /* Replace the reference in statement STMT with temporary variable
1236 NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of
1237 the reference in the statement. IN_LHS is true if the reference
1238 is in the lhs of STMT, false if it is in rhs. */
1241 replace_ref_with (gimple stmt
, tree new_tree
, bool set
, bool in_lhs
)
1245 gimple_stmt_iterator bsi
, psi
;
1247 if (gimple_code (stmt
) == GIMPLE_PHI
)
1249 gcc_assert (!in_lhs
&& !set
);
1251 val
= PHI_RESULT (stmt
);
1252 bsi
= gsi_after_labels (gimple_bb (stmt
));
1253 psi
= gsi_for_stmt (stmt
);
1254 remove_phi_node (&psi
, false);
1256 /* Turn the phi node into GIMPLE_ASSIGN. */
1257 new_stmt
= gimple_build_assign (val
, new_tree
);
1258 gsi_insert_before (&bsi
, new_stmt
, GSI_NEW_STMT
);
1262 /* Since the reference is of gimple_reg type, it should only
1263 appear as lhs or rhs of modify statement. */
1264 gcc_assert (is_gimple_assign (stmt
));
1266 bsi
= gsi_for_stmt (stmt
);
1268 /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */
1271 gcc_assert (!in_lhs
);
1272 gimple_assign_set_rhs_from_tree (&bsi
, new_tree
);
1273 stmt
= gsi_stmt (bsi
);
1280 /* We have statement
1284 If OLD is a memory reference, then VAL is gimple_val, and we transform
1290 Otherwise, we are replacing a combination chain,
1291 VAL is the expression that performs the combination, and OLD is an
1292 SSA name. In this case, we transform the assignment to
1299 val
= gimple_assign_lhs (stmt
);
1300 if (TREE_CODE (val
) != SSA_NAME
)
1302 val
= gimple_assign_rhs1 (stmt
);
1303 gcc_assert (gimple_assign_single_p (stmt
));
1304 if (TREE_CLOBBER_P (val
))
1305 val
= get_or_create_ssa_default_def (cfun
, SSA_NAME_VAR (new_tree
));
1307 gcc_assert (gimple_assign_copy_p (stmt
));
1319 val
= gimple_assign_lhs (stmt
);
1322 new_stmt
= gimple_build_assign (new_tree
, unshare_expr (val
));
1323 gsi_insert_after (&bsi
, new_stmt
, GSI_NEW_STMT
);
1326 /* Returns a memory reference to DR in the ITER-th iteration of
1327 the loop it was analyzed in. Append init stmts to STMTS. */
1330 ref_at_iteration (data_reference_p dr
, int iter
, gimple_seq
*stmts
)
1332 tree off
= DR_OFFSET (dr
);
1333 tree coff
= DR_INIT (dr
);
1336 else if (TREE_CODE (DR_STEP (dr
)) == INTEGER_CST
)
1337 coff
= size_binop (PLUS_EXPR
, coff
,
1338 size_binop (MULT_EXPR
, DR_STEP (dr
), ssize_int (iter
)));
1340 off
= size_binop (PLUS_EXPR
, off
,
1341 size_binop (MULT_EXPR
, DR_STEP (dr
), ssize_int (iter
)));
1342 tree addr
= fold_build_pointer_plus (DR_BASE_ADDRESS (dr
), off
);
1343 addr
= force_gimple_operand_1 (addr
, stmts
, is_gimple_mem_ref_addr
,
1345 tree alias_ptr
= fold_convert (reference_alias_ptr_type (DR_REF (dr
)), coff
);
1346 /* While data-ref analysis punts on bit offsets it still handles
1347 bitfield accesses at byte boundaries. Cope with that. Note that
1348 we cannot simply re-apply the outer COMPONENT_REF because the
1349 byte-granular portion of it is already applied via DR_INIT and
1350 DR_OFFSET, so simply build a BIT_FIELD_REF knowing that the bits
1351 start at offset zero. */
1352 if (TREE_CODE (DR_REF (dr
)) == COMPONENT_REF
1353 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr
), 1)))
1355 tree field
= TREE_OPERAND (DR_REF (dr
), 1);
1356 return build3 (BIT_FIELD_REF
, TREE_TYPE (DR_REF (dr
)),
1357 build2 (MEM_REF
, DECL_BIT_FIELD_TYPE (field
),
1359 DECL_SIZE (field
), bitsize_zero_node
);
1362 return fold_build2 (MEM_REF
, TREE_TYPE (DR_REF (dr
)), addr
, alias_ptr
);
1365 /* Get the initialization expression for the INDEX-th temporary variable
1369 get_init_expr (chain_p chain
, unsigned index
)
1371 if (chain
->type
== CT_COMBINATION
)
1373 tree e1
= get_init_expr (chain
->ch1
, index
);
1374 tree e2
= get_init_expr (chain
->ch2
, index
);
1376 return fold_build2 (chain
->op
, chain
->rslt_type
, e1
, e2
);
1379 return chain
->inits
[index
];
1382 /* Returns a new temporary variable used for the I-th variable carrying
1383 value of REF. The variable's uid is marked in TMP_VARS. */
1386 predcom_tmp_var (tree ref
, unsigned i
, bitmap tmp_vars
)
1388 tree type
= TREE_TYPE (ref
);
1389 /* We never access the components of the temporary variable in predictive
1391 tree var
= create_tmp_reg (type
, get_lsm_tmp_name (ref
, i
));
1392 bitmap_set_bit (tmp_vars
, DECL_UID (var
));
1396 /* Creates the variables for CHAIN, as well as phi nodes for them and
1397 initialization on entry to LOOP. Uids of the newly created
1398 temporary variables are marked in TMP_VARS. */
1401 initialize_root_vars (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1404 unsigned n
= chain
->length
;
1405 dref root
= get_chain_root (chain
);
1406 bool reuse_first
= !chain
->has_max_use_after
;
1407 tree ref
, init
, var
, next
;
1410 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1412 /* If N == 0, then all the references are within the single iteration. And
1413 since this is an nonempty chain, reuse_first cannot be true. */
1414 gcc_assert (n
> 0 || !reuse_first
);
1416 chain
->vars
.create (n
+ 1);
1418 if (chain
->type
== CT_COMBINATION
)
1419 ref
= gimple_assign_lhs (root
->stmt
);
1421 ref
= DR_REF (root
->ref
);
1423 for (i
= 0; i
< n
+ (reuse_first
? 0 : 1); i
++)
1425 var
= predcom_tmp_var (ref
, i
, tmp_vars
);
1426 chain
->vars
.quick_push (var
);
1429 chain
->vars
.quick_push (chain
->vars
[0]);
1431 FOR_EACH_VEC_ELT (chain
->vars
, i
, var
)
1432 chain
->vars
[i
] = make_ssa_name (var
, NULL
);
1434 for (i
= 0; i
< n
; i
++)
1436 var
= chain
->vars
[i
];
1437 next
= chain
->vars
[i
+ 1];
1438 init
= get_init_expr (chain
, i
);
1440 init
= force_gimple_operand (init
, &stmts
, true, NULL_TREE
);
1442 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1444 phi
= create_phi_node (var
, loop
->header
);
1445 add_phi_arg (phi
, init
, entry
, UNKNOWN_LOCATION
);
1446 add_phi_arg (phi
, next
, latch
, UNKNOWN_LOCATION
);
1450 /* Create the variables and initialization statement for root of chain
1451 CHAIN. Uids of the newly created temporary variables are marked
1455 initialize_root (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1457 dref root
= get_chain_root (chain
);
1458 bool in_lhs
= (chain
->type
== CT_STORE_LOAD
1459 || chain
->type
== CT_COMBINATION
);
1461 initialize_root_vars (loop
, chain
, tmp_vars
);
1462 replace_ref_with (root
->stmt
,
1463 chain
->vars
[chain
->length
],
1467 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1468 initialization on entry to LOOP if necessary. The ssa name for the variable
1469 is stored in VARS. If WRITTEN is true, also a phi node to copy its value
1470 around the loop is created. Uid of the newly created temporary variable
1471 is marked in TMP_VARS. INITS is the list containing the (single)
1475 initialize_root_vars_lm (struct loop
*loop
, dref root
, bool written
,
1476 vec
<tree
> *vars
, vec
<tree
> inits
,
1480 tree ref
= DR_REF (root
->ref
), init
, var
, next
;
1483 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1485 /* Find the initializer for the variable, and check that it cannot
1489 vars
->create (written
? 2 : 1);
1490 var
= predcom_tmp_var (ref
, 0, tmp_vars
);
1491 vars
->quick_push (var
);
1493 vars
->quick_push ((*vars
)[0]);
1495 FOR_EACH_VEC_ELT (*vars
, i
, var
)
1496 (*vars
)[i
] = make_ssa_name (var
, NULL
);
1500 init
= force_gimple_operand (init
, &stmts
, written
, NULL_TREE
);
1502 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1507 phi
= create_phi_node (var
, loop
->header
);
1508 add_phi_arg (phi
, init
, entry
, UNKNOWN_LOCATION
);
1509 add_phi_arg (phi
, next
, latch
, UNKNOWN_LOCATION
);
1513 gimple init_stmt
= gimple_build_assign (var
, init
);
1514 gsi_insert_on_edge_immediate (entry
, init_stmt
);
1519 /* Execute load motion for references in chain CHAIN. Uids of the newly
1520 created temporary variables are marked in TMP_VARS. */
1523 execute_load_motion (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1527 unsigned n_writes
= 0, ridx
, i
;
1530 gcc_assert (chain
->type
== CT_INVARIANT
);
1531 gcc_assert (!chain
->combined
);
1532 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
1533 if (DR_IS_WRITE (a
->ref
))
1536 /* If there are no reads in the loop, there is nothing to do. */
1537 if (n_writes
== chain
->refs
.length ())
1540 initialize_root_vars_lm (loop
, get_chain_root (chain
), n_writes
> 0,
1541 &vars
, chain
->inits
, tmp_vars
);
1544 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
1546 bool is_read
= DR_IS_READ (a
->ref
);
1548 if (DR_IS_WRITE (a
->ref
))
1554 var
= make_ssa_name (SSA_NAME_VAR (var
), NULL
);
1561 replace_ref_with (a
->stmt
, vars
[ridx
],
1562 !is_read
, !is_read
);
1568 /* Returns the single statement in that NAME is used, excepting
1569 the looparound phi nodes contained in one of the chains. If there is no
1570 such statement, or more statements, NULL is returned. */
1573 single_nonlooparound_use (tree name
)
1576 imm_use_iterator it
;
1577 gimple stmt
, ret
= NULL
;
1579 FOR_EACH_IMM_USE_FAST (use
, it
, name
)
1581 stmt
= USE_STMT (use
);
1583 if (gimple_code (stmt
) == GIMPLE_PHI
)
1585 /* Ignore uses in looparound phi nodes. Uses in other phi nodes
1586 could not be processed anyway, so just fail for them. */
1587 if (bitmap_bit_p (looparound_phis
,
1588 SSA_NAME_VERSION (PHI_RESULT (stmt
))))
1593 else if (is_gimple_debug (stmt
))
1595 else if (ret
!= NULL
)
1604 /* Remove statement STMT, as well as the chain of assignments in that it is
1608 remove_stmt (gimple stmt
)
1612 gimple_stmt_iterator psi
;
1614 if (gimple_code (stmt
) == GIMPLE_PHI
)
1616 name
= PHI_RESULT (stmt
);
1617 next
= single_nonlooparound_use (name
);
1618 reset_debug_uses (stmt
);
1619 psi
= gsi_for_stmt (stmt
);
1620 remove_phi_node (&psi
, true);
1623 || !gimple_assign_ssa_name_copy_p (next
)
1624 || gimple_assign_rhs1 (next
) != name
)
1632 gimple_stmt_iterator bsi
;
1634 bsi
= gsi_for_stmt (stmt
);
1636 name
= gimple_assign_lhs (stmt
);
1637 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1639 next
= single_nonlooparound_use (name
);
1640 reset_debug_uses (stmt
);
1642 unlink_stmt_vdef (stmt
);
1643 gsi_remove (&bsi
, true);
1644 release_defs (stmt
);
1647 || !gimple_assign_ssa_name_copy_p (next
)
1648 || gimple_assign_rhs1 (next
) != name
)
1655 /* Perform the predictive commoning optimization for a chain CHAIN.
1656 Uids of the newly created temporary variables are marked in TMP_VARS.*/
1659 execute_pred_commoning_chain (struct loop
*loop
, chain_p chain
,
1666 if (chain
->combined
)
1668 /* For combined chains, just remove the statements that are used to
1669 compute the values of the expression (except for the root one). */
1670 for (i
= 1; chain
->refs
.iterate (i
, &a
); i
++)
1671 remove_stmt (a
->stmt
);
1675 /* For non-combined chains, set up the variables that hold its value,
1676 and replace the uses of the original references by these
1678 initialize_root (loop
, chain
, tmp_vars
);
1679 for (i
= 1; chain
->refs
.iterate (i
, &a
); i
++)
1681 var
= chain
->vars
[chain
->length
- a
->distance
];
1682 replace_ref_with (a
->stmt
, var
, false, false);
1687 /* Determines the unroll factor necessary to remove as many temporary variable
1688 copies as possible. CHAINS is the list of chains that will be
1692 determine_unroll_factor (vec
<chain_p
> chains
)
1695 unsigned factor
= 1, af
, nfactor
, i
;
1696 unsigned max
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
1698 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1700 if (chain
->type
== CT_INVARIANT
|| chain
->combined
)
1703 /* The best unroll factor for this chain is equal to the number of
1704 temporary variables that we create for it. */
1706 if (chain
->has_max_use_after
)
1709 nfactor
= factor
* af
/ gcd (factor
, af
);
1717 /* Perform the predictive commoning optimization for CHAINS.
1718 Uids of the newly created temporary variables are marked in TMP_VARS. */
1721 execute_pred_commoning (struct loop
*loop
, vec
<chain_p
> chains
,
1727 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1729 if (chain
->type
== CT_INVARIANT
)
1730 execute_load_motion (loop
, chain
, tmp_vars
);
1732 execute_pred_commoning_chain (loop
, chain
, tmp_vars
);
1735 update_ssa (TODO_update_ssa_only_virtuals
);
1738 /* For each reference in CHAINS, if its defining statement is
1739 phi node, record the ssa name that is defined by it. */
1742 replace_phis_by_defined_names (vec
<chain_p
> chains
)
1748 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1749 FOR_EACH_VEC_ELT (chain
->refs
, j
, a
)
1751 if (gimple_code (a
->stmt
) == GIMPLE_PHI
)
1753 a
->name_defined_by_phi
= PHI_RESULT (a
->stmt
);
1759 /* For each reference in CHAINS, if name_defined_by_phi is not
1760 NULL, use it to set the stmt field. */
1763 replace_names_by_phis (vec
<chain_p
> chains
)
1769 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1770 FOR_EACH_VEC_ELT (chain
->refs
, j
, a
)
1771 if (a
->stmt
== NULL
)
1773 a
->stmt
= SSA_NAME_DEF_STMT (a
->name_defined_by_phi
);
1774 gcc_assert (gimple_code (a
->stmt
) == GIMPLE_PHI
);
1775 a
->name_defined_by_phi
= NULL_TREE
;
1779 /* Wrapper over execute_pred_commoning, to pass it as a callback
1780 to tree_transform_and_unroll_loop. */
1784 vec
<chain_p
> chains
;
1789 execute_pred_commoning_cbck (struct loop
*loop
, void *data
)
1791 struct epcc_data
*const dta
= (struct epcc_data
*) data
;
1793 /* Restore phi nodes that were replaced by ssa names before
1794 tree_transform_and_unroll_loop (see detailed description in
1795 tree_predictive_commoning_loop). */
1796 replace_names_by_phis (dta
->chains
);
1797 execute_pred_commoning (loop
, dta
->chains
, dta
->tmp_vars
);
1800 /* Base NAME and all the names in the chain of phi nodes that use it
1801 on variable VAR. The phi nodes are recognized by being in the copies of
1802 the header of the LOOP. */
1805 base_names_in_chain_on (struct loop
*loop
, tree name
, tree var
)
1808 imm_use_iterator iter
;
1810 replace_ssa_name_symbol (name
, var
);
1815 FOR_EACH_IMM_USE_STMT (stmt
, iter
, name
)
1817 if (gimple_code (stmt
) == GIMPLE_PHI
1818 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1821 BREAK_FROM_IMM_USE_STMT (iter
);
1827 name
= PHI_RESULT (phi
);
1828 replace_ssa_name_symbol (name
, var
);
1832 /* Given an unrolled LOOP after predictive commoning, remove the
1833 register copies arising from phi nodes by changing the base
1834 variables of SSA names. TMP_VARS is the set of the temporary variables
1835 for those we want to perform this. */
1838 eliminate_temp_copies (struct loop
*loop
, bitmap tmp_vars
)
1842 tree name
, use
, var
;
1843 gimple_stmt_iterator psi
;
1845 e
= loop_latch_edge (loop
);
1846 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1848 phi
= gsi_stmt (psi
);
1849 name
= PHI_RESULT (phi
);
1850 var
= SSA_NAME_VAR (name
);
1851 if (!var
|| !bitmap_bit_p (tmp_vars
, DECL_UID (var
)))
1853 use
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1854 gcc_assert (TREE_CODE (use
) == SSA_NAME
);
1856 /* Base all the ssa names in the ud and du chain of NAME on VAR. */
1857 stmt
= SSA_NAME_DEF_STMT (use
);
1858 while (gimple_code (stmt
) == GIMPLE_PHI
1859 /* In case we could not unroll the loop enough to eliminate
1860 all copies, we may reach the loop header before the defining
1861 statement (in that case, some register copies will be present
1862 in loop latch in the final code, corresponding to the newly
1863 created looparound phi nodes). */
1864 && gimple_bb (stmt
) != loop
->header
)
1866 gcc_assert (single_pred_p (gimple_bb (stmt
)));
1867 use
= PHI_ARG_DEF (stmt
, 0);
1868 stmt
= SSA_NAME_DEF_STMT (use
);
1871 base_names_in_chain_on (loop
, use
, var
);
1875 /* Returns true if CHAIN is suitable to be combined. */
1878 chain_can_be_combined_p (chain_p chain
)
1880 return (!chain
->combined
1881 && (chain
->type
== CT_LOAD
|| chain
->type
== CT_COMBINATION
));
1884 /* Returns the modify statement that uses NAME. Skips over assignment
1885 statements, NAME is replaced with the actual name used in the returned
1889 find_use_stmt (tree
*name
)
1894 /* Skip over assignments. */
1897 stmt
= single_nonlooparound_use (*name
);
1901 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1904 lhs
= gimple_assign_lhs (stmt
);
1905 if (TREE_CODE (lhs
) != SSA_NAME
)
1908 if (gimple_assign_copy_p (stmt
))
1910 rhs
= gimple_assign_rhs1 (stmt
);
1916 else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1917 == GIMPLE_BINARY_RHS
)
1924 /* Returns true if we may perform reassociation for operation CODE in TYPE. */
1927 may_reassociate_p (tree type
, enum tree_code code
)
1929 if (FLOAT_TYPE_P (type
)
1930 && !flag_unsafe_math_optimizations
)
1933 return (commutative_tree_code (code
)
1934 && associative_tree_code (code
));
1937 /* If the operation used in STMT is associative and commutative, go through the
1938 tree of the same operations and returns its root. Distance to the root
1939 is stored in DISTANCE. */
1942 find_associative_operation_root (gimple stmt
, unsigned *distance
)
1946 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1947 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1950 if (!may_reassociate_p (type
, code
))
1955 lhs
= gimple_assign_lhs (stmt
);
1956 gcc_assert (TREE_CODE (lhs
) == SSA_NAME
);
1958 next
= find_use_stmt (&lhs
);
1960 || gimple_assign_rhs_code (next
) != code
)
1972 /* Returns the common statement in that NAME1 and NAME2 have a use. If there
1973 is no such statement, returns NULL_TREE. In case the operation used on
1974 NAME1 and NAME2 is associative and commutative, returns the root of the
1975 tree formed by this operation instead of the statement that uses NAME1 or
1979 find_common_use_stmt (tree
*name1
, tree
*name2
)
1981 gimple stmt1
, stmt2
;
1983 stmt1
= find_use_stmt (name1
);
1987 stmt2
= find_use_stmt (name2
);
1994 stmt1
= find_associative_operation_root (stmt1
, NULL
);
1997 stmt2
= find_associative_operation_root (stmt2
, NULL
);
2001 return (stmt1
== stmt2
? stmt1
: NULL
);
2004 /* Checks whether R1 and R2 are combined together using CODE, with the result
2005 in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2006 if it is true. If CODE is ERROR_MARK, set these values instead. */
2009 combinable_refs_p (dref r1
, dref r2
,
2010 enum tree_code
*code
, bool *swap
, tree
*rslt_type
)
2012 enum tree_code acode
;
2018 name1
= name_for_ref (r1
);
2019 name2
= name_for_ref (r2
);
2020 gcc_assert (name1
!= NULL_TREE
&& name2
!= NULL_TREE
);
2022 stmt
= find_common_use_stmt (&name1
, &name2
);
2025 /* A simple post-dominance check - make sure the combination
2026 is executed under the same condition as the references. */
2027 || (gimple_bb (stmt
) != gimple_bb (r1
->stmt
)
2028 && gimple_bb (stmt
) != gimple_bb (r2
->stmt
)))
2031 acode
= gimple_assign_rhs_code (stmt
);
2032 aswap
= (!commutative_tree_code (acode
)
2033 && gimple_assign_rhs1 (stmt
) != name1
);
2034 atype
= TREE_TYPE (gimple_assign_lhs (stmt
));
2036 if (*code
== ERROR_MARK
)
2044 return (*code
== acode
2046 && *rslt_type
== atype
);
2049 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2050 an assignment of the remaining operand. */
2053 remove_name_from_operation (gimple stmt
, tree op
)
2056 gimple_stmt_iterator si
;
2058 gcc_assert (is_gimple_assign (stmt
));
2060 if (gimple_assign_rhs1 (stmt
) == op
)
2061 other_op
= gimple_assign_rhs2 (stmt
);
2063 other_op
= gimple_assign_rhs1 (stmt
);
2065 si
= gsi_for_stmt (stmt
);
2066 gimple_assign_set_rhs_from_tree (&si
, other_op
);
2068 /* We should not have reallocated STMT. */
2069 gcc_assert (gsi_stmt (si
) == stmt
);
2074 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2075 are combined in a single statement, and returns this statement. */
2078 reassociate_to_the_same_stmt (tree name1
, tree name2
)
2080 gimple stmt1
, stmt2
, root1
, root2
, s1
, s2
;
2081 gimple new_stmt
, tmp_stmt
;
2082 tree new_name
, tmp_name
, var
, r1
, r2
;
2083 unsigned dist1
, dist2
;
2084 enum tree_code code
;
2085 tree type
= TREE_TYPE (name1
);
2086 gimple_stmt_iterator bsi
;
2088 stmt1
= find_use_stmt (&name1
);
2089 stmt2
= find_use_stmt (&name2
);
2090 root1
= find_associative_operation_root (stmt1
, &dist1
);
2091 root2
= find_associative_operation_root (stmt2
, &dist2
);
2092 code
= gimple_assign_rhs_code (stmt1
);
2094 gcc_assert (root1
&& root2
&& root1
== root2
2095 && code
== gimple_assign_rhs_code (stmt2
));
2097 /* Find the root of the nearest expression in that both NAME1 and NAME2
2104 while (dist1
> dist2
)
2106 s1
= find_use_stmt (&r1
);
2107 r1
= gimple_assign_lhs (s1
);
2110 while (dist2
> dist1
)
2112 s2
= find_use_stmt (&r2
);
2113 r2
= gimple_assign_lhs (s2
);
2119 s1
= find_use_stmt (&r1
);
2120 r1
= gimple_assign_lhs (s1
);
2121 s2
= find_use_stmt (&r2
);
2122 r2
= gimple_assign_lhs (s2
);
2125 /* Remove NAME1 and NAME2 from the statements in that they are used
2127 remove_name_from_operation (stmt1
, name1
);
2128 remove_name_from_operation (stmt2
, name2
);
2130 /* Insert the new statement combining NAME1 and NAME2 before S1, and
2131 combine it with the rhs of S1. */
2132 var
= create_tmp_reg (type
, "predreastmp");
2133 new_name
= make_ssa_name (var
, NULL
);
2134 new_stmt
= gimple_build_assign_with_ops (code
, new_name
, name1
, name2
);
2136 var
= create_tmp_reg (type
, "predreastmp");
2137 tmp_name
= make_ssa_name (var
, NULL
);
2139 /* Rhs of S1 may now be either a binary expression with operation
2140 CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2141 so that name1 or name2 was removed from it). */
2142 tmp_stmt
= gimple_build_assign_with_ops (gimple_assign_rhs_code (s1
),
2144 gimple_assign_rhs1 (s1
),
2145 gimple_assign_rhs2 (s1
));
2147 bsi
= gsi_for_stmt (s1
);
2148 gimple_assign_set_rhs_with_ops (&bsi
, code
, new_name
, tmp_name
);
2149 s1
= gsi_stmt (bsi
);
2152 gsi_insert_before (&bsi
, new_stmt
, GSI_SAME_STMT
);
2153 gsi_insert_before (&bsi
, tmp_stmt
, GSI_SAME_STMT
);
2158 /* Returns the statement that combines references R1 and R2. In case R1
2159 and R2 are not used in the same statement, but they are used with an
2160 associative and commutative operation in the same expression, reassociate
2161 the expression so that they are used in the same statement. */
2164 stmt_combining_refs (dref r1
, dref r2
)
2166 gimple stmt1
, stmt2
;
2167 tree name1
= name_for_ref (r1
);
2168 tree name2
= name_for_ref (r2
);
2170 stmt1
= find_use_stmt (&name1
);
2171 stmt2
= find_use_stmt (&name2
);
2175 return reassociate_to_the_same_stmt (name1
, name2
);
2178 /* Tries to combine chains CH1 and CH2 together. If this succeeds, the
2179 description of the new chain is returned, otherwise we return NULL. */
2182 combine_chains (chain_p ch1
, chain_p ch2
)
2185 enum tree_code op
= ERROR_MARK
;
2190 tree rslt_type
= NULL_TREE
;
2194 if (ch1
->length
!= ch2
->length
)
2197 if (ch1
->refs
.length () != ch2
->refs
.length ())
2200 for (i
= 0; (ch1
->refs
.iterate (i
, &r1
)
2201 && ch2
->refs
.iterate (i
, &r2
)); i
++)
2203 if (r1
->distance
!= r2
->distance
)
2206 if (!combinable_refs_p (r1
, r2
, &op
, &swap
, &rslt_type
))
2217 new_chain
= XCNEW (struct chain
);
2218 new_chain
->type
= CT_COMBINATION
;
2220 new_chain
->ch1
= ch1
;
2221 new_chain
->ch2
= ch2
;
2222 new_chain
->rslt_type
= rslt_type
;
2223 new_chain
->length
= ch1
->length
;
2225 for (i
= 0; (ch1
->refs
.iterate (i
, &r1
)
2226 && ch2
->refs
.iterate (i
, &r2
)); i
++)
2228 nw
= XCNEW (struct dref_d
);
2229 nw
->stmt
= stmt_combining_refs (r1
, r2
);
2230 nw
->distance
= r1
->distance
;
2232 new_chain
->refs
.safe_push (nw
);
2235 new_chain
->has_max_use_after
= false;
2236 root_stmt
= get_chain_root (new_chain
)->stmt
;
2237 for (i
= 1; new_chain
->refs
.iterate (i
, &nw
); i
++)
2239 if (nw
->distance
== new_chain
->length
2240 && !stmt_dominates_stmt_p (nw
->stmt
, root_stmt
))
2242 new_chain
->has_max_use_after
= true;
2247 ch1
->combined
= true;
2248 ch2
->combined
= true;
2252 /* Try to combine the CHAINS. */
2255 try_combine_chains (vec
<chain_p
> *chains
)
2258 chain_p ch1
, ch2
, cch
;
2259 vec
<chain_p
> worklist
= vNULL
;
2261 FOR_EACH_VEC_ELT (*chains
, i
, ch1
)
2262 if (chain_can_be_combined_p (ch1
))
2263 worklist
.safe_push (ch1
);
2265 while (!worklist
.is_empty ())
2267 ch1
= worklist
.pop ();
2268 if (!chain_can_be_combined_p (ch1
))
2271 FOR_EACH_VEC_ELT (*chains
, j
, ch2
)
2273 if (!chain_can_be_combined_p (ch2
))
2276 cch
= combine_chains (ch1
, ch2
);
2279 worklist
.safe_push (cch
);
2280 chains
->safe_push (cch
);
2286 worklist
.release ();
2289 /* Prepare initializers for CHAIN in LOOP. Returns false if this is
2290 impossible because one of these initializers may trap, true otherwise. */
2293 prepare_initializers_chain (struct loop
*loop
, chain_p chain
)
2295 unsigned i
, n
= (chain
->type
== CT_INVARIANT
) ? 1 : chain
->length
;
2296 struct data_reference
*dr
= get_chain_root (chain
)->ref
;
2300 edge entry
= loop_preheader_edge (loop
);
2302 /* Find the initializers for the variables, and check that they cannot
2304 chain
->inits
.create (n
);
2305 for (i
= 0; i
< n
; i
++)
2306 chain
->inits
.quick_push (NULL_TREE
);
2308 /* If we have replaced some looparound phi nodes, use their initializers
2309 instead of creating our own. */
2310 FOR_EACH_VEC_ELT (chain
->refs
, i
, laref
)
2312 if (gimple_code (laref
->stmt
) != GIMPLE_PHI
)
2315 gcc_assert (laref
->distance
> 0);
2316 chain
->inits
[n
- laref
->distance
]
2317 = PHI_ARG_DEF_FROM_EDGE (laref
->stmt
, entry
);
2320 for (i
= 0; i
< n
; i
++)
2322 if (chain
->inits
[i
] != NULL_TREE
)
2325 init
= ref_at_iteration (dr
, (int) i
- n
, &stmts
);
2326 if (!chain
->all_always_accessed
&& tree_could_trap_p (init
))
2330 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
2332 chain
->inits
[i
] = init
;
2338 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2339 be used because the initializers might trap. */
2342 prepare_initializers (struct loop
*loop
, vec
<chain_p
> chains
)
2347 for (i
= 0; i
< chains
.length (); )
2350 if (prepare_initializers_chain (loop
, chain
))
2354 release_chain (chain
);
2355 chains
.unordered_remove (i
);
2360 /* Performs predictive commoning for LOOP. Returns true if LOOP was
2364 tree_predictive_commoning_loop (struct loop
*loop
)
2366 vec
<loop_p
> loop_nest
;
2367 vec
<data_reference_p
> datarefs
;
2368 vec
<ddr_p
> dependences
;
2369 struct component
*components
;
2370 vec
<chain_p
> chains
= vNULL
;
2371 unsigned unroll_factor
;
2372 struct tree_niter_desc desc
;
2373 bool unroll
= false;
2377 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2378 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
2380 /* Find the data references and split them into components according to their
2381 dependence relations. */
2382 datarefs
.create (10);
2383 dependences
.create (10);
2384 loop_nest
.create (3);
2385 if (! compute_data_dependences_for_loop (loop
, true, &loop_nest
, &datarefs
,
2388 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2389 fprintf (dump_file
, "Cannot analyze data dependencies\n");
2390 loop_nest
.release ();
2391 free_data_refs (datarefs
);
2392 free_dependence_relations (dependences
);
2396 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2397 dump_data_dependence_relations (dump_file
, dependences
);
2399 components
= split_data_refs_to_components (loop
, datarefs
, dependences
);
2400 loop_nest
.release ();
2401 free_dependence_relations (dependences
);
2404 free_data_refs (datarefs
);
2405 free_affine_expand_cache (&name_expansions
);
2409 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2411 fprintf (dump_file
, "Initial state:\n\n");
2412 dump_components (dump_file
, components
);
2415 /* Find the suitable components and split them into chains. */
2416 components
= filter_suitable_components (loop
, components
);
2418 tmp_vars
= BITMAP_ALLOC (NULL
);
2419 looparound_phis
= BITMAP_ALLOC (NULL
);
2420 determine_roots (loop
, components
, &chains
);
2421 release_components (components
);
2423 if (!chains
.exists ())
2425 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2427 "Predictive commoning failed: no suitable chains\n");
2430 prepare_initializers (loop
, chains
);
2432 /* Try to combine the chains that are always worked with together. */
2433 try_combine_chains (&chains
);
2435 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2437 fprintf (dump_file
, "Before commoning:\n\n");
2438 dump_chains (dump_file
, chains
);
2441 /* Determine the unroll factor, and if the loop should be unrolled, ensure
2442 that its number of iterations is divisible by the factor. */
2443 unroll_factor
= determine_unroll_factor (chains
);
2445 unroll
= (unroll_factor
> 1
2446 && can_unroll_loop_p (loop
, unroll_factor
, &desc
));
2447 exit
= single_dom_exit (loop
);
2449 /* Execute the predictive commoning transformations, and possibly unroll the
2453 struct epcc_data dta
;
2455 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2456 fprintf (dump_file
, "Unrolling %u times.\n", unroll_factor
);
2458 dta
.chains
= chains
;
2459 dta
.tmp_vars
= tmp_vars
;
2461 update_ssa (TODO_update_ssa_only_virtuals
);
2463 /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2464 execute_pred_commoning_cbck is called may cause phi nodes to be
2465 reallocated, which is a problem since CHAINS may point to these
2466 statements. To fix this, we store the ssa names defined by the
2467 phi nodes here instead of the phi nodes themselves, and restore
2468 the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
2469 replace_phis_by_defined_names (chains
);
2471 tree_transform_and_unroll_loop (loop
, unroll_factor
, exit
, &desc
,
2472 execute_pred_commoning_cbck
, &dta
);
2473 eliminate_temp_copies (loop
, tmp_vars
);
2477 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2479 "Executing predictive commoning without unrolling.\n");
2480 execute_pred_commoning (loop
, chains
, tmp_vars
);
2484 release_chains (chains
);
2485 free_data_refs (datarefs
);
2486 BITMAP_FREE (tmp_vars
);
2487 BITMAP_FREE (looparound_phis
);
2489 free_affine_expand_cache (&name_expansions
);
2494 /* Runs predictive commoning. */
2497 tree_predictive_commoning (void)
2499 bool unrolled
= false;
2504 initialize_original_copy_tables ();
2505 FOR_EACH_LOOP (li
, loop
, LI_ONLY_INNERMOST
)
2506 if (optimize_loop_for_speed_p (loop
))
2508 unrolled
|= tree_predictive_commoning_loop (loop
);
2514 ret
= TODO_cleanup_cfg
;
2516 free_original_copy_tables ();