1 /* Predictive commoning.
2 Copyright (C) 2005, 2007 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 upto 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 "diagnostic.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
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 DEF_VEC_ALLOC_P (dref
, heap
);
244 /* Type of the chain of the references. */
248 /* The addresses of the references in the chain are constant. */
251 /* There are only loads in the chain. */
254 /* Root of the chain is store, the rest are loads. */
257 /* A combination of two chains. */
261 /* Chains of data references. */
265 /* Type of the chain. */
266 enum chain_type type
;
268 /* For combination chains, the operator and the two chains that are
269 combined, and the type of the result. */
272 struct chain
*ch1
, *ch2
;
274 /* The references in the chain. */
275 VEC(dref
,heap
) *refs
;
277 /* The maximum distance of the reference in the chain from the root. */
280 /* The variables used to copy the value throughout iterations. */
281 VEC(tree
,heap
) *vars
;
283 /* Initializers for the variables. */
284 VEC(tree
,heap
) *inits
;
286 /* True if there is a use of a variable with the maximal distance
287 that comes after the root in the loop. */
288 unsigned has_max_use_after
: 1;
290 /* True if all the memory references in the chain are always accessed. */
291 unsigned all_always_accessed
: 1;
293 /* True if this chain was combined together with some other chain. */
294 unsigned combined
: 1;
298 DEF_VEC_ALLOC_P (chain_p
, heap
);
300 /* Describes the knowledge about the step of the memory references in
305 /* The step is zero. */
308 /* The step is nonzero. */
311 /* The step may or may not be nonzero. */
315 /* Components of the data dependence graph. */
319 /* The references in the component. */
320 VEC(dref
,heap
) *refs
;
322 /* What we know about the step of the references in the component. */
323 enum ref_step_type comp_step
;
325 /* Next component in the list. */
326 struct component
*next
;
329 /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */
331 static bitmap looparound_phis
;
333 /* Cache used by tree_to_aff_combination_expand. */
335 static struct pointer_map_t
*name_expansions
;
337 /* Dumps data reference REF to FILE. */
339 extern void dump_dref (FILE *, dref
);
341 dump_dref (FILE *file
, dref ref
)
346 print_generic_expr (file
, DR_REF (ref
->ref
), TDF_SLIM
);
347 fprintf (file
, " (id %u%s)\n", ref
->pos
,
348 DR_IS_READ (ref
->ref
) ? "" : ", write");
350 fprintf (file
, " offset ");
351 dump_double_int (file
, ref
->offset
, false);
352 fprintf (file
, "\n");
354 fprintf (file
, " distance %u\n", ref
->distance
);
358 if (gimple_code (ref
->stmt
) == GIMPLE_PHI
)
359 fprintf (file
, " looparound ref\n");
361 fprintf (file
, " combination ref\n");
362 fprintf (file
, " in statement ");
363 print_gimple_stmt (file
, ref
->stmt
, 0, TDF_SLIM
);
364 fprintf (file
, "\n");
365 fprintf (file
, " distance %u\n", ref
->distance
);
370 /* Dumps CHAIN to FILE. */
372 extern void dump_chain (FILE *, chain_p
);
374 dump_chain (FILE *file
, chain_p chain
)
377 const char *chain_type
;
384 chain_type
= "Load motion";
388 chain_type
= "Loads-only";
392 chain_type
= "Store-loads";
396 chain_type
= "Combination";
403 fprintf (file
, "%s chain %p%s\n", chain_type
, (void *) chain
,
404 chain
->combined
? " (combined)" : "");
405 if (chain
->type
!= CT_INVARIANT
)
406 fprintf (file
, " max distance %u%s\n", chain
->length
,
407 chain
->has_max_use_after
? "" : ", may reuse first");
409 if (chain
->type
== CT_COMBINATION
)
411 fprintf (file
, " equal to %p %s %p in type ",
412 (void *) chain
->ch1
, op_symbol_code (chain
->op
),
413 (void *) chain
->ch2
);
414 print_generic_expr (file
, chain
->rslt_type
, TDF_SLIM
);
415 fprintf (file
, "\n");
420 fprintf (file
, " vars");
421 for (i
= 0; VEC_iterate (tree
, chain
->vars
, i
, var
); i
++)
424 print_generic_expr (file
, var
, TDF_SLIM
);
426 fprintf (file
, "\n");
431 fprintf (file
, " inits");
432 for (i
= 0; VEC_iterate (tree
, chain
->inits
, i
, var
); i
++)
435 print_generic_expr (file
, var
, TDF_SLIM
);
437 fprintf (file
, "\n");
440 fprintf (file
, " references:\n");
441 for (i
= 0; VEC_iterate (dref
, chain
->refs
, i
, a
); i
++)
444 fprintf (file
, "\n");
447 /* Dumps CHAINS to FILE. */
449 extern void dump_chains (FILE *, VEC (chain_p
, heap
) *);
451 dump_chains (FILE *file
, VEC (chain_p
, heap
) *chains
)
456 for (i
= 0; VEC_iterate (chain_p
, chains
, i
, chain
); i
++)
457 dump_chain (file
, chain
);
460 /* Dumps COMP to FILE. */
462 extern void dump_component (FILE *, struct component
*);
464 dump_component (FILE *file
, struct component
*comp
)
469 fprintf (file
, "Component%s:\n",
470 comp
->comp_step
== RS_INVARIANT
? " (invariant)" : "");
471 for (i
= 0; VEC_iterate (dref
, comp
->refs
, i
, a
); i
++)
473 fprintf (file
, "\n");
476 /* Dumps COMPS to FILE. */
478 extern void dump_components (FILE *, struct component
*);
480 dump_components (FILE *file
, struct component
*comps
)
482 struct component
*comp
;
484 for (comp
= comps
; comp
; comp
= comp
->next
)
485 dump_component (file
, comp
);
488 /* Frees a chain CHAIN. */
491 release_chain (chain_p chain
)
499 for (i
= 0; VEC_iterate (dref
, chain
->refs
, i
, ref
); i
++)
502 VEC_free (dref
, heap
, chain
->refs
);
503 VEC_free (tree
, heap
, chain
->vars
);
504 VEC_free (tree
, heap
, chain
->inits
);
512 release_chains (VEC (chain_p
, heap
) *chains
)
517 for (i
= 0; VEC_iterate (chain_p
, chains
, i
, chain
); i
++)
518 release_chain (chain
);
519 VEC_free (chain_p
, heap
, chains
);
522 /* Frees a component COMP. */
525 release_component (struct component
*comp
)
527 VEC_free (dref
, heap
, comp
->refs
);
531 /* Frees list of components COMPS. */
534 release_components (struct component
*comps
)
536 struct component
*act
, *next
;
538 for (act
= comps
; act
; act
= next
)
541 release_component (act
);
545 /* Finds a root of tree given by FATHERS containing A, and performs path
549 component_of (unsigned fathers
[], unsigned a
)
553 for (root
= a
; root
!= fathers
[root
]; root
= fathers
[root
])
556 for (; a
!= root
; a
= n
)
565 /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the
566 components, A and B are components to merge. */
569 merge_comps (unsigned fathers
[], unsigned sizes
[], unsigned a
, unsigned b
)
571 unsigned ca
= component_of (fathers
, a
);
572 unsigned cb
= component_of (fathers
, b
);
577 if (sizes
[ca
] < sizes
[cb
])
579 sizes
[cb
] += sizes
[ca
];
584 sizes
[ca
] += sizes
[cb
];
589 /* Returns true if A is a reference that is suitable for predictive commoning
590 in the innermost loop that contains it. REF_STEP is set according to the
591 step of the reference A. */
594 suitable_reference_p (struct data_reference
*a
, enum ref_step_type
*ref_step
)
596 tree ref
= DR_REF (a
), step
= DR_STEP (a
);
599 || !is_gimple_reg_type (TREE_TYPE (ref
))
600 || tree_could_throw_p (ref
))
603 if (integer_zerop (step
))
604 *ref_step
= RS_INVARIANT
;
605 else if (integer_nonzerop (step
))
606 *ref_step
= RS_NONZERO
;
613 /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
616 aff_combination_dr_offset (struct data_reference
*dr
, aff_tree
*offset
)
620 tree_to_aff_combination_expand (DR_OFFSET (dr
), sizetype
, offset
,
622 aff_combination_const (&delta
, sizetype
, tree_to_double_int (DR_INIT (dr
)));
623 aff_combination_add (offset
, &delta
);
626 /* Determines number of iterations of the innermost enclosing loop before B
627 refers to exactly the same location as A and stores it to OFF. If A and
628 B do not have the same step, they never meet, or anything else fails,
629 returns false, otherwise returns true. Both A and B are assumed to
630 satisfy suitable_reference_p. */
633 determine_offset (struct data_reference
*a
, struct data_reference
*b
,
636 aff_tree diff
, baseb
, step
;
639 /* Check that both the references access the location in the same type. */
640 typea
= TREE_TYPE (DR_REF (a
));
641 typeb
= TREE_TYPE (DR_REF (b
));
642 if (!useless_type_conversion_p (typeb
, typea
))
645 /* Check whether the base address and the step of both references is the
647 if (!operand_equal_p (DR_STEP (a
), DR_STEP (b
), 0)
648 || !operand_equal_p (DR_BASE_ADDRESS (a
), DR_BASE_ADDRESS (b
), 0))
651 if (integer_zerop (DR_STEP (a
)))
653 /* If the references have loop invariant address, check that they access
654 exactly the same location. */
655 *off
= double_int_zero
;
656 return (operand_equal_p (DR_OFFSET (a
), DR_OFFSET (b
), 0)
657 && operand_equal_p (DR_INIT (a
), DR_INIT (b
), 0));
660 /* Compare the offsets of the addresses, and check whether the difference
661 is a multiple of step. */
662 aff_combination_dr_offset (a
, &diff
);
663 aff_combination_dr_offset (b
, &baseb
);
664 aff_combination_scale (&baseb
, double_int_minus_one
);
665 aff_combination_add (&diff
, &baseb
);
667 tree_to_aff_combination_expand (DR_STEP (a
), sizetype
,
668 &step
, &name_expansions
);
669 return aff_combination_constant_multiple_p (&diff
, &step
, off
);
672 /* Returns the last basic block in LOOP for that we are sure that
673 it is executed whenever the loop is entered. */
676 last_always_executed_block (struct loop
*loop
)
679 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
681 basic_block last
= loop
->latch
;
683 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
684 last
= nearest_common_dominator (CDI_DOMINATORS
, last
, ex
->src
);
685 VEC_free (edge
, heap
, exits
);
690 /* Splits dependence graph on DATAREFS described by DEPENDS to components. */
692 static struct component
*
693 split_data_refs_to_components (struct loop
*loop
,
694 VEC (data_reference_p
, heap
) *datarefs
,
695 VEC (ddr_p
, heap
) *depends
)
697 unsigned i
, n
= VEC_length (data_reference_p
, datarefs
);
698 unsigned ca
, ia
, ib
, bad
;
699 unsigned *comp_father
= XNEWVEC (unsigned, n
+ 1);
700 unsigned *comp_size
= XNEWVEC (unsigned, n
+ 1);
701 struct component
**comps
;
702 struct data_reference
*dr
, *dra
, *drb
;
703 struct data_dependence_relation
*ddr
;
704 struct component
*comp_list
= NULL
, *comp
;
706 basic_block last_always_executed
= last_always_executed_block (loop
);
708 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
712 /* A fake reference for call or asm_expr that may clobber memory;
716 dr
->aux
= (void *) (size_t) i
;
721 /* A component reserved for the "bad" data references. */
725 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
727 enum ref_step_type dummy
;
729 if (!suitable_reference_p (dr
, &dummy
))
731 ia
= (unsigned) (size_t) dr
->aux
;
732 merge_comps (comp_father
, comp_size
, n
, ia
);
736 for (i
= 0; VEC_iterate (ddr_p
, depends
, i
, ddr
); i
++)
738 double_int dummy_off
;
740 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
745 ia
= component_of (comp_father
, (unsigned) (size_t) dra
->aux
);
746 ib
= component_of (comp_father
, (unsigned) (size_t) drb
->aux
);
750 bad
= component_of (comp_father
, n
);
752 /* If both A and B are reads, we may ignore unsuitable dependences. */
753 if (DR_IS_READ (dra
) && DR_IS_READ (drb
)
754 && (ia
== bad
|| ib
== bad
755 || !determine_offset (dra
, drb
, &dummy_off
)))
758 merge_comps (comp_father
, comp_size
, ia
, ib
);
761 comps
= XCNEWVEC (struct component
*, n
);
762 bad
= component_of (comp_father
, n
);
763 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
765 ia
= (unsigned) (size_t) dr
->aux
;
766 ca
= component_of (comp_father
, ia
);
773 comp
= XCNEW (struct component
);
774 comp
->refs
= VEC_alloc (dref
, heap
, comp_size
[ca
]);
778 dataref
= XCNEW (struct dref
);
780 dataref
->stmt
= DR_STMT (dr
);
781 dataref
->offset
= double_int_zero
;
782 dataref
->distance
= 0;
784 dataref
->always_accessed
785 = dominated_by_p (CDI_DOMINATORS
, last_always_executed
,
786 gimple_bb (dataref
->stmt
));
787 dataref
->pos
= VEC_length (dref
, comp
->refs
);
788 VEC_quick_push (dref
, comp
->refs
, dataref
);
791 for (i
= 0; i
< n
; i
++)
796 comp
->next
= comp_list
;
808 /* Returns true if the component COMP satisfies the conditions
809 described in 2) at the beginning of this file. LOOP is the current
813 suitable_component_p (struct loop
*loop
, struct component
*comp
)
817 basic_block ba
, bp
= loop
->header
;
818 bool ok
, has_write
= false;
820 for (i
= 0; VEC_iterate (dref
, comp
->refs
, i
, a
); i
++)
822 ba
= gimple_bb (a
->stmt
);
824 if (!just_once_each_iteration_p (loop
, ba
))
827 gcc_assert (dominated_by_p (CDI_DOMINATORS
, ba
, bp
));
830 if (!DR_IS_READ (a
->ref
))
834 first
= VEC_index (dref
, comp
->refs
, 0);
835 ok
= suitable_reference_p (first
->ref
, &comp
->comp_step
);
837 first
->offset
= double_int_zero
;
839 for (i
= 1; VEC_iterate (dref
, comp
->refs
, i
, a
); i
++)
841 if (!determine_offset (first
->ref
, a
->ref
, &a
->offset
))
844 #ifdef ENABLE_CHECKING
846 enum ref_step_type a_step
;
847 ok
= suitable_reference_p (a
->ref
, &a_step
);
848 gcc_assert (ok
&& a_step
== comp
->comp_step
);
853 /* If there is a write inside the component, we must know whether the
854 step is nonzero or not -- we would not otherwise be able to recognize
855 whether the value accessed by reads comes from the OFFSET-th iteration
856 or the previous one. */
857 if (has_write
&& comp
->comp_step
== RS_ANY
)
863 /* Check the conditions on references inside each of components COMPS,
864 and remove the unsuitable components from the list. The new list
865 of components is returned. The conditions are described in 2) at
866 the beginning of this file. LOOP is the current loop. */
868 static struct component
*
869 filter_suitable_components (struct loop
*loop
, struct component
*comps
)
871 struct component
**comp
, *act
;
873 for (comp
= &comps
; *comp
; )
876 if (suitable_component_p (loop
, act
))
884 for (i
= 0; VEC_iterate (dref
, act
->refs
, i
, ref
); i
++)
886 release_component (act
);
893 /* Compares two drefs A and B by their offset and position. Callback for
897 order_drefs (const void *a
, const void *b
)
899 const dref
*const da
= (const dref
*) a
;
900 const dref
*const db
= (const dref
*) b
;
901 int offcmp
= double_int_scmp ((*da
)->offset
, (*db
)->offset
);
906 return (*da
)->pos
- (*db
)->pos
;
909 /* Returns root of the CHAIN. */
912 get_chain_root (chain_p chain
)
914 return VEC_index (dref
, chain
->refs
, 0);
917 /* Adds REF to the chain CHAIN. */
920 add_ref_to_chain (chain_p chain
, dref ref
)
922 dref root
= get_chain_root (chain
);
925 gcc_assert (double_int_scmp (root
->offset
, ref
->offset
) <= 0);
926 dist
= double_int_add (ref
->offset
, double_int_neg (root
->offset
));
927 if (double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE
), dist
) <= 0)
932 gcc_assert (double_int_fits_in_uhwi_p (dist
));
934 VEC_safe_push (dref
, heap
, chain
->refs
, ref
);
936 ref
->distance
= double_int_to_uhwi (dist
);
938 if (ref
->distance
>= chain
->length
)
940 chain
->length
= ref
->distance
;
941 chain
->has_max_use_after
= false;
944 if (ref
->distance
== chain
->length
945 && ref
->pos
> root
->pos
)
946 chain
->has_max_use_after
= true;
948 chain
->all_always_accessed
&= ref
->always_accessed
;
951 /* Returns the chain for invariant component COMP. */
954 make_invariant_chain (struct component
*comp
)
956 chain_p chain
= XCNEW (struct chain
);
960 chain
->type
= CT_INVARIANT
;
962 chain
->all_always_accessed
= true;
964 for (i
= 0; VEC_iterate (dref
, comp
->refs
, i
, ref
); i
++)
966 VEC_safe_push (dref
, heap
, chain
->refs
, ref
);
967 chain
->all_always_accessed
&= ref
->always_accessed
;
973 /* Make a new chain rooted at REF. */
976 make_rooted_chain (dref ref
)
978 chain_p chain
= XCNEW (struct chain
);
980 chain
->type
= DR_IS_READ (ref
->ref
) ? CT_LOAD
: CT_STORE_LOAD
;
982 VEC_safe_push (dref
, heap
, chain
->refs
, ref
);
983 chain
->all_always_accessed
= ref
->always_accessed
;
990 /* Returns true if CHAIN is not trivial. */
993 nontrivial_chain_p (chain_p chain
)
995 return chain
!= NULL
&& VEC_length (dref
, chain
->refs
) > 1;
998 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1002 name_for_ref (dref ref
)
1006 if (is_gimple_assign (ref
->stmt
))
1008 if (!ref
->ref
|| DR_IS_READ (ref
->ref
))
1009 name
= gimple_assign_lhs (ref
->stmt
);
1011 name
= gimple_assign_rhs1 (ref
->stmt
);
1014 name
= PHI_RESULT (ref
->stmt
);
1016 return (TREE_CODE (name
) == SSA_NAME
? name
: NULL_TREE
);
1019 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1020 iterations of the innermost enclosing loop). */
1023 valid_initializer_p (struct data_reference
*ref
,
1024 unsigned distance
, struct data_reference
*root
)
1026 aff_tree diff
, base
, step
;
1029 if (!DR_BASE_ADDRESS (ref
))
1032 /* Both REF and ROOT must be accessing the same object. */
1033 if (!operand_equal_p (DR_BASE_ADDRESS (ref
), DR_BASE_ADDRESS (root
), 0))
1036 /* The initializer is defined outside of loop, hence its address must be
1037 invariant inside the loop. */
1038 gcc_assert (integer_zerop (DR_STEP (ref
)));
1040 /* If the address of the reference is invariant, initializer must access
1041 exactly the same location. */
1042 if (integer_zerop (DR_STEP (root
)))
1043 return (operand_equal_p (DR_OFFSET (ref
), DR_OFFSET (root
), 0)
1044 && operand_equal_p (DR_INIT (ref
), DR_INIT (root
), 0));
1046 /* Verify that this index of REF is equal to the root's index at
1047 -DISTANCE-th iteration. */
1048 aff_combination_dr_offset (root
, &diff
);
1049 aff_combination_dr_offset (ref
, &base
);
1050 aff_combination_scale (&base
, double_int_minus_one
);
1051 aff_combination_add (&diff
, &base
);
1053 tree_to_aff_combination_expand (DR_STEP (root
), sizetype
, &step
,
1055 if (!aff_combination_constant_multiple_p (&diff
, &step
, &off
))
1058 if (!double_int_equal_p (off
, uhwi_to_double_int (distance
)))
1064 /* Finds looparound phi node of LOOP that copies the value of REF, and if its
1065 initial value is correct (equal to initial value of REF shifted by one
1066 iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT
1067 is the root of the current chain. */
1070 find_looparound_phi (struct loop
*loop
, dref ref
, dref root
)
1072 tree name
, init
, init_ref
;
1073 gimple phi
= NULL
, init_stmt
;
1074 edge latch
= loop_latch_edge (loop
);
1075 struct data_reference init_dr
;
1076 gimple_stmt_iterator psi
;
1078 if (is_gimple_assign (ref
->stmt
))
1080 if (DR_IS_READ (ref
->ref
))
1081 name
= gimple_assign_lhs (ref
->stmt
);
1083 name
= gimple_assign_rhs1 (ref
->stmt
);
1086 name
= PHI_RESULT (ref
->stmt
);
1090 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1092 phi
= gsi_stmt (psi
);
1093 if (PHI_ARG_DEF_FROM_EDGE (phi
, latch
) == name
)
1097 if (gsi_end_p (psi
))
1100 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1101 if (TREE_CODE (init
) != SSA_NAME
)
1103 init_stmt
= SSA_NAME_DEF_STMT (init
);
1104 if (gimple_code (init_stmt
) != GIMPLE_ASSIGN
)
1106 gcc_assert (gimple_assign_lhs (init_stmt
) == init
);
1108 init_ref
= gimple_assign_rhs1 (init_stmt
);
1109 if (!REFERENCE_CLASS_P (init_ref
)
1110 && !DECL_P (init_ref
))
1113 /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1114 loop enclosing PHI). */
1115 memset (&init_dr
, 0, sizeof (struct data_reference
));
1116 DR_REF (&init_dr
) = init_ref
;
1117 DR_STMT (&init_dr
) = phi
;
1118 dr_analyze_innermost (&init_dr
);
1120 if (!valid_initializer_p (&init_dr
, ref
->distance
+ 1, root
->ref
))
1126 /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1129 insert_looparound_copy (chain_p chain
, dref ref
, gimple phi
)
1131 dref nw
= XCNEW (struct dref
), aref
;
1135 nw
->distance
= ref
->distance
+ 1;
1136 nw
->always_accessed
= 1;
1138 for (i
= 0; VEC_iterate (dref
, chain
->refs
, i
, aref
); i
++)
1139 if (aref
->distance
>= nw
->distance
)
1141 VEC_safe_insert (dref
, heap
, chain
->refs
, i
, nw
);
1143 if (nw
->distance
> chain
->length
)
1145 chain
->length
= nw
->distance
;
1146 chain
->has_max_use_after
= false;
1150 /* For references in CHAIN that are copied around the LOOP (created previously
1151 by PRE, or by user), add the results of such copies to the chain. This
1152 enables us to remove the copies by unrolling, and may need less registers
1153 (also, it may allow us to combine chains together). */
1156 add_looparound_copies (struct loop
*loop
, chain_p chain
)
1159 dref ref
, root
= get_chain_root (chain
);
1162 for (i
= 0; VEC_iterate (dref
, chain
->refs
, i
, ref
); i
++)
1164 phi
= find_looparound_phi (loop
, ref
, root
);
1168 bitmap_set_bit (looparound_phis
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
1169 insert_looparound_copy (chain
, ref
, phi
);
1173 /* Find roots of the values and determine distances in the component COMP.
1174 The references are redistributed into CHAINS. LOOP is the current
1178 determine_roots_comp (struct loop
*loop
,
1179 struct component
*comp
,
1180 VEC (chain_p
, heap
) **chains
)
1184 chain_p chain
= NULL
;
1186 /* Invariants are handled specially. */
1187 if (comp
->comp_step
== RS_INVARIANT
)
1189 chain
= make_invariant_chain (comp
);
1190 VEC_safe_push (chain_p
, heap
, *chains
, chain
);
1194 qsort (VEC_address (dref
, comp
->refs
), VEC_length (dref
, comp
->refs
),
1195 sizeof (dref
), order_drefs
);
1197 for (i
= 0; VEC_iterate (dref
, comp
->refs
, i
, a
); i
++)
1199 if (!chain
|| !DR_IS_READ (a
->ref
))
1201 if (nontrivial_chain_p (chain
))
1202 VEC_safe_push (chain_p
, heap
, *chains
, chain
);
1204 release_chain (chain
);
1205 chain
= make_rooted_chain (a
);
1209 add_ref_to_chain (chain
, a
);
1212 if (nontrivial_chain_p (chain
))
1214 add_looparound_copies (loop
, chain
);
1215 VEC_safe_push (chain_p
, heap
, *chains
, chain
);
1218 release_chain (chain
);
1221 /* Find roots of the values and determine distances in components COMPS, and
1222 separates the references to CHAINS. LOOP is the current loop. */
1225 determine_roots (struct loop
*loop
,
1226 struct component
*comps
, VEC (chain_p
, heap
) **chains
)
1228 struct component
*comp
;
1230 for (comp
= comps
; comp
; comp
= comp
->next
)
1231 determine_roots_comp (loop
, comp
, chains
);
1234 /* Replace the reference in statement STMT with temporary variable
1235 NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of
1236 the reference in the statement. IN_LHS is true if the reference
1237 is in the lhs of STMT, false if it is in rhs. */
1240 replace_ref_with (gimple stmt
, tree new_tree
, bool set
, bool in_lhs
)
1244 gimple_stmt_iterator bsi
, psi
;
1246 if (gimple_code (stmt
) == GIMPLE_PHI
)
1248 gcc_assert (!in_lhs
&& !set
);
1250 val
= PHI_RESULT (stmt
);
1251 bsi
= gsi_after_labels (gimple_bb (stmt
));
1252 psi
= gsi_for_stmt (stmt
);
1253 remove_phi_node (&psi
, false);
1255 /* Turn the phi node into GIMPLE_ASSIGN. */
1256 new_stmt
= gimple_build_assign (val
, new_tree
);
1257 gsi_insert_before (&bsi
, new_stmt
, GSI_NEW_STMT
);
1261 /* Since the reference is of gimple_reg type, it should only
1262 appear as lhs or rhs of modify statement. */
1263 gcc_assert (is_gimple_assign (stmt
));
1265 bsi
= gsi_for_stmt (stmt
);
1267 /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */
1270 gcc_assert (!in_lhs
);
1271 gimple_assign_set_rhs_from_tree (&bsi
, new_tree
);
1272 stmt
= gsi_stmt (bsi
);
1279 /* We have statement
1283 If OLD is a memory reference, then VAL is gimple_val, and we transform
1289 Otherwise, we are replacing a combination chain,
1290 VAL is the expression that performs the combination, and OLD is an
1291 SSA name. In this case, we transform the assignment to
1298 val
= gimple_assign_lhs (stmt
);
1299 if (TREE_CODE (val
) != SSA_NAME
)
1301 gcc_assert (gimple_assign_copy_p (stmt
));
1302 val
= gimple_assign_rhs1 (stmt
);
1314 val
= gimple_assign_lhs (stmt
);
1317 new_stmt
= gimple_build_assign (new_tree
, unshare_expr (val
));
1318 gsi_insert_after (&bsi
, new_stmt
, GSI_NEW_STMT
);
1321 /* Returns the reference to the address of REF in the ITER-th iteration of
1322 LOOP, or NULL if we fail to determine it (ITER may be negative). We
1323 try to preserve the original shape of the reference (not rewrite it
1324 as an indirect ref to the address), to make tree_could_trap_p in
1325 prepare_initializers_chain return false more often. */
1328 ref_at_iteration (struct loop
*loop
, tree ref
, int iter
)
1330 tree idx
, *idx_p
, type
, val
, op0
= NULL_TREE
, ret
;
1334 if (handled_component_p (ref
))
1336 op0
= ref_at_iteration (loop
, TREE_OPERAND (ref
, 0), iter
);
1340 else if (!INDIRECT_REF_P (ref
))
1341 return unshare_expr (ref
);
1343 if (TREE_CODE (ref
) == INDIRECT_REF
)
1345 ret
= build1 (INDIRECT_REF
, TREE_TYPE (ref
), NULL_TREE
);
1346 idx
= TREE_OPERAND (ref
, 0);
1347 idx_p
= &TREE_OPERAND (ret
, 0);
1349 else if (TREE_CODE (ref
) == COMPONENT_REF
)
1351 /* Check that the offset is loop invariant. */
1352 if (TREE_OPERAND (ref
, 2)
1353 && !expr_invariant_in_loop_p (loop
, TREE_OPERAND (ref
, 2)))
1356 return build3 (COMPONENT_REF
, TREE_TYPE (ref
), op0
,
1357 unshare_expr (TREE_OPERAND (ref
, 1)),
1358 unshare_expr (TREE_OPERAND (ref
, 2)));
1360 else if (TREE_CODE (ref
) == ARRAY_REF
)
1362 /* Check that the lower bound and the step are loop invariant. */
1363 if (TREE_OPERAND (ref
, 2)
1364 && !expr_invariant_in_loop_p (loop
, TREE_OPERAND (ref
, 2)))
1366 if (TREE_OPERAND (ref
, 3)
1367 && !expr_invariant_in_loop_p (loop
, TREE_OPERAND (ref
, 3)))
1370 ret
= build4 (ARRAY_REF
, TREE_TYPE (ref
), op0
, NULL_TREE
,
1371 unshare_expr (TREE_OPERAND (ref
, 2)),
1372 unshare_expr (TREE_OPERAND (ref
, 3)));
1373 idx
= TREE_OPERAND (ref
, 1);
1374 idx_p
= &TREE_OPERAND (ret
, 1);
1379 ok
= simple_iv (loop
, first_stmt (loop
->header
), idx
, &iv
, true);
1382 iv
.base
= expand_simple_operations (iv
.base
);
1383 if (integer_zerop (iv
.step
))
1384 *idx_p
= unshare_expr (iv
.base
);
1387 type
= TREE_TYPE (iv
.base
);
1388 if (POINTER_TYPE_P (type
))
1390 val
= fold_build2 (MULT_EXPR
, sizetype
, iv
.step
,
1392 val
= fold_build2 (POINTER_PLUS_EXPR
, type
, iv
.base
, val
);
1396 val
= fold_build2 (MULT_EXPR
, type
, iv
.step
,
1397 build_int_cst_type (type
, iter
));
1398 val
= fold_build2 (PLUS_EXPR
, type
, iv
.base
, val
);
1400 *idx_p
= unshare_expr (val
);
1406 /* Get the initialization expression for the INDEX-th temporary variable
1410 get_init_expr (chain_p chain
, unsigned index
)
1412 if (chain
->type
== CT_COMBINATION
)
1414 tree e1
= get_init_expr (chain
->ch1
, index
);
1415 tree e2
= get_init_expr (chain
->ch2
, index
);
1417 return fold_build2 (chain
->op
, chain
->rslt_type
, e1
, e2
);
1420 return VEC_index (tree
, chain
->inits
, index
);
1423 /* Marks all virtual operands of statement STMT for renaming. */
1426 mark_virtual_ops_for_renaming (gimple stmt
)
1431 if (gimple_code (stmt
) == GIMPLE_PHI
)
1433 var
= PHI_RESULT (stmt
);
1434 if (is_gimple_reg (var
))
1437 if (TREE_CODE (var
) == SSA_NAME
)
1438 var
= SSA_NAME_VAR (var
);
1439 mark_sym_for_renaming (var
);
1445 FOR_EACH_SSA_TREE_OPERAND (var
, stmt
, iter
, SSA_OP_ALL_VIRTUALS
)
1447 if (TREE_CODE (var
) == SSA_NAME
)
1448 var
= SSA_NAME_VAR (var
);
1449 mark_sym_for_renaming (var
);
1453 /* Calls mark_virtual_ops_for_renaming for all members of LIST. */
1456 mark_virtual_ops_for_renaming_list (gimple_seq list
)
1458 gimple_stmt_iterator gsi
;
1460 for (gsi
= gsi_start (list
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1461 mark_virtual_ops_for_renaming (gsi_stmt (gsi
));
1464 /* Returns a new temporary variable used for the I-th variable carrying
1465 value of REF. The variable's uid is marked in TMP_VARS. */
1468 predcom_tmp_var (tree ref
, unsigned i
, bitmap tmp_vars
)
1470 tree type
= TREE_TYPE (ref
);
1471 tree var
= create_tmp_var (type
, get_lsm_tmp_name (ref
, i
));
1473 /* We never access the components of the temporary variable in predictive
1475 if (TREE_CODE (type
) == COMPLEX_TYPE
1476 || TREE_CODE (type
) == VECTOR_TYPE
)
1477 DECL_GIMPLE_REG_P (var
) = 1;
1479 add_referenced_var (var
);
1480 bitmap_set_bit (tmp_vars
, DECL_UID (var
));
1484 /* Creates the variables for CHAIN, as well as phi nodes for them and
1485 initialization on entry to LOOP. Uids of the newly created
1486 temporary variables are marked in TMP_VARS. */
1489 initialize_root_vars (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1492 unsigned n
= chain
->length
;
1493 dref root
= get_chain_root (chain
);
1494 bool reuse_first
= !chain
->has_max_use_after
;
1495 tree ref
, init
, var
, next
;
1498 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1500 /* If N == 0, then all the references are within the single iteration. And
1501 since this is an nonempty chain, reuse_first cannot be true. */
1502 gcc_assert (n
> 0 || !reuse_first
);
1504 chain
->vars
= VEC_alloc (tree
, heap
, n
+ 1);
1506 if (chain
->type
== CT_COMBINATION
)
1507 ref
= gimple_assign_lhs (root
->stmt
);
1509 ref
= DR_REF (root
->ref
);
1511 for (i
= 0; i
< n
+ (reuse_first
? 0 : 1); i
++)
1513 var
= predcom_tmp_var (ref
, i
, tmp_vars
);
1514 VEC_quick_push (tree
, chain
->vars
, var
);
1517 VEC_quick_push (tree
, chain
->vars
, VEC_index (tree
, chain
->vars
, 0));
1519 for (i
= 0; VEC_iterate (tree
, chain
->vars
, i
, var
); i
++)
1520 VEC_replace (tree
, chain
->vars
, i
, make_ssa_name (var
, NULL
));
1522 for (i
= 0; i
< n
; i
++)
1524 var
= VEC_index (tree
, chain
->vars
, i
);
1525 next
= VEC_index (tree
, chain
->vars
, i
+ 1);
1526 init
= get_init_expr (chain
, i
);
1528 init
= force_gimple_operand (init
, &stmts
, true, NULL_TREE
);
1531 mark_virtual_ops_for_renaming_list (stmts
);
1532 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1535 phi
= create_phi_node (var
, loop
->header
);
1536 SSA_NAME_DEF_STMT (var
) = phi
;
1537 add_phi_arg (phi
, init
, entry
);
1538 add_phi_arg (phi
, next
, latch
);
1542 /* Create the variables and initialization statement for root of chain
1543 CHAIN. Uids of the newly created temporary variables are marked
1547 initialize_root (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1549 dref root
= get_chain_root (chain
);
1550 bool in_lhs
= (chain
->type
== CT_STORE_LOAD
1551 || chain
->type
== CT_COMBINATION
);
1553 initialize_root_vars (loop
, chain
, tmp_vars
);
1554 replace_ref_with (root
->stmt
,
1555 VEC_index (tree
, chain
->vars
, chain
->length
),
1559 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1560 initialization on entry to LOOP if necessary. The ssa name for the variable
1561 is stored in VARS. If WRITTEN is true, also a phi node to copy its value
1562 around the loop is created. Uid of the newly created temporary variable
1563 is marked in TMP_VARS. INITS is the list containing the (single)
1567 initialize_root_vars_lm (struct loop
*loop
, dref root
, bool written
,
1568 VEC(tree
, heap
) **vars
, VEC(tree
, heap
) *inits
,
1572 tree ref
= DR_REF (root
->ref
), init
, var
, next
;
1575 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1577 /* Find the initializer for the variable, and check that it cannot
1579 init
= VEC_index (tree
, inits
, 0);
1581 *vars
= VEC_alloc (tree
, heap
, written
? 2 : 1);
1582 var
= predcom_tmp_var (ref
, 0, tmp_vars
);
1583 VEC_quick_push (tree
, *vars
, var
);
1585 VEC_quick_push (tree
, *vars
, VEC_index (tree
, *vars
, 0));
1587 for (i
= 0; VEC_iterate (tree
, *vars
, i
, var
); i
++)
1588 VEC_replace (tree
, *vars
, i
, make_ssa_name (var
, NULL
));
1590 var
= VEC_index (tree
, *vars
, 0);
1592 init
= force_gimple_operand (init
, &stmts
, written
, NULL_TREE
);
1595 mark_virtual_ops_for_renaming_list (stmts
);
1596 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1601 next
= VEC_index (tree
, *vars
, 1);
1602 phi
= create_phi_node (var
, loop
->header
);
1603 SSA_NAME_DEF_STMT (var
) = phi
;
1604 add_phi_arg (phi
, init
, entry
);
1605 add_phi_arg (phi
, next
, latch
);
1609 gimple init_stmt
= gimple_build_assign (var
, init
);
1610 mark_virtual_ops_for_renaming (init_stmt
);
1611 gsi_insert_on_edge_immediate (entry
, init_stmt
);
1616 /* Execute load motion for references in chain CHAIN. Uids of the newly
1617 created temporary variables are marked in TMP_VARS. */
1620 execute_load_motion (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1622 VEC (tree
, heap
) *vars
;
1624 unsigned n_writes
= 0, ridx
, i
;
1627 gcc_assert (chain
->type
== CT_INVARIANT
);
1628 gcc_assert (!chain
->combined
);
1629 for (i
= 0; VEC_iterate (dref
, chain
->refs
, i
, a
); i
++)
1630 if (!DR_IS_READ (a
->ref
))
1633 /* If there are no reads in the loop, there is nothing to do. */
1634 if (n_writes
== VEC_length (dref
, chain
->refs
))
1637 initialize_root_vars_lm (loop
, get_chain_root (chain
), n_writes
> 0,
1638 &vars
, chain
->inits
, tmp_vars
);
1641 for (i
= 0; VEC_iterate (dref
, chain
->refs
, i
, a
); i
++)
1643 bool is_read
= DR_IS_READ (a
->ref
);
1644 mark_virtual_ops_for_renaming (a
->stmt
);
1646 if (!DR_IS_READ (a
->ref
))
1651 var
= VEC_index (tree
, vars
, 0);
1652 var
= make_ssa_name (SSA_NAME_VAR (var
), NULL
);
1653 VEC_replace (tree
, vars
, 0, var
);
1659 replace_ref_with (a
->stmt
, VEC_index (tree
, vars
, ridx
),
1660 !is_read
, !is_read
);
1663 VEC_free (tree
, heap
, vars
);
1666 /* Returns the single statement in that NAME is used, excepting
1667 the looparound phi nodes contained in one of the chains. If there is no
1668 such statement, or more statements, NULL is returned. */
1671 single_nonlooparound_use (tree name
)
1674 imm_use_iterator it
;
1675 gimple stmt
, ret
= NULL
;
1677 FOR_EACH_IMM_USE_FAST (use
, it
, name
)
1679 stmt
= USE_STMT (use
);
1681 if (gimple_code (stmt
) == GIMPLE_PHI
)
1683 /* Ignore uses in looparound phi nodes. Uses in other phi nodes
1684 could not be processed anyway, so just fail for them. */
1685 if (bitmap_bit_p (looparound_phis
,
1686 SSA_NAME_VERSION (PHI_RESULT (stmt
))))
1691 else if (ret
!= NULL
)
1700 /* Remove statement STMT, as well as the chain of assignments in that it is
1704 remove_stmt (gimple stmt
)
1708 gimple_stmt_iterator psi
;
1710 if (gimple_code (stmt
) == GIMPLE_PHI
)
1712 name
= PHI_RESULT (stmt
);
1713 next
= single_nonlooparound_use (name
);
1714 psi
= gsi_for_stmt (stmt
);
1715 remove_phi_node (&psi
, true);
1718 || !gimple_assign_ssa_name_copy_p (next
)
1719 || gimple_assign_rhs1 (next
) != name
)
1727 gimple_stmt_iterator bsi
;
1729 bsi
= gsi_for_stmt (stmt
);
1731 name
= gimple_assign_lhs (stmt
);
1732 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1734 next
= single_nonlooparound_use (name
);
1736 mark_virtual_ops_for_renaming (stmt
);
1737 gsi_remove (&bsi
, true);
1738 release_defs (stmt
);
1741 || !gimple_assign_ssa_name_copy_p (next
)
1742 || gimple_assign_rhs1 (next
) != name
)
1749 /* Perform the predictive commoning optimization for a chain CHAIN.
1750 Uids of the newly created temporary variables are marked in TMP_VARS.*/
1753 execute_pred_commoning_chain (struct loop
*loop
, chain_p chain
,
1760 if (chain
->combined
)
1762 /* For combined chains, just remove the statements that are used to
1763 compute the values of the expression (except for the root one). */
1764 for (i
= 1; VEC_iterate (dref
, chain
->refs
, i
, a
); i
++)
1765 remove_stmt (a
->stmt
);
1769 /* For non-combined chains, set up the variables that hold its value,
1770 and replace the uses of the original references by these
1772 root
= get_chain_root (chain
);
1773 mark_virtual_ops_for_renaming (root
->stmt
);
1775 initialize_root (loop
, chain
, tmp_vars
);
1776 for (i
= 1; VEC_iterate (dref
, chain
->refs
, i
, a
); i
++)
1778 mark_virtual_ops_for_renaming (a
->stmt
);
1779 var
= VEC_index (tree
, chain
->vars
, chain
->length
- a
->distance
);
1780 replace_ref_with (a
->stmt
, var
, false, false);
1785 /* Determines the unroll factor necessary to remove as many temporary variable
1786 copies as possible. CHAINS is the list of chains that will be
1790 determine_unroll_factor (VEC (chain_p
, heap
) *chains
)
1793 unsigned factor
= 1, af
, nfactor
, i
;
1794 unsigned max
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
1796 for (i
= 0; VEC_iterate (chain_p
, chains
, i
, chain
); i
++)
1798 if (chain
->type
== CT_INVARIANT
|| chain
->combined
)
1801 /* The best unroll factor for this chain is equal to the number of
1802 temporary variables that we create for it. */
1804 if (chain
->has_max_use_after
)
1807 nfactor
= factor
* af
/ gcd (factor
, af
);
1815 /* Perform the predictive commoning optimization for CHAINS.
1816 Uids of the newly created temporary variables are marked in TMP_VARS. */
1819 execute_pred_commoning (struct loop
*loop
, VEC (chain_p
, heap
) *chains
,
1825 for (i
= 0; VEC_iterate (chain_p
, chains
, i
, chain
); i
++)
1827 if (chain
->type
== CT_INVARIANT
)
1828 execute_load_motion (loop
, chain
, tmp_vars
);
1830 execute_pred_commoning_chain (loop
, chain
, tmp_vars
);
1833 update_ssa (TODO_update_ssa_only_virtuals
);
1836 /* For each reference in CHAINS, if its defining statement is
1837 phi node, record the ssa name that is defined by it. */
1840 replace_phis_by_defined_names (VEC (chain_p
, heap
) *chains
)
1846 for (i
= 0; VEC_iterate (chain_p
, chains
, i
, chain
); i
++)
1847 for (j
= 0; VEC_iterate (dref
, chain
->refs
, j
, a
); j
++)
1849 if (gimple_code (a
->stmt
) == GIMPLE_PHI
)
1851 a
->name_defined_by_phi
= PHI_RESULT (a
->stmt
);
1857 /* For each reference in CHAINS, if name_defined_by_phi is not
1858 NULL, use it to set the stmt field. */
1861 replace_names_by_phis (VEC (chain_p
, heap
) *chains
)
1867 for (i
= 0; VEC_iterate (chain_p
, chains
, i
, chain
); i
++)
1868 for (j
= 0; VEC_iterate (dref
, chain
->refs
, j
, a
); j
++)
1869 if (a
->stmt
== NULL
)
1871 a
->stmt
= SSA_NAME_DEF_STMT (a
->name_defined_by_phi
);
1872 gcc_assert (gimple_code (a
->stmt
) == GIMPLE_PHI
);
1873 a
->name_defined_by_phi
= NULL_TREE
;
1877 /* Wrapper over execute_pred_commoning, to pass it as a callback
1878 to tree_transform_and_unroll_loop. */
1882 VEC (chain_p
, heap
) *chains
;
1887 execute_pred_commoning_cbck (struct loop
*loop
, void *data
)
1889 struct epcc_data
*const dta
= (struct epcc_data
*) data
;
1891 /* Restore phi nodes that were replaced by ssa names before
1892 tree_transform_and_unroll_loop (see detailed description in
1893 tree_predictive_commoning_loop). */
1894 replace_names_by_phis (dta
->chains
);
1895 execute_pred_commoning (loop
, dta
->chains
, dta
->tmp_vars
);
1898 /* Returns true if we can and should unroll LOOP FACTOR times. Number
1899 of iterations of the loop is returned in NITER. */
1902 should_unroll_loop_p (struct loop
*loop
, unsigned factor
,
1903 struct tree_niter_desc
*niter
)
1910 /* Check whether unrolling is possible. We only want to unroll loops
1911 for that we are able to determine number of iterations. We also
1912 want to split the extra iterations of the loop from its end,
1913 therefore we require that the loop has precisely one
1916 exit
= single_dom_exit (loop
);
1920 if (!number_of_iterations_exit (loop
, exit
, niter
, false))
1923 /* And of course, we must be able to duplicate the loop. */
1924 if (!can_duplicate_loop_p (loop
))
1927 /* The final loop should be small enough. */
1928 if (tree_num_loop_insns (loop
, &eni_size_weights
) * factor
1929 > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
))
1935 /* Base NAME and all the names in the chain of phi nodes that use it
1936 on variable VAR. The phi nodes are recognized by being in the copies of
1937 the header of the LOOP. */
1940 base_names_in_chain_on (struct loop
*loop
, tree name
, tree var
)
1943 imm_use_iterator iter
;
1946 SSA_NAME_VAR (name
) = var
;
1951 FOR_EACH_IMM_USE_STMT (stmt
, iter
, name
)
1953 if (gimple_code (stmt
) == GIMPLE_PHI
1954 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1957 BREAK_FROM_IMM_USE_STMT (iter
);
1963 if (gimple_bb (phi
) == loop
->header
)
1964 e
= loop_latch_edge (loop
);
1966 e
= single_pred_edge (gimple_bb (stmt
));
1968 name
= PHI_RESULT (phi
);
1969 SSA_NAME_VAR (name
) = var
;
1973 /* Given an unrolled LOOP after predictive commoning, remove the
1974 register copies arising from phi nodes by changing the base
1975 variables of SSA names. TMP_VARS is the set of the temporary variables
1976 for those we want to perform this. */
1979 eliminate_temp_copies (struct loop
*loop
, bitmap tmp_vars
)
1983 tree name
, use
, var
;
1984 gimple_stmt_iterator psi
;
1986 e
= loop_latch_edge (loop
);
1987 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1989 phi
= gsi_stmt (psi
);
1990 name
= PHI_RESULT (phi
);
1991 var
= SSA_NAME_VAR (name
);
1992 if (!bitmap_bit_p (tmp_vars
, DECL_UID (var
)))
1994 use
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1995 gcc_assert (TREE_CODE (use
) == SSA_NAME
);
1997 /* Base all the ssa names in the ud and du chain of NAME on VAR. */
1998 stmt
= SSA_NAME_DEF_STMT (use
);
1999 while (gimple_code (stmt
) == GIMPLE_PHI
2000 /* In case we could not unroll the loop enough to eliminate
2001 all copies, we may reach the loop header before the defining
2002 statement (in that case, some register copies will be present
2003 in loop latch in the final code, corresponding to the newly
2004 created looparound phi nodes). */
2005 && gimple_bb (stmt
) != loop
->header
)
2007 gcc_assert (single_pred_p (gimple_bb (stmt
)));
2008 use
= PHI_ARG_DEF (stmt
, 0);
2009 stmt
= SSA_NAME_DEF_STMT (use
);
2012 base_names_in_chain_on (loop
, use
, var
);
2016 /* Returns true if CHAIN is suitable to be combined. */
2019 chain_can_be_combined_p (chain_p chain
)
2021 return (!chain
->combined
2022 && (chain
->type
== CT_LOAD
|| chain
->type
== CT_COMBINATION
));
2025 /* Returns the modify statement that uses NAME. Skips over assignment
2026 statements, NAME is replaced with the actual name used in the returned
2030 find_use_stmt (tree
*name
)
2035 /* Skip over assignments. */
2038 stmt
= single_nonlooparound_use (*name
);
2042 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2045 lhs
= gimple_assign_lhs (stmt
);
2046 if (TREE_CODE (lhs
) != SSA_NAME
)
2049 if (gimple_assign_copy_p (stmt
))
2051 rhs
= gimple_assign_rhs1 (stmt
);
2057 else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
2058 == GIMPLE_BINARY_RHS
)
2065 /* Returns true if we may perform reassociation for operation CODE in TYPE. */
2068 may_reassociate_p (tree type
, enum tree_code code
)
2070 if (FLOAT_TYPE_P (type
)
2071 && !flag_unsafe_math_optimizations
)
2074 return (commutative_tree_code (code
)
2075 && associative_tree_code (code
));
2078 /* If the operation used in STMT is associative and commutative, go through the
2079 tree of the same operations and returns its root. Distance to the root
2080 is stored in DISTANCE. */
2083 find_associative_operation_root (gimple stmt
, unsigned *distance
)
2087 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2088 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2091 if (!may_reassociate_p (type
, code
))
2096 lhs
= gimple_assign_lhs (stmt
);
2097 gcc_assert (TREE_CODE (lhs
) == SSA_NAME
);
2099 next
= find_use_stmt (&lhs
);
2101 || gimple_assign_rhs_code (next
) != code
)
2113 /* Returns the common statement in that NAME1 and NAME2 have a use. If there
2114 is no such statement, returns NULL_TREE. In case the operation used on
2115 NAME1 and NAME2 is associative and commutative, returns the root of the
2116 tree formed by this operation instead of the statement that uses NAME1 or
2120 find_common_use_stmt (tree
*name1
, tree
*name2
)
2122 gimple stmt1
, stmt2
;
2124 stmt1
= find_use_stmt (name1
);
2128 stmt2
= find_use_stmt (name2
);
2135 stmt1
= find_associative_operation_root (stmt1
, NULL
);
2138 stmt2
= find_associative_operation_root (stmt2
, NULL
);
2142 return (stmt1
== stmt2
? stmt1
: NULL
);
2145 /* Checks whether R1 and R2 are combined together using CODE, with the result
2146 in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2147 if it is true. If CODE is ERROR_MARK, set these values instead. */
2150 combinable_refs_p (dref r1
, dref r2
,
2151 enum tree_code
*code
, bool *swap
, tree
*rslt_type
)
2153 enum tree_code acode
;
2159 name1
= name_for_ref (r1
);
2160 name2
= name_for_ref (r2
);
2161 gcc_assert (name1
!= NULL_TREE
&& name2
!= NULL_TREE
);
2163 stmt
= find_common_use_stmt (&name1
, &name2
);
2168 acode
= gimple_assign_rhs_code (stmt
);
2169 aswap
= (!commutative_tree_code (acode
)
2170 && gimple_assign_rhs1 (stmt
) != name1
);
2171 atype
= TREE_TYPE (gimple_assign_lhs (stmt
));
2173 if (*code
== ERROR_MARK
)
2181 return (*code
== acode
2183 && *rslt_type
== atype
);
2186 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2187 an assignment of the remaining operand. */
2190 remove_name_from_operation (gimple stmt
, tree op
)
2193 gimple_stmt_iterator si
;
2195 gcc_assert (is_gimple_assign (stmt
));
2197 if (gimple_assign_rhs1 (stmt
) == op
)
2198 other_op
= gimple_assign_rhs2 (stmt
);
2200 other_op
= gimple_assign_rhs1 (stmt
);
2202 si
= gsi_for_stmt (stmt
);
2203 gimple_assign_set_rhs_from_tree (&si
, other_op
);
2205 /* We should not have reallocated STMT. */
2206 gcc_assert (gsi_stmt (si
) == stmt
);
2211 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2212 are combined in a single statement, and returns this statement. */
2215 reassociate_to_the_same_stmt (tree name1
, tree name2
)
2217 gimple stmt1
, stmt2
, root1
, root2
, s1
, s2
;
2218 gimple new_stmt
, tmp_stmt
;
2219 tree new_name
, tmp_name
, var
, r1
, r2
;
2220 unsigned dist1
, dist2
;
2221 enum tree_code code
;
2222 tree type
= TREE_TYPE (name1
);
2223 gimple_stmt_iterator bsi
;
2225 stmt1
= find_use_stmt (&name1
);
2226 stmt2
= find_use_stmt (&name2
);
2227 root1
= find_associative_operation_root (stmt1
, &dist1
);
2228 root2
= find_associative_operation_root (stmt2
, &dist2
);
2229 code
= gimple_assign_rhs_code (stmt1
);
2231 gcc_assert (root1
&& root2
&& root1
== root2
2232 && code
== gimple_assign_rhs_code (stmt2
));
2234 /* Find the root of the nearest expression in that both NAME1 and NAME2
2241 while (dist1
> dist2
)
2243 s1
= find_use_stmt (&r1
);
2244 r1
= gimple_assign_lhs (s1
);
2247 while (dist2
> dist1
)
2249 s2
= find_use_stmt (&r2
);
2250 r2
= gimple_assign_lhs (s2
);
2256 s1
= find_use_stmt (&r1
);
2257 r1
= gimple_assign_lhs (s1
);
2258 s2
= find_use_stmt (&r2
);
2259 r2
= gimple_assign_lhs (s2
);
2262 /* Remove NAME1 and NAME2 from the statements in that they are used
2264 remove_name_from_operation (stmt1
, name1
);
2265 remove_name_from_operation (stmt2
, name2
);
2267 /* Insert the new statement combining NAME1 and NAME2 before S1, and
2268 combine it with the rhs of S1. */
2269 var
= create_tmp_var (type
, "predreastmp");
2270 add_referenced_var (var
);
2271 new_name
= make_ssa_name (var
, NULL
);
2272 new_stmt
= gimple_build_assign_with_ops (code
, new_name
, name1
, name2
);
2274 var
= create_tmp_var (type
, "predreastmp");
2275 add_referenced_var (var
);
2276 tmp_name
= make_ssa_name (var
, NULL
);
2278 /* Rhs of S1 may now be either a binary expression with operation
2279 CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2280 so that name1 or name2 was removed from it). */
2281 tmp_stmt
= gimple_build_assign_with_ops (gimple_assign_rhs_code (s1
),
2283 gimple_assign_rhs1 (s1
),
2284 gimple_assign_rhs2 (s1
));
2286 bsi
= gsi_for_stmt (s1
);
2287 gimple_assign_set_rhs_with_ops (&bsi
, code
, new_name
, tmp_name
);
2288 s1
= gsi_stmt (bsi
);
2291 gsi_insert_before (&bsi
, new_stmt
, GSI_SAME_STMT
);
2292 gsi_insert_before (&bsi
, tmp_stmt
, GSI_SAME_STMT
);
2297 /* Returns the statement that combines references R1 and R2. In case R1
2298 and R2 are not used in the same statement, but they are used with an
2299 associative and commutative operation in the same expression, reassociate
2300 the expression so that they are used in the same statement. */
2303 stmt_combining_refs (dref r1
, dref r2
)
2305 gimple stmt1
, stmt2
;
2306 tree name1
= name_for_ref (r1
);
2307 tree name2
= name_for_ref (r2
);
2309 stmt1
= find_use_stmt (&name1
);
2310 stmt2
= find_use_stmt (&name2
);
2314 return reassociate_to_the_same_stmt (name1
, name2
);
2317 /* Tries to combine chains CH1 and CH2 together. If this succeeds, the
2318 description of the new chain is returned, otherwise we return NULL. */
2321 combine_chains (chain_p ch1
, chain_p ch2
)
2324 enum tree_code op
= ERROR_MARK
;
2329 tree rslt_type
= NULL_TREE
;
2333 if (ch1
->length
!= ch2
->length
)
2336 if (VEC_length (dref
, ch1
->refs
) != VEC_length (dref
, ch2
->refs
))
2339 for (i
= 0; (VEC_iterate (dref
, ch1
->refs
, i
, r1
)
2340 && VEC_iterate (dref
, ch2
->refs
, i
, r2
)); i
++)
2342 if (r1
->distance
!= r2
->distance
)
2345 if (!combinable_refs_p (r1
, r2
, &op
, &swap
, &rslt_type
))
2356 new_chain
= XCNEW (struct chain
);
2357 new_chain
->type
= CT_COMBINATION
;
2359 new_chain
->ch1
= ch1
;
2360 new_chain
->ch2
= ch2
;
2361 new_chain
->rslt_type
= rslt_type
;
2362 new_chain
->length
= ch1
->length
;
2364 for (i
= 0; (VEC_iterate (dref
, ch1
->refs
, i
, r1
)
2365 && VEC_iterate (dref
, ch2
->refs
, i
, r2
)); i
++)
2367 nw
= XCNEW (struct dref
);
2368 nw
->stmt
= stmt_combining_refs (r1
, r2
);
2369 nw
->distance
= r1
->distance
;
2371 VEC_safe_push (dref
, heap
, new_chain
->refs
, nw
);
2374 new_chain
->has_max_use_after
= false;
2375 root_stmt
= get_chain_root (new_chain
)->stmt
;
2376 for (i
= 1; VEC_iterate (dref
, new_chain
->refs
, i
, nw
); i
++)
2378 if (nw
->distance
== new_chain
->length
2379 && !stmt_dominates_stmt_p (nw
->stmt
, root_stmt
))
2381 new_chain
->has_max_use_after
= true;
2386 ch1
->combined
= true;
2387 ch2
->combined
= true;
2391 /* Try to combine the CHAINS. */
2394 try_combine_chains (VEC (chain_p
, heap
) **chains
)
2397 chain_p ch1
, ch2
, cch
;
2398 VEC (chain_p
, heap
) *worklist
= NULL
;
2400 for (i
= 0; VEC_iterate (chain_p
, *chains
, i
, ch1
); i
++)
2401 if (chain_can_be_combined_p (ch1
))
2402 VEC_safe_push (chain_p
, heap
, worklist
, ch1
);
2404 while (!VEC_empty (chain_p
, worklist
))
2406 ch1
= VEC_pop (chain_p
, worklist
);
2407 if (!chain_can_be_combined_p (ch1
))
2410 for (j
= 0; VEC_iterate (chain_p
, *chains
, j
, ch2
); j
++)
2412 if (!chain_can_be_combined_p (ch2
))
2415 cch
= combine_chains (ch1
, ch2
);
2418 VEC_safe_push (chain_p
, heap
, worklist
, cch
);
2419 VEC_safe_push (chain_p
, heap
, *chains
, cch
);
2426 /* Sets alias information based on data reference DR for REF,
2430 set_alias_info (tree ref
, struct data_reference
*dr
)
2433 tree tag
= DR_SYMBOL_TAG (dr
);
2435 gcc_assert (tag
!= NULL_TREE
);
2437 ref
= get_base_address (ref
);
2438 if (!ref
|| !INDIRECT_REF_P (ref
))
2441 var
= SSA_NAME_VAR (TREE_OPERAND (ref
, 0));
2442 if (var_ann (var
)->symbol_mem_tag
)
2446 new_type_alias (var
, tag
, ref
);
2448 var_ann (var
)->symbol_mem_tag
= tag
;
2451 /* Prepare initializers for CHAIN in LOOP. Returns false if this is
2452 impossible because one of these initializers may trap, true otherwise. */
2455 prepare_initializers_chain (struct loop
*loop
, chain_p chain
)
2457 unsigned i
, n
= (chain
->type
== CT_INVARIANT
) ? 1 : chain
->length
;
2458 struct data_reference
*dr
= get_chain_root (chain
)->ref
;
2462 edge entry
= loop_preheader_edge (loop
);
2464 /* Find the initializers for the variables, and check that they cannot
2466 chain
->inits
= VEC_alloc (tree
, heap
, n
);
2467 for (i
= 0; i
< n
; i
++)
2468 VEC_quick_push (tree
, chain
->inits
, NULL_TREE
);
2470 /* If we have replaced some looparound phi nodes, use their initializers
2471 instead of creating our own. */
2472 for (i
= 0; VEC_iterate (dref
, chain
->refs
, i
, laref
); i
++)
2474 if (gimple_code (laref
->stmt
) != GIMPLE_PHI
)
2477 gcc_assert (laref
->distance
> 0);
2478 VEC_replace (tree
, chain
->inits
, n
- laref
->distance
,
2479 PHI_ARG_DEF_FROM_EDGE (laref
->stmt
, entry
));
2482 for (i
= 0; i
< n
; i
++)
2484 if (VEC_index (tree
, chain
->inits
, i
) != NULL_TREE
)
2487 init
= ref_at_iteration (loop
, DR_REF (dr
), (int) i
- n
);
2491 if (!chain
->all_always_accessed
&& tree_could_trap_p (init
))
2494 init
= force_gimple_operand (init
, &stmts
, false, NULL_TREE
);
2497 mark_virtual_ops_for_renaming_list (stmts
);
2498 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
2500 set_alias_info (init
, dr
);
2502 VEC_replace (tree
, chain
->inits
, i
, init
);
2508 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2509 be used because the initializers might trap. */
2512 prepare_initializers (struct loop
*loop
, VEC (chain_p
, heap
) *chains
)
2517 for (i
= 0; i
< VEC_length (chain_p
, chains
); )
2519 chain
= VEC_index (chain_p
, chains
, i
);
2520 if (prepare_initializers_chain (loop
, chain
))
2524 release_chain (chain
);
2525 VEC_unordered_remove (chain_p
, chains
, i
);
2530 /* Performs predictive commoning for LOOP. Returns true if LOOP was
2534 tree_predictive_commoning_loop (struct loop
*loop
)
2536 VEC (data_reference_p
, heap
) *datarefs
;
2537 VEC (ddr_p
, heap
) *dependences
;
2538 struct component
*components
;
2539 VEC (chain_p
, heap
) *chains
= NULL
;
2540 unsigned unroll_factor
;
2541 struct tree_niter_desc desc
;
2542 bool unroll
= false;
2546 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2547 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
2549 /* Find the data references and split them into components according to their
2550 dependence relations. */
2551 datarefs
= VEC_alloc (data_reference_p
, heap
, 10);
2552 dependences
= VEC_alloc (ddr_p
, heap
, 10);
2553 compute_data_dependences_for_loop (loop
, true, &datarefs
, &dependences
);
2554 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2555 dump_data_dependence_relations (dump_file
, dependences
);
2557 components
= split_data_refs_to_components (loop
, datarefs
, dependences
);
2558 free_dependence_relations (dependences
);
2561 free_data_refs (datarefs
);
2565 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2567 fprintf (dump_file
, "Initial state:\n\n");
2568 dump_components (dump_file
, components
);
2571 /* Find the suitable components and split them into chains. */
2572 components
= filter_suitable_components (loop
, components
);
2574 tmp_vars
= BITMAP_ALLOC (NULL
);
2575 looparound_phis
= BITMAP_ALLOC (NULL
);
2576 determine_roots (loop
, components
, &chains
);
2577 release_components (components
);
2581 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2583 "Predictive commoning failed: no suitable chains\n");
2586 prepare_initializers (loop
, chains
);
2588 /* Try to combine the chains that are always worked with together. */
2589 try_combine_chains (&chains
);
2591 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2593 fprintf (dump_file
, "Before commoning:\n\n");
2594 dump_chains (dump_file
, chains
);
2597 /* Determine the unroll factor, and if the loop should be unrolled, ensure
2598 that its number of iterations is divisible by the factor. */
2599 unroll_factor
= determine_unroll_factor (chains
);
2601 unroll
= should_unroll_loop_p (loop
, unroll_factor
, &desc
);
2602 exit
= single_dom_exit (loop
);
2604 /* Execute the predictive commoning transformations, and possibly unroll the
2608 struct epcc_data dta
;
2610 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2611 fprintf (dump_file
, "Unrolling %u times.\n", unroll_factor
);
2613 dta
.chains
= chains
;
2614 dta
.tmp_vars
= tmp_vars
;
2616 update_ssa (TODO_update_ssa_only_virtuals
);
2618 /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2619 execute_pred_commoning_cbck is called may cause phi nodes to be
2620 reallocated, which is a problem since CHAINS may point to these
2621 statements. To fix this, we store the ssa names defined by the
2622 phi nodes here instead of the phi nodes themselves, and restore
2623 the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
2624 replace_phis_by_defined_names (chains
);
2626 tree_transform_and_unroll_loop (loop
, unroll_factor
, exit
, &desc
,
2627 execute_pred_commoning_cbck
, &dta
);
2628 eliminate_temp_copies (loop
, tmp_vars
);
2632 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2634 "Executing predictive commoning without unrolling.\n");
2635 execute_pred_commoning (loop
, chains
, tmp_vars
);
2639 release_chains (chains
);
2640 free_data_refs (datarefs
);
2641 BITMAP_FREE (tmp_vars
);
2642 BITMAP_FREE (looparound_phis
);
2644 free_affine_expand_cache (&name_expansions
);
2649 /* Runs predictive commoning. */
2652 tree_predictive_commoning (void)
2654 bool unrolled
= false;
2659 initialize_original_copy_tables ();
2660 FOR_EACH_LOOP (li
, loop
, LI_ONLY_INNERMOST
)
2661 if (optimize_loop_for_speed_p (loop
))
2663 unrolled
|= tree_predictive_commoning_loop (loop
);
2669 ret
= TODO_cleanup_cfg
;
2671 free_original_copy_tables ();