1 /* Predictive commoning.
2 Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This file implements the predictive commoning optimization. Predictive
22 commoning can be viewed as CSE around a loop, and with some improvements,
23 as generalized strength reduction-- i.e., reusing values computed in
24 earlier iterations of a loop in the later ones. So far, the pass only
25 handles the most useful case, that is, reusing values of memory references.
26 If you think this is all just a special case of PRE, you are sort of right;
27 however, concentrating on loops is simpler, and makes it possible to
28 incorporate data dependence analysis to detect the opportunities, perform
29 loop unrolling to avoid copies together with renaming immediately,
30 and if needed, we could also take register pressure into account.
32 Let us demonstrate what is done on an example:
34 for (i = 0; i < 100; i++)
36 a[i+2] = a[i] + a[i+1];
42 1) We find data references in the loop, and split them to mutually
43 independent groups (i.e., we find components of a data dependence
44 graph). We ignore read-read dependences whose distance is not constant.
45 (TODO -- we could also ignore antidependences). In this example, we
46 find the following groups:
48 a[i]{read}, a[i+1]{read}, a[i+2]{write}
49 b[10]{read}, b[10]{write}
50 c[99 - i]{read}, c[i]{write}
51 d[i + 1]{read}, d[i]{write}
53 2) Inside each of the group, we verify several conditions:
54 a) all the references must differ in indices only, and the indices
55 must all have the same step
56 b) the references must dominate loop latch (and thus, they must be
57 ordered by dominance relation).
58 c) the distance of the indices must be a small multiple of the step
59 We are then able to compute the difference of the references (# of
60 iterations before they point to the same place as the first of them).
61 Also, in case there are writes in the loop, we split the groups into
62 chains whose head is the write whose values are used by the reads in
63 the same chain. The chains are then processed independently,
64 making the further transformations simpler. Also, the shorter chains
65 need the same number of registers, but may require lower unrolling
66 factor in order to get rid of the copies on the loop latch.
68 In our example, we get the following chains (the chain for c is invalid).
70 a[i]{read,+0}, a[i+1]{read,-1}, a[i+2]{write,-2}
71 b[10]{read,+0}, b[10]{write,+0}
72 d[i + 1]{read,+0}, d[i]{write,+1}
74 3) For each read, we determine the read or write whose value it reuses,
75 together with the distance of this reuse. I.e. we take the last
76 reference before it with distance 0, or the last of the references
77 with the smallest positive distance to the read. Then, we remove
78 the references that are not used in any of these chains, discard the
79 empty groups, and propagate all the links so that they point to the
80 single root reference of the chain (adjusting their distance
81 appropriately). Some extra care needs to be taken for references with
82 step 0. In our example (the numbers indicate the distance of the
85 a[i] --> (*) 2, a[i+1] --> (*) 1, a[i+2] (*)
86 b[10] --> (*) 1, b[10] (*)
88 4) The chains are combined together if possible. If the corresponding
89 elements of two chains are always combined together with the same
90 operator, we remember just the result of this combination, instead
91 of remembering the values separately. We may need to perform
92 reassociation to enable combining, for example
94 e[i] + f[i+1] + e[i+1] + f[i]
96 can be reassociated as
98 (e[i] + f[i]) + (e[i+1] + f[i+1])
100 and we can combine the chains for e and f into one chain.
102 5) For each root reference (end of the chain) R, let N be maximum distance
103 of a reference reusing its value. Variables R0 up to RN are created,
104 together with phi nodes that transfer values from R1 .. RN to
106 Initial values are loaded to R0..R(N-1) (in case not all references
107 must necessarily be accessed and they may trap, we may fail here;
108 TODO sometimes, the loads could be guarded by a check for the number
109 of iterations). Values loaded/stored in roots are also copied to
110 RN. Other reads are replaced with the appropriate variable Ri.
111 Everything is put to SSA form.
113 As a small improvement, if R0 is dead after the root (i.e., all uses of
114 the value with the maximum distance dominate the root), we can avoid
115 creating RN and use R0 instead of it.
117 In our example, we get (only the parts concerning a and b are shown):
118 for (i = 0; i < 100; i++)
130 6) Factor F for unrolling is determined as the smallest common multiple of
131 (N + 1) for each root reference (N for references for that we avoided
132 creating RN). If F and the loop is small enough, loop is unrolled F
133 times. The stores to RN (R0) in the copies of the loop body are
134 periodically replaced with R0, R1, ... (R1, R2, ...), so that they can
135 be coalesced and the copies can be eliminated.
137 TODO -- copy propagation and other optimizations may change the live
138 ranges of the temporary registers and prevent them from being coalesced;
139 this may increase the register pressure.
141 In our case, F = 2 and the (main loop of the) result is
143 for (i = 0; i < ...; i += 2)
160 TODO -- stores killing other stores can be taken into account, e.g.,
161 for (i = 0; i < n; i++)
171 for (i = 0; i < n; i++)
181 The interesting part is that this would generalize store motion; still, since
182 sm is performed elsewhere, it does not seem that important.
184 Predictive commoning can be generalized for arbitrary computations (not
185 just memory loads), and also nontrivial transfer functions (e.g., replacing
186 i * i with ii_last + 2 * i + 1), to generalize strength reduction. */
190 #include "coretypes.h"
195 #include "tree-flow.h"
197 #include "tree-data-ref.h"
198 #include "tree-scalar-evolution.h"
199 #include "tree-chrec.h"
201 #include "gimple-pretty-print.h"
202 #include "tree-pass.h"
203 #include "tree-affine.h"
204 #include "tree-inline.h"
206 /* The maximum number of iterations between the considered memory
209 #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
211 /* Data references (or phi nodes that carry data reference values across
214 typedef struct dref_d
216 /* The reference itself. */
217 struct data_reference
*ref
;
219 /* The statement in that the reference appears. */
222 /* In case that STMT is a phi node, this field is set to the SSA name
223 defined by it in replace_phis_by_defined_names (in order to avoid
224 pointing to phi node that got reallocated in the meantime). */
225 tree name_defined_by_phi
;
227 /* Distance of the reference from the root of the chain (in number of
228 iterations of the loop). */
231 /* Number of iterations offset from the first reference in the component. */
234 /* Number of the reference in a component, in dominance ordering. */
237 /* True if the memory reference is always accessed when the loop is
239 unsigned always_accessed
: 1;
243 DEF_VEC_ALLOC_P (dref
, heap
);
245 /* Type of the chain of the references. */
249 /* The addresses of the references in the chain are constant. */
252 /* There are only loads in the chain. */
255 /* Root of the chain is store, the rest are loads. */
258 /* A combination of two chains. */
262 /* Chains of data references. */
266 /* Type of the chain. */
267 enum chain_type type
;
269 /* For combination chains, the operator and the two chains that are
270 combined, and the type of the result. */
273 struct chain
*ch1
, *ch2
;
275 /* The references in the chain. */
276 VEC(dref
,heap
) *refs
;
278 /* The maximum distance of the reference in the chain from the root. */
281 /* The variables used to copy the value throughout iterations. */
282 VEC(tree
,heap
) *vars
;
284 /* Initializers for the variables. */
285 VEC(tree
,heap
) *inits
;
287 /* True if there is a use of a variable with the maximal distance
288 that comes after the root in the loop. */
289 unsigned has_max_use_after
: 1;
291 /* True if all the memory references in the chain are always accessed. */
292 unsigned all_always_accessed
: 1;
294 /* True if this chain was combined together with some other chain. */
295 unsigned combined
: 1;
299 DEF_VEC_ALLOC_P (chain_p
, heap
);
301 /* Describes the knowledge about the step of the memory references in
306 /* The step is zero. */
309 /* The step is nonzero. */
312 /* The step may or may not be nonzero. */
316 /* Components of the data dependence graph. */
320 /* The references in the component. */
321 VEC(dref
,heap
) *refs
;
323 /* What we know about the step of the references in the component. */
324 enum ref_step_type comp_step
;
326 /* Next component in the list. */
327 struct component
*next
;
330 /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */
332 static bitmap looparound_phis
;
334 /* Cache used by tree_to_aff_combination_expand. */
336 static struct pointer_map_t
*name_expansions
;
338 /* Dumps data reference REF to FILE. */
340 extern void dump_dref (FILE *, dref
);
342 dump_dref (FILE *file
, dref ref
)
347 print_generic_expr (file
, DR_REF (ref
->ref
), TDF_SLIM
);
348 fprintf (file
, " (id %u%s)\n", ref
->pos
,
349 DR_IS_READ (ref
->ref
) ? "" : ", write");
351 fprintf (file
, " offset ");
352 dump_double_int (file
, ref
->offset
, false);
353 fprintf (file
, "\n");
355 fprintf (file
, " distance %u\n", ref
->distance
);
359 if (gimple_code (ref
->stmt
) == GIMPLE_PHI
)
360 fprintf (file
, " looparound ref\n");
362 fprintf (file
, " combination ref\n");
363 fprintf (file
, " in statement ");
364 print_gimple_stmt (file
, ref
->stmt
, 0, TDF_SLIM
);
365 fprintf (file
, "\n");
366 fprintf (file
, " distance %u\n", ref
->distance
);
371 /* Dumps CHAIN to FILE. */
373 extern void dump_chain (FILE *, chain_p
);
375 dump_chain (FILE *file
, chain_p chain
)
378 const char *chain_type
;
385 chain_type
= "Load motion";
389 chain_type
= "Loads-only";
393 chain_type
= "Store-loads";
397 chain_type
= "Combination";
404 fprintf (file
, "%s chain %p%s\n", chain_type
, (void *) chain
,
405 chain
->combined
? " (combined)" : "");
406 if (chain
->type
!= CT_INVARIANT
)
407 fprintf (file
, " max distance %u%s\n", chain
->length
,
408 chain
->has_max_use_after
? "" : ", may reuse first");
410 if (chain
->type
== CT_COMBINATION
)
412 fprintf (file
, " equal to %p %s %p in type ",
413 (void *) chain
->ch1
, op_symbol_code (chain
->op
),
414 (void *) chain
->ch2
);
415 print_generic_expr (file
, chain
->rslt_type
, TDF_SLIM
);
416 fprintf (file
, "\n");
421 fprintf (file
, " vars");
422 FOR_EACH_VEC_ELT (tree
, chain
->vars
, i
, var
)
425 print_generic_expr (file
, var
, TDF_SLIM
);
427 fprintf (file
, "\n");
432 fprintf (file
, " inits");
433 FOR_EACH_VEC_ELT (tree
, chain
->inits
, i
, var
)
436 print_generic_expr (file
, var
, TDF_SLIM
);
438 fprintf (file
, "\n");
441 fprintf (file
, " references:\n");
442 FOR_EACH_VEC_ELT (dref
, chain
->refs
, i
, a
)
445 fprintf (file
, "\n");
448 /* Dumps CHAINS to FILE. */
450 extern void dump_chains (FILE *, VEC (chain_p
, heap
) *);
452 dump_chains (FILE *file
, VEC (chain_p
, heap
) *chains
)
457 FOR_EACH_VEC_ELT (chain_p
, chains
, i
, chain
)
458 dump_chain (file
, chain
);
461 /* Dumps COMP to FILE. */
463 extern void dump_component (FILE *, struct component
*);
465 dump_component (FILE *file
, struct component
*comp
)
470 fprintf (file
, "Component%s:\n",
471 comp
->comp_step
== RS_INVARIANT
? " (invariant)" : "");
472 FOR_EACH_VEC_ELT (dref
, comp
->refs
, i
, a
)
474 fprintf (file
, "\n");
477 /* Dumps COMPS to FILE. */
479 extern void dump_components (FILE *, struct component
*);
481 dump_components (FILE *file
, struct component
*comps
)
483 struct component
*comp
;
485 for (comp
= comps
; comp
; comp
= comp
->next
)
486 dump_component (file
, comp
);
489 /* Frees a chain CHAIN. */
492 release_chain (chain_p chain
)
500 FOR_EACH_VEC_ELT (dref
, chain
->refs
, i
, ref
)
503 VEC_free (dref
, heap
, chain
->refs
);
504 VEC_free (tree
, heap
, chain
->vars
);
505 VEC_free (tree
, heap
, chain
->inits
);
513 release_chains (VEC (chain_p
, heap
) *chains
)
518 FOR_EACH_VEC_ELT (chain_p
, chains
, i
, chain
)
519 release_chain (chain
);
520 VEC_free (chain_p
, heap
, chains
);
523 /* Frees a component COMP. */
526 release_component (struct component
*comp
)
528 VEC_free (dref
, heap
, comp
->refs
);
532 /* Frees list of components COMPS. */
535 release_components (struct component
*comps
)
537 struct component
*act
, *next
;
539 for (act
= comps
; act
; act
= next
)
542 release_component (act
);
546 /* Finds a root of tree given by FATHERS containing A, and performs path
550 component_of (unsigned fathers
[], unsigned a
)
554 for (root
= a
; root
!= fathers
[root
]; root
= fathers
[root
])
557 for (; a
!= root
; a
= n
)
566 /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the
567 components, A and B are components to merge. */
570 merge_comps (unsigned fathers
[], unsigned sizes
[], unsigned a
, unsigned b
)
572 unsigned ca
= component_of (fathers
, a
);
573 unsigned cb
= component_of (fathers
, b
);
578 if (sizes
[ca
] < sizes
[cb
])
580 sizes
[cb
] += sizes
[ca
];
585 sizes
[ca
] += sizes
[cb
];
590 /* Returns true if A is a reference that is suitable for predictive commoning
591 in the innermost loop that contains it. REF_STEP is set according to the
592 step of the reference A. */
595 suitable_reference_p (struct data_reference
*a
, enum ref_step_type
*ref_step
)
597 tree ref
= DR_REF (a
), step
= DR_STEP (a
);
600 || TREE_THIS_VOLATILE (ref
)
601 || !is_gimple_reg_type (TREE_TYPE (ref
))
602 || tree_could_throw_p (ref
))
605 if (integer_zerop (step
))
606 *ref_step
= RS_INVARIANT
;
607 else if (integer_nonzerop (step
))
608 *ref_step
= RS_NONZERO
;
615 /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
618 aff_combination_dr_offset (struct data_reference
*dr
, aff_tree
*offset
)
620 tree type
= TREE_TYPE (DR_OFFSET (dr
));
623 tree_to_aff_combination_expand (DR_OFFSET (dr
), type
, offset
,
625 aff_combination_const (&delta
, type
, tree_to_double_int (DR_INIT (dr
)));
626 aff_combination_add (offset
, &delta
);
629 /* Determines number of iterations of the innermost enclosing loop before B
630 refers to exactly the same location as A and stores it to OFF. If A and
631 B do not have the same step, they never meet, or anything else fails,
632 returns false, otherwise returns true. Both A and B are assumed to
633 satisfy suitable_reference_p. */
636 determine_offset (struct data_reference
*a
, struct data_reference
*b
,
639 aff_tree diff
, baseb
, step
;
642 /* Check that both the references access the location in the same type. */
643 typea
= TREE_TYPE (DR_REF (a
));
644 typeb
= TREE_TYPE (DR_REF (b
));
645 if (!useless_type_conversion_p (typeb
, typea
))
648 /* Check whether the base address and the step of both references is the
650 if (!operand_equal_p (DR_STEP (a
), DR_STEP (b
), 0)
651 || !operand_equal_p (DR_BASE_ADDRESS (a
), DR_BASE_ADDRESS (b
), 0))
654 if (integer_zerop (DR_STEP (a
)))
656 /* If the references have loop invariant address, check that they access
657 exactly the same location. */
658 *off
= double_int_zero
;
659 return (operand_equal_p (DR_OFFSET (a
), DR_OFFSET (b
), 0)
660 && operand_equal_p (DR_INIT (a
), DR_INIT (b
), 0));
663 /* Compare the offsets of the addresses, and check whether the difference
664 is a multiple of step. */
665 aff_combination_dr_offset (a
, &diff
);
666 aff_combination_dr_offset (b
, &baseb
);
667 aff_combination_scale (&baseb
, double_int_minus_one
);
668 aff_combination_add (&diff
, &baseb
);
670 tree_to_aff_combination_expand (DR_STEP (a
), TREE_TYPE (DR_STEP (a
)),
671 &step
, &name_expansions
);
672 return aff_combination_constant_multiple_p (&diff
, &step
, off
);
675 /* Returns the last basic block in LOOP for that we are sure that
676 it is executed whenever the loop is entered. */
679 last_always_executed_block (struct loop
*loop
)
682 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
684 basic_block last
= loop
->latch
;
686 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
687 last
= nearest_common_dominator (CDI_DOMINATORS
, last
, ex
->src
);
688 VEC_free (edge
, heap
, exits
);
693 /* Splits dependence graph on DATAREFS described by DEPENDS to components. */
695 static struct component
*
696 split_data_refs_to_components (struct loop
*loop
,
697 VEC (data_reference_p
, heap
) *datarefs
,
698 VEC (ddr_p
, heap
) *depends
)
700 unsigned i
, n
= VEC_length (data_reference_p
, datarefs
);
701 unsigned ca
, ia
, ib
, bad
;
702 unsigned *comp_father
= XNEWVEC (unsigned, n
+ 1);
703 unsigned *comp_size
= XNEWVEC (unsigned, n
+ 1);
704 struct component
**comps
;
705 struct data_reference
*dr
, *dra
, *drb
;
706 struct data_dependence_relation
*ddr
;
707 struct component
*comp_list
= NULL
, *comp
;
709 basic_block last_always_executed
= last_always_executed_block (loop
);
711 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
715 /* A fake reference for call or asm_expr that may clobber memory;
719 dr
->aux
= (void *) (size_t) i
;
724 /* A component reserved for the "bad" data references. */
728 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
730 enum ref_step_type dummy
;
732 if (!suitable_reference_p (dr
, &dummy
))
734 ia
= (unsigned) (size_t) dr
->aux
;
735 merge_comps (comp_father
, comp_size
, n
, ia
);
739 FOR_EACH_VEC_ELT (ddr_p
, depends
, i
, ddr
)
741 double_int dummy_off
;
743 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
748 ia
= component_of (comp_father
, (unsigned) (size_t) dra
->aux
);
749 ib
= component_of (comp_father
, (unsigned) (size_t) drb
->aux
);
753 bad
= component_of (comp_father
, n
);
755 /* If both A and B are reads, we may ignore unsuitable dependences. */
756 if (DR_IS_READ (dra
) && DR_IS_READ (drb
)
757 && (ia
== bad
|| ib
== bad
758 || !determine_offset (dra
, drb
, &dummy_off
)))
761 merge_comps (comp_father
, comp_size
, ia
, ib
);
764 comps
= XCNEWVEC (struct component
*, n
);
765 bad
= component_of (comp_father
, n
);
766 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
768 ia
= (unsigned) (size_t) dr
->aux
;
769 ca
= component_of (comp_father
, ia
);
776 comp
= XCNEW (struct component
);
777 comp
->refs
= VEC_alloc (dref
, heap
, comp_size
[ca
]);
781 dataref
= XCNEW (struct dref_d
);
783 dataref
->stmt
= DR_STMT (dr
);
784 dataref
->offset
= double_int_zero
;
785 dataref
->distance
= 0;
787 dataref
->always_accessed
788 = dominated_by_p (CDI_DOMINATORS
, last_always_executed
,
789 gimple_bb (dataref
->stmt
));
790 dataref
->pos
= VEC_length (dref
, comp
->refs
);
791 VEC_quick_push (dref
, comp
->refs
, dataref
);
794 for (i
= 0; i
< n
; i
++)
799 comp
->next
= comp_list
;
811 /* Returns true if the component COMP satisfies the conditions
812 described in 2) at the beginning of this file. LOOP is the current
816 suitable_component_p (struct loop
*loop
, struct component
*comp
)
820 basic_block ba
, bp
= loop
->header
;
821 bool ok
, has_write
= false;
823 FOR_EACH_VEC_ELT (dref
, comp
->refs
, i
, a
)
825 ba
= gimple_bb (a
->stmt
);
827 if (!just_once_each_iteration_p (loop
, ba
))
830 gcc_assert (dominated_by_p (CDI_DOMINATORS
, ba
, bp
));
833 if (DR_IS_WRITE (a
->ref
))
837 first
= VEC_index (dref
, comp
->refs
, 0);
838 ok
= suitable_reference_p (first
->ref
, &comp
->comp_step
);
840 first
->offset
= double_int_zero
;
842 for (i
= 1; VEC_iterate (dref
, comp
->refs
, i
, a
); i
++)
844 if (!determine_offset (first
->ref
, a
->ref
, &a
->offset
))
847 #ifdef ENABLE_CHECKING
849 enum ref_step_type a_step
;
850 ok
= suitable_reference_p (a
->ref
, &a_step
);
851 gcc_assert (ok
&& a_step
== comp
->comp_step
);
856 /* If there is a write inside the component, we must know whether the
857 step is nonzero or not -- we would not otherwise be able to recognize
858 whether the value accessed by reads comes from the OFFSET-th iteration
859 or the previous one. */
860 if (has_write
&& comp
->comp_step
== RS_ANY
)
866 /* Check the conditions on references inside each of components COMPS,
867 and remove the unsuitable components from the list. The new list
868 of components is returned. The conditions are described in 2) at
869 the beginning of this file. LOOP is the current loop. */
871 static struct component
*
872 filter_suitable_components (struct loop
*loop
, struct component
*comps
)
874 struct component
**comp
, *act
;
876 for (comp
= &comps
; *comp
; )
879 if (suitable_component_p (loop
, act
))
887 FOR_EACH_VEC_ELT (dref
, act
->refs
, i
, ref
)
889 release_component (act
);
896 /* Compares two drefs A and B by their offset and position. Callback for
900 order_drefs (const void *a
, const void *b
)
902 const dref
*const da
= (const dref
*) a
;
903 const dref
*const db
= (const dref
*) b
;
904 int offcmp
= double_int_scmp ((*da
)->offset
, (*db
)->offset
);
909 return (*da
)->pos
- (*db
)->pos
;
912 /* Returns root of the CHAIN. */
915 get_chain_root (chain_p chain
)
917 return VEC_index (dref
, chain
->refs
, 0);
920 /* Adds REF to the chain CHAIN. */
923 add_ref_to_chain (chain_p chain
, dref ref
)
925 dref root
= get_chain_root (chain
);
928 gcc_assert (double_int_scmp (root
->offset
, ref
->offset
) <= 0);
929 dist
= double_int_sub (ref
->offset
, root
->offset
);
930 if (double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE
), dist
) <= 0)
935 gcc_assert (double_int_fits_in_uhwi_p (dist
));
937 VEC_safe_push (dref
, heap
, chain
->refs
, ref
);
939 ref
->distance
= double_int_to_uhwi (dist
);
941 if (ref
->distance
>= chain
->length
)
943 chain
->length
= ref
->distance
;
944 chain
->has_max_use_after
= false;
947 if (ref
->distance
== chain
->length
948 && ref
->pos
> root
->pos
)
949 chain
->has_max_use_after
= true;
951 chain
->all_always_accessed
&= ref
->always_accessed
;
954 /* Returns the chain for invariant component COMP. */
957 make_invariant_chain (struct component
*comp
)
959 chain_p chain
= XCNEW (struct chain
);
963 chain
->type
= CT_INVARIANT
;
965 chain
->all_always_accessed
= true;
967 FOR_EACH_VEC_ELT (dref
, comp
->refs
, i
, ref
)
969 VEC_safe_push (dref
, heap
, chain
->refs
, ref
);
970 chain
->all_always_accessed
&= ref
->always_accessed
;
976 /* Make a new chain rooted at REF. */
979 make_rooted_chain (dref ref
)
981 chain_p chain
= XCNEW (struct chain
);
983 chain
->type
= DR_IS_READ (ref
->ref
) ? CT_LOAD
: CT_STORE_LOAD
;
985 VEC_safe_push (dref
, heap
, chain
->refs
, ref
);
986 chain
->all_always_accessed
= ref
->always_accessed
;
993 /* Returns true if CHAIN is not trivial. */
996 nontrivial_chain_p (chain_p chain
)
998 return chain
!= NULL
&& VEC_length (dref
, chain
->refs
) > 1;
1001 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1005 name_for_ref (dref ref
)
1009 if (is_gimple_assign (ref
->stmt
))
1011 if (!ref
->ref
|| DR_IS_READ (ref
->ref
))
1012 name
= gimple_assign_lhs (ref
->stmt
);
1014 name
= gimple_assign_rhs1 (ref
->stmt
);
1017 name
= PHI_RESULT (ref
->stmt
);
1019 return (TREE_CODE (name
) == SSA_NAME
? name
: NULL_TREE
);
1022 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1023 iterations of the innermost enclosing loop). */
1026 valid_initializer_p (struct data_reference
*ref
,
1027 unsigned distance
, struct data_reference
*root
)
1029 aff_tree diff
, base
, step
;
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
), TREE_TYPE (DR_STEP (root
)),
1054 &step
, &name_expansions
);
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 if (!dr_analyze_innermost (&init_dr
, loop
))
1121 if (!valid_initializer_p (&init_dr
, ref
->distance
+ 1, root
->ref
))
1127 /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1130 insert_looparound_copy (chain_p chain
, dref ref
, gimple phi
)
1132 dref nw
= XCNEW (struct dref_d
), aref
;
1136 nw
->distance
= ref
->distance
+ 1;
1137 nw
->always_accessed
= 1;
1139 FOR_EACH_VEC_ELT (dref
, chain
->refs
, i
, aref
)
1140 if (aref
->distance
>= nw
->distance
)
1142 VEC_safe_insert (dref
, heap
, chain
->refs
, i
, nw
);
1144 if (nw
->distance
> chain
->length
)
1146 chain
->length
= nw
->distance
;
1147 chain
->has_max_use_after
= false;
1151 /* For references in CHAIN that are copied around the LOOP (created previously
1152 by PRE, or by user), add the results of such copies to the chain. This
1153 enables us to remove the copies by unrolling, and may need less registers
1154 (also, it may allow us to combine chains together). */
1157 add_looparound_copies (struct loop
*loop
, chain_p chain
)
1160 dref ref
, root
= get_chain_root (chain
);
1163 FOR_EACH_VEC_ELT (dref
, chain
->refs
, i
, ref
)
1165 phi
= find_looparound_phi (loop
, ref
, root
);
1169 bitmap_set_bit (looparound_phis
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
1170 insert_looparound_copy (chain
, ref
, phi
);
1174 /* Find roots of the values and determine distances in the component COMP.
1175 The references are redistributed into CHAINS. LOOP is the current
1179 determine_roots_comp (struct loop
*loop
,
1180 struct component
*comp
,
1181 VEC (chain_p
, heap
) **chains
)
1185 chain_p chain
= NULL
;
1186 double_int last_ofs
= double_int_zero
;
1188 /* Invariants are handled specially. */
1189 if (comp
->comp_step
== RS_INVARIANT
)
1191 chain
= make_invariant_chain (comp
);
1192 VEC_safe_push (chain_p
, heap
, *chains
, chain
);
1196 VEC_qsort (dref
, comp
->refs
, order_drefs
);
1198 FOR_EACH_VEC_ELT (dref
, comp
->refs
, i
, a
)
1200 if (!chain
|| DR_IS_WRITE (a
->ref
)
1201 || double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE
),
1202 double_int_sub (a
->offset
, last_ofs
)) <= 0)
1204 if (nontrivial_chain_p (chain
))
1206 add_looparound_copies (loop
, chain
);
1207 VEC_safe_push (chain_p
, heap
, *chains
, chain
);
1210 release_chain (chain
);
1211 chain
= make_rooted_chain (a
);
1212 last_ofs
= a
->offset
;
1216 add_ref_to_chain (chain
, a
);
1219 if (nontrivial_chain_p (chain
))
1221 add_looparound_copies (loop
, chain
);
1222 VEC_safe_push (chain_p
, heap
, *chains
, chain
);
1225 release_chain (chain
);
1228 /* Find roots of the values and determine distances in components COMPS, and
1229 separates the references to CHAINS. LOOP is the current loop. */
1232 determine_roots (struct loop
*loop
,
1233 struct component
*comps
, VEC (chain_p
, heap
) **chains
)
1235 struct component
*comp
;
1237 for (comp
= comps
; comp
; comp
= comp
->next
)
1238 determine_roots_comp (loop
, comp
, chains
);
1241 /* Replace the reference in statement STMT with temporary variable
1242 NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of
1243 the reference in the statement. IN_LHS is true if the reference
1244 is in the lhs of STMT, false if it is in rhs. */
1247 replace_ref_with (gimple stmt
, tree new_tree
, bool set
, bool in_lhs
)
1251 gimple_stmt_iterator bsi
, psi
;
1253 if (gimple_code (stmt
) == GIMPLE_PHI
)
1255 gcc_assert (!in_lhs
&& !set
);
1257 val
= PHI_RESULT (stmt
);
1258 bsi
= gsi_after_labels (gimple_bb (stmt
));
1259 psi
= gsi_for_stmt (stmt
);
1260 remove_phi_node (&psi
, false);
1262 /* Turn the phi node into GIMPLE_ASSIGN. */
1263 new_stmt
= gimple_build_assign (val
, new_tree
);
1264 gsi_insert_before (&bsi
, new_stmt
, GSI_NEW_STMT
);
1268 /* Since the reference is of gimple_reg type, it should only
1269 appear as lhs or rhs of modify statement. */
1270 gcc_assert (is_gimple_assign (stmt
));
1272 bsi
= gsi_for_stmt (stmt
);
1274 /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */
1277 gcc_assert (!in_lhs
);
1278 gimple_assign_set_rhs_from_tree (&bsi
, new_tree
);
1279 stmt
= gsi_stmt (bsi
);
1286 /* We have statement
1290 If OLD is a memory reference, then VAL is gimple_val, and we transform
1296 Otherwise, we are replacing a combination chain,
1297 VAL is the expression that performs the combination, and OLD is an
1298 SSA name. In this case, we transform the assignment to
1305 val
= gimple_assign_lhs (stmt
);
1306 if (TREE_CODE (val
) != SSA_NAME
)
1308 val
= gimple_assign_rhs1 (stmt
);
1309 gcc_assert (gimple_assign_single_p (stmt
));
1310 if (TREE_CLOBBER_P (val
))
1312 val
= gimple_default_def (cfun
, SSA_NAME_VAR (new_tree
));
1313 if (val
== NULL_TREE
)
1315 val
= make_ssa_name (SSA_NAME_VAR (new_tree
),
1316 gimple_build_nop ());
1317 set_default_def (SSA_NAME_VAR (new_tree
), val
);
1321 gcc_assert (gimple_assign_copy_p (stmt
));
1333 val
= gimple_assign_lhs (stmt
);
1336 new_stmt
= gimple_build_assign (new_tree
, unshare_expr (val
));
1337 gsi_insert_after (&bsi
, new_stmt
, GSI_NEW_STMT
);
1340 /* Returns the reference to the address of REF in the ITER-th iteration of
1341 LOOP, or NULL if we fail to determine it (ITER may be negative). We
1342 try to preserve the original shape of the reference (not rewrite it
1343 as an indirect ref to the address), to make tree_could_trap_p in
1344 prepare_initializers_chain return false more often. */
1347 ref_at_iteration (struct loop
*loop
, tree ref
, int iter
)
1349 tree idx
, *idx_p
, type
, val
, op0
= NULL_TREE
, ret
;
1353 if (handled_component_p (ref
))
1355 op0
= ref_at_iteration (loop
, TREE_OPERAND (ref
, 0), iter
);
1359 else if (!INDIRECT_REF_P (ref
)
1360 && TREE_CODE (ref
) != MEM_REF
)
1361 return unshare_expr (ref
);
1363 if (TREE_CODE (ref
) == MEM_REF
)
1365 ret
= unshare_expr (ref
);
1366 idx
= TREE_OPERAND (ref
, 0);
1367 idx_p
= &TREE_OPERAND (ret
, 0);
1369 else if (TREE_CODE (ref
) == COMPONENT_REF
)
1371 /* Check that the offset is loop invariant. */
1372 if (TREE_OPERAND (ref
, 2)
1373 && !expr_invariant_in_loop_p (loop
, TREE_OPERAND (ref
, 2)))
1376 return build3 (COMPONENT_REF
, TREE_TYPE (ref
), op0
,
1377 unshare_expr (TREE_OPERAND (ref
, 1)),
1378 unshare_expr (TREE_OPERAND (ref
, 2)));
1380 else if (TREE_CODE (ref
) == ARRAY_REF
)
1382 /* Check that the lower bound and the step are loop invariant. */
1383 if (TREE_OPERAND (ref
, 2)
1384 && !expr_invariant_in_loop_p (loop
, TREE_OPERAND (ref
, 2)))
1386 if (TREE_OPERAND (ref
, 3)
1387 && !expr_invariant_in_loop_p (loop
, TREE_OPERAND (ref
, 3)))
1390 ret
= build4 (ARRAY_REF
, TREE_TYPE (ref
), op0
, NULL_TREE
,
1391 unshare_expr (TREE_OPERAND (ref
, 2)),
1392 unshare_expr (TREE_OPERAND (ref
, 3)));
1393 idx
= TREE_OPERAND (ref
, 1);
1394 idx_p
= &TREE_OPERAND (ret
, 1);
1399 ok
= simple_iv (loop
, loop
, idx
, &iv
, true);
1402 iv
.base
= expand_simple_operations (iv
.base
);
1403 if (integer_zerop (iv
.step
))
1404 *idx_p
= unshare_expr (iv
.base
);
1407 type
= TREE_TYPE (iv
.base
);
1408 if (POINTER_TYPE_P (type
))
1410 val
= fold_build2 (MULT_EXPR
, sizetype
, iv
.step
,
1412 val
= fold_build_pointer_plus (iv
.base
, val
);
1416 val
= fold_build2 (MULT_EXPR
, type
, iv
.step
,
1417 build_int_cst_type (type
, iter
));
1418 val
= fold_build2 (PLUS_EXPR
, type
, iv
.base
, val
);
1420 *idx_p
= unshare_expr (val
);
1426 /* Get the initialization expression for the INDEX-th temporary variable
1430 get_init_expr (chain_p chain
, unsigned index
)
1432 if (chain
->type
== CT_COMBINATION
)
1434 tree e1
= get_init_expr (chain
->ch1
, index
);
1435 tree e2
= get_init_expr (chain
->ch2
, index
);
1437 return fold_build2 (chain
->op
, chain
->rslt_type
, e1
, e2
);
1440 return VEC_index (tree
, chain
->inits
, index
);
1443 /* Returns a new temporary variable used for the I-th variable carrying
1444 value of REF. The variable's uid is marked in TMP_VARS. */
1447 predcom_tmp_var (tree ref
, unsigned i
, bitmap tmp_vars
)
1449 tree type
= TREE_TYPE (ref
);
1450 /* We never access the components of the temporary variable in predictive
1452 tree var
= create_tmp_reg (type
, get_lsm_tmp_name (ref
, i
));
1454 add_referenced_var (var
);
1455 bitmap_set_bit (tmp_vars
, DECL_UID (var
));
1459 /* Creates the variables for CHAIN, as well as phi nodes for them and
1460 initialization on entry to LOOP. Uids of the newly created
1461 temporary variables are marked in TMP_VARS. */
1464 initialize_root_vars (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1467 unsigned n
= chain
->length
;
1468 dref root
= get_chain_root (chain
);
1469 bool reuse_first
= !chain
->has_max_use_after
;
1470 tree ref
, init
, var
, next
;
1473 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1475 /* If N == 0, then all the references are within the single iteration. And
1476 since this is an nonempty chain, reuse_first cannot be true. */
1477 gcc_assert (n
> 0 || !reuse_first
);
1479 chain
->vars
= VEC_alloc (tree
, heap
, n
+ 1);
1481 if (chain
->type
== CT_COMBINATION
)
1482 ref
= gimple_assign_lhs (root
->stmt
);
1484 ref
= DR_REF (root
->ref
);
1486 for (i
= 0; i
< n
+ (reuse_first
? 0 : 1); i
++)
1488 var
= predcom_tmp_var (ref
, i
, tmp_vars
);
1489 VEC_quick_push (tree
, chain
->vars
, var
);
1492 VEC_quick_push (tree
, chain
->vars
, VEC_index (tree
, chain
->vars
, 0));
1494 FOR_EACH_VEC_ELT (tree
, chain
->vars
, i
, var
)
1495 VEC_replace (tree
, chain
->vars
, i
, make_ssa_name (var
, NULL
));
1497 for (i
= 0; i
< n
; i
++)
1499 var
= VEC_index (tree
, chain
->vars
, i
);
1500 next
= VEC_index (tree
, chain
->vars
, i
+ 1);
1501 init
= get_init_expr (chain
, i
);
1503 init
= force_gimple_operand (init
, &stmts
, true, NULL_TREE
);
1505 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1507 phi
= create_phi_node (var
, loop
->header
);
1508 SSA_NAME_DEF_STMT (var
) = phi
;
1509 add_phi_arg (phi
, init
, entry
, UNKNOWN_LOCATION
);
1510 add_phi_arg (phi
, next
, latch
, UNKNOWN_LOCATION
);
1514 /* Create the variables and initialization statement for root of chain
1515 CHAIN. Uids of the newly created temporary variables are marked
1519 initialize_root (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1521 dref root
= get_chain_root (chain
);
1522 bool in_lhs
= (chain
->type
== CT_STORE_LOAD
1523 || chain
->type
== CT_COMBINATION
);
1525 initialize_root_vars (loop
, chain
, tmp_vars
);
1526 replace_ref_with (root
->stmt
,
1527 VEC_index (tree
, chain
->vars
, chain
->length
),
1531 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1532 initialization on entry to LOOP if necessary. The ssa name for the variable
1533 is stored in VARS. If WRITTEN is true, also a phi node to copy its value
1534 around the loop is created. Uid of the newly created temporary variable
1535 is marked in TMP_VARS. INITS is the list containing the (single)
1539 initialize_root_vars_lm (struct loop
*loop
, dref root
, bool written
,
1540 VEC(tree
, heap
) **vars
, VEC(tree
, heap
) *inits
,
1544 tree ref
= DR_REF (root
->ref
), init
, var
, next
;
1547 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1549 /* Find the initializer for the variable, and check that it cannot
1551 init
= VEC_index (tree
, inits
, 0);
1553 *vars
= VEC_alloc (tree
, heap
, written
? 2 : 1);
1554 var
= predcom_tmp_var (ref
, 0, tmp_vars
);
1555 VEC_quick_push (tree
, *vars
, var
);
1557 VEC_quick_push (tree
, *vars
, VEC_index (tree
, *vars
, 0));
1559 FOR_EACH_VEC_ELT (tree
, *vars
, i
, var
)
1560 VEC_replace (tree
, *vars
, i
, make_ssa_name (var
, NULL
));
1562 var
= VEC_index (tree
, *vars
, 0);
1564 init
= force_gimple_operand (init
, &stmts
, written
, NULL_TREE
);
1566 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1570 next
= VEC_index (tree
, *vars
, 1);
1571 phi
= create_phi_node (var
, loop
->header
);
1572 SSA_NAME_DEF_STMT (var
) = phi
;
1573 add_phi_arg (phi
, init
, entry
, UNKNOWN_LOCATION
);
1574 add_phi_arg (phi
, next
, latch
, UNKNOWN_LOCATION
);
1578 gimple init_stmt
= gimple_build_assign (var
, init
);
1579 gsi_insert_on_edge_immediate (entry
, init_stmt
);
1584 /* Execute load motion for references in chain CHAIN. Uids of the newly
1585 created temporary variables are marked in TMP_VARS. */
1588 execute_load_motion (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1590 VEC (tree
, heap
) *vars
;
1592 unsigned n_writes
= 0, ridx
, i
;
1595 gcc_assert (chain
->type
== CT_INVARIANT
);
1596 gcc_assert (!chain
->combined
);
1597 FOR_EACH_VEC_ELT (dref
, chain
->refs
, i
, a
)
1598 if (DR_IS_WRITE (a
->ref
))
1601 /* If there are no reads in the loop, there is nothing to do. */
1602 if (n_writes
== VEC_length (dref
, chain
->refs
))
1605 initialize_root_vars_lm (loop
, get_chain_root (chain
), n_writes
> 0,
1606 &vars
, chain
->inits
, tmp_vars
);
1609 FOR_EACH_VEC_ELT (dref
, chain
->refs
, i
, a
)
1611 bool is_read
= DR_IS_READ (a
->ref
);
1613 if (DR_IS_WRITE (a
->ref
))
1618 var
= VEC_index (tree
, vars
, 0);
1619 var
= make_ssa_name (SSA_NAME_VAR (var
), NULL
);
1620 VEC_replace (tree
, vars
, 0, var
);
1626 replace_ref_with (a
->stmt
, VEC_index (tree
, vars
, ridx
),
1627 !is_read
, !is_read
);
1630 VEC_free (tree
, heap
, vars
);
1633 /* Returns the single statement in that NAME is used, excepting
1634 the looparound phi nodes contained in one of the chains. If there is no
1635 such statement, or more statements, NULL is returned. */
1638 single_nonlooparound_use (tree name
)
1641 imm_use_iterator it
;
1642 gimple stmt
, ret
= NULL
;
1644 FOR_EACH_IMM_USE_FAST (use
, it
, name
)
1646 stmt
= USE_STMT (use
);
1648 if (gimple_code (stmt
) == GIMPLE_PHI
)
1650 /* Ignore uses in looparound phi nodes. Uses in other phi nodes
1651 could not be processed anyway, so just fail for them. */
1652 if (bitmap_bit_p (looparound_phis
,
1653 SSA_NAME_VERSION (PHI_RESULT (stmt
))))
1658 else if (is_gimple_debug (stmt
))
1660 else if (ret
!= NULL
)
1669 /* Remove statement STMT, as well as the chain of assignments in that it is
1673 remove_stmt (gimple stmt
)
1677 gimple_stmt_iterator psi
;
1679 if (gimple_code (stmt
) == GIMPLE_PHI
)
1681 name
= PHI_RESULT (stmt
);
1682 next
= single_nonlooparound_use (name
);
1683 reset_debug_uses (stmt
);
1684 psi
= gsi_for_stmt (stmt
);
1685 remove_phi_node (&psi
, true);
1688 || !gimple_assign_ssa_name_copy_p (next
)
1689 || gimple_assign_rhs1 (next
) != name
)
1697 gimple_stmt_iterator bsi
;
1699 bsi
= gsi_for_stmt (stmt
);
1701 name
= gimple_assign_lhs (stmt
);
1702 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1704 next
= single_nonlooparound_use (name
);
1705 reset_debug_uses (stmt
);
1707 unlink_stmt_vdef (stmt
);
1708 gsi_remove (&bsi
, true);
1709 release_defs (stmt
);
1712 || !gimple_assign_ssa_name_copy_p (next
)
1713 || gimple_assign_rhs1 (next
) != name
)
1720 /* Perform the predictive commoning optimization for a chain CHAIN.
1721 Uids of the newly created temporary variables are marked in TMP_VARS.*/
1724 execute_pred_commoning_chain (struct loop
*loop
, chain_p chain
,
1731 if (chain
->combined
)
1733 /* For combined chains, just remove the statements that are used to
1734 compute the values of the expression (except for the root one). */
1735 for (i
= 1; VEC_iterate (dref
, chain
->refs
, i
, a
); i
++)
1736 remove_stmt (a
->stmt
);
1740 /* For non-combined chains, set up the variables that hold its value,
1741 and replace the uses of the original references by these
1743 initialize_root (loop
, chain
, tmp_vars
);
1744 for (i
= 1; VEC_iterate (dref
, chain
->refs
, i
, a
); i
++)
1746 var
= VEC_index (tree
, chain
->vars
, chain
->length
- a
->distance
);
1747 replace_ref_with (a
->stmt
, var
, false, false);
1752 /* Determines the unroll factor necessary to remove as many temporary variable
1753 copies as possible. CHAINS is the list of chains that will be
1757 determine_unroll_factor (VEC (chain_p
, heap
) *chains
)
1760 unsigned factor
= 1, af
, nfactor
, i
;
1761 unsigned max
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
1763 FOR_EACH_VEC_ELT (chain_p
, chains
, i
, chain
)
1765 if (chain
->type
== CT_INVARIANT
|| chain
->combined
)
1768 /* The best unroll factor for this chain is equal to the number of
1769 temporary variables that we create for it. */
1771 if (chain
->has_max_use_after
)
1774 nfactor
= factor
* af
/ gcd (factor
, af
);
1782 /* Perform the predictive commoning optimization for CHAINS.
1783 Uids of the newly created temporary variables are marked in TMP_VARS. */
1786 execute_pred_commoning (struct loop
*loop
, VEC (chain_p
, heap
) *chains
,
1792 FOR_EACH_VEC_ELT (chain_p
, chains
, i
, chain
)
1794 if (chain
->type
== CT_INVARIANT
)
1795 execute_load_motion (loop
, chain
, tmp_vars
);
1797 execute_pred_commoning_chain (loop
, chain
, tmp_vars
);
1800 update_ssa (TODO_update_ssa_only_virtuals
);
1803 /* For each reference in CHAINS, if its defining statement is
1804 phi node, record the ssa name that is defined by it. */
1807 replace_phis_by_defined_names (VEC (chain_p
, heap
) *chains
)
1813 FOR_EACH_VEC_ELT (chain_p
, chains
, i
, chain
)
1814 FOR_EACH_VEC_ELT (dref
, chain
->refs
, j
, a
)
1816 if (gimple_code (a
->stmt
) == GIMPLE_PHI
)
1818 a
->name_defined_by_phi
= PHI_RESULT (a
->stmt
);
1824 /* For each reference in CHAINS, if name_defined_by_phi is not
1825 NULL, use it to set the stmt field. */
1828 replace_names_by_phis (VEC (chain_p
, heap
) *chains
)
1834 FOR_EACH_VEC_ELT (chain_p
, chains
, i
, chain
)
1835 FOR_EACH_VEC_ELT (dref
, chain
->refs
, j
, a
)
1836 if (a
->stmt
== NULL
)
1838 a
->stmt
= SSA_NAME_DEF_STMT (a
->name_defined_by_phi
);
1839 gcc_assert (gimple_code (a
->stmt
) == GIMPLE_PHI
);
1840 a
->name_defined_by_phi
= NULL_TREE
;
1844 /* Wrapper over execute_pred_commoning, to pass it as a callback
1845 to tree_transform_and_unroll_loop. */
1849 VEC (chain_p
, heap
) *chains
;
1854 execute_pred_commoning_cbck (struct loop
*loop
, void *data
)
1856 struct epcc_data
*const dta
= (struct epcc_data
*) data
;
1858 /* Restore phi nodes that were replaced by ssa names before
1859 tree_transform_and_unroll_loop (see detailed description in
1860 tree_predictive_commoning_loop). */
1861 replace_names_by_phis (dta
->chains
);
1862 execute_pred_commoning (loop
, dta
->chains
, dta
->tmp_vars
);
1865 /* Base NAME and all the names in the chain of phi nodes that use it
1866 on variable VAR. The phi nodes are recognized by being in the copies of
1867 the header of the LOOP. */
1870 base_names_in_chain_on (struct loop
*loop
, tree name
, tree var
)
1873 imm_use_iterator iter
;
1875 SSA_NAME_VAR (name
) = var
;
1880 FOR_EACH_IMM_USE_STMT (stmt
, iter
, name
)
1882 if (gimple_code (stmt
) == GIMPLE_PHI
1883 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1886 BREAK_FROM_IMM_USE_STMT (iter
);
1892 name
= PHI_RESULT (phi
);
1893 SSA_NAME_VAR (name
) = var
;
1897 /* Given an unrolled LOOP after predictive commoning, remove the
1898 register copies arising from phi nodes by changing the base
1899 variables of SSA names. TMP_VARS is the set of the temporary variables
1900 for those we want to perform this. */
1903 eliminate_temp_copies (struct loop
*loop
, bitmap tmp_vars
)
1907 tree name
, use
, var
;
1908 gimple_stmt_iterator psi
;
1910 e
= loop_latch_edge (loop
);
1911 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1913 phi
= gsi_stmt (psi
);
1914 name
= PHI_RESULT (phi
);
1915 var
= SSA_NAME_VAR (name
);
1916 if (!bitmap_bit_p (tmp_vars
, DECL_UID (var
)))
1918 use
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1919 gcc_assert (TREE_CODE (use
) == SSA_NAME
);
1921 /* Base all the ssa names in the ud and du chain of NAME on VAR. */
1922 stmt
= SSA_NAME_DEF_STMT (use
);
1923 while (gimple_code (stmt
) == GIMPLE_PHI
1924 /* In case we could not unroll the loop enough to eliminate
1925 all copies, we may reach the loop header before the defining
1926 statement (in that case, some register copies will be present
1927 in loop latch in the final code, corresponding to the newly
1928 created looparound phi nodes). */
1929 && gimple_bb (stmt
) != loop
->header
)
1931 gcc_assert (single_pred_p (gimple_bb (stmt
)));
1932 use
= PHI_ARG_DEF (stmt
, 0);
1933 stmt
= SSA_NAME_DEF_STMT (use
);
1936 base_names_in_chain_on (loop
, use
, var
);
1940 /* Returns true if CHAIN is suitable to be combined. */
1943 chain_can_be_combined_p (chain_p chain
)
1945 return (!chain
->combined
1946 && (chain
->type
== CT_LOAD
|| chain
->type
== CT_COMBINATION
));
1949 /* Returns the modify statement that uses NAME. Skips over assignment
1950 statements, NAME is replaced with the actual name used in the returned
1954 find_use_stmt (tree
*name
)
1959 /* Skip over assignments. */
1962 stmt
= single_nonlooparound_use (*name
);
1966 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1969 lhs
= gimple_assign_lhs (stmt
);
1970 if (TREE_CODE (lhs
) != SSA_NAME
)
1973 if (gimple_assign_copy_p (stmt
))
1975 rhs
= gimple_assign_rhs1 (stmt
);
1981 else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1982 == GIMPLE_BINARY_RHS
)
1989 /* Returns true if we may perform reassociation for operation CODE in TYPE. */
1992 may_reassociate_p (tree type
, enum tree_code code
)
1994 if (FLOAT_TYPE_P (type
)
1995 && !flag_unsafe_math_optimizations
)
1998 return (commutative_tree_code (code
)
1999 && associative_tree_code (code
));
2002 /* If the operation used in STMT is associative and commutative, go through the
2003 tree of the same operations and returns its root. Distance to the root
2004 is stored in DISTANCE. */
2007 find_associative_operation_root (gimple stmt
, unsigned *distance
)
2011 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2012 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2015 if (!may_reassociate_p (type
, code
))
2020 lhs
= gimple_assign_lhs (stmt
);
2021 gcc_assert (TREE_CODE (lhs
) == SSA_NAME
);
2023 next
= find_use_stmt (&lhs
);
2025 || gimple_assign_rhs_code (next
) != code
)
2037 /* Returns the common statement in that NAME1 and NAME2 have a use. If there
2038 is no such statement, returns NULL_TREE. In case the operation used on
2039 NAME1 and NAME2 is associative and commutative, returns the root of the
2040 tree formed by this operation instead of the statement that uses NAME1 or
2044 find_common_use_stmt (tree
*name1
, tree
*name2
)
2046 gimple stmt1
, stmt2
;
2048 stmt1
= find_use_stmt (name1
);
2052 stmt2
= find_use_stmt (name2
);
2059 stmt1
= find_associative_operation_root (stmt1
, NULL
);
2062 stmt2
= find_associative_operation_root (stmt2
, NULL
);
2066 return (stmt1
== stmt2
? stmt1
: NULL
);
2069 /* Checks whether R1 and R2 are combined together using CODE, with the result
2070 in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2071 if it is true. If CODE is ERROR_MARK, set these values instead. */
2074 combinable_refs_p (dref r1
, dref r2
,
2075 enum tree_code
*code
, bool *swap
, tree
*rslt_type
)
2077 enum tree_code acode
;
2083 name1
= name_for_ref (r1
);
2084 name2
= name_for_ref (r2
);
2085 gcc_assert (name1
!= NULL_TREE
&& name2
!= NULL_TREE
);
2087 stmt
= find_common_use_stmt (&name1
, &name2
);
2092 acode
= gimple_assign_rhs_code (stmt
);
2093 aswap
= (!commutative_tree_code (acode
)
2094 && gimple_assign_rhs1 (stmt
) != name1
);
2095 atype
= TREE_TYPE (gimple_assign_lhs (stmt
));
2097 if (*code
== ERROR_MARK
)
2105 return (*code
== acode
2107 && *rslt_type
== atype
);
2110 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2111 an assignment of the remaining operand. */
2114 remove_name_from_operation (gimple stmt
, tree op
)
2117 gimple_stmt_iterator si
;
2119 gcc_assert (is_gimple_assign (stmt
));
2121 if (gimple_assign_rhs1 (stmt
) == op
)
2122 other_op
= gimple_assign_rhs2 (stmt
);
2124 other_op
= gimple_assign_rhs1 (stmt
);
2126 si
= gsi_for_stmt (stmt
);
2127 gimple_assign_set_rhs_from_tree (&si
, other_op
);
2129 /* We should not have reallocated STMT. */
2130 gcc_assert (gsi_stmt (si
) == stmt
);
2135 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2136 are combined in a single statement, and returns this statement. */
2139 reassociate_to_the_same_stmt (tree name1
, tree name2
)
2141 gimple stmt1
, stmt2
, root1
, root2
, s1
, s2
;
2142 gimple new_stmt
, tmp_stmt
;
2143 tree new_name
, tmp_name
, var
, r1
, r2
;
2144 unsigned dist1
, dist2
;
2145 enum tree_code code
;
2146 tree type
= TREE_TYPE (name1
);
2147 gimple_stmt_iterator bsi
;
2149 stmt1
= find_use_stmt (&name1
);
2150 stmt2
= find_use_stmt (&name2
);
2151 root1
= find_associative_operation_root (stmt1
, &dist1
);
2152 root2
= find_associative_operation_root (stmt2
, &dist2
);
2153 code
= gimple_assign_rhs_code (stmt1
);
2155 gcc_assert (root1
&& root2
&& root1
== root2
2156 && code
== gimple_assign_rhs_code (stmt2
));
2158 /* Find the root of the nearest expression in that both NAME1 and NAME2
2165 while (dist1
> dist2
)
2167 s1
= find_use_stmt (&r1
);
2168 r1
= gimple_assign_lhs (s1
);
2171 while (dist2
> dist1
)
2173 s2
= find_use_stmt (&r2
);
2174 r2
= gimple_assign_lhs (s2
);
2180 s1
= find_use_stmt (&r1
);
2181 r1
= gimple_assign_lhs (s1
);
2182 s2
= find_use_stmt (&r2
);
2183 r2
= gimple_assign_lhs (s2
);
2186 /* Remove NAME1 and NAME2 from the statements in that they are used
2188 remove_name_from_operation (stmt1
, name1
);
2189 remove_name_from_operation (stmt2
, name2
);
2191 /* Insert the new statement combining NAME1 and NAME2 before S1, and
2192 combine it with the rhs of S1. */
2193 var
= create_tmp_reg (type
, "predreastmp");
2194 add_referenced_var (var
);
2195 new_name
= make_ssa_name (var
, NULL
);
2196 new_stmt
= gimple_build_assign_with_ops (code
, new_name
, name1
, name2
);
2198 var
= create_tmp_reg (type
, "predreastmp");
2199 add_referenced_var (var
);
2200 tmp_name
= make_ssa_name (var
, NULL
);
2202 /* Rhs of S1 may now be either a binary expression with operation
2203 CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2204 so that name1 or name2 was removed from it). */
2205 tmp_stmt
= gimple_build_assign_with_ops (gimple_assign_rhs_code (s1
),
2207 gimple_assign_rhs1 (s1
),
2208 gimple_assign_rhs2 (s1
));
2210 bsi
= gsi_for_stmt (s1
);
2211 gimple_assign_set_rhs_with_ops (&bsi
, code
, new_name
, tmp_name
);
2212 s1
= gsi_stmt (bsi
);
2215 gsi_insert_before (&bsi
, new_stmt
, GSI_SAME_STMT
);
2216 gsi_insert_before (&bsi
, tmp_stmt
, GSI_SAME_STMT
);
2221 /* Returns the statement that combines references R1 and R2. In case R1
2222 and R2 are not used in the same statement, but they are used with an
2223 associative and commutative operation in the same expression, reassociate
2224 the expression so that they are used in the same statement. */
2227 stmt_combining_refs (dref r1
, dref r2
)
2229 gimple stmt1
, stmt2
;
2230 tree name1
= name_for_ref (r1
);
2231 tree name2
= name_for_ref (r2
);
2233 stmt1
= find_use_stmt (&name1
);
2234 stmt2
= find_use_stmt (&name2
);
2238 return reassociate_to_the_same_stmt (name1
, name2
);
2241 /* Tries to combine chains CH1 and CH2 together. If this succeeds, the
2242 description of the new chain is returned, otherwise we return NULL. */
2245 combine_chains (chain_p ch1
, chain_p ch2
)
2248 enum tree_code op
= ERROR_MARK
;
2253 tree rslt_type
= NULL_TREE
;
2257 if (ch1
->length
!= ch2
->length
)
2260 if (VEC_length (dref
, ch1
->refs
) != VEC_length (dref
, ch2
->refs
))
2263 for (i
= 0; (VEC_iterate (dref
, ch1
->refs
, i
, r1
)
2264 && VEC_iterate (dref
, ch2
->refs
, i
, r2
)); i
++)
2266 if (r1
->distance
!= r2
->distance
)
2269 if (!combinable_refs_p (r1
, r2
, &op
, &swap
, &rslt_type
))
2280 new_chain
= XCNEW (struct chain
);
2281 new_chain
->type
= CT_COMBINATION
;
2283 new_chain
->ch1
= ch1
;
2284 new_chain
->ch2
= ch2
;
2285 new_chain
->rslt_type
= rslt_type
;
2286 new_chain
->length
= ch1
->length
;
2288 for (i
= 0; (VEC_iterate (dref
, ch1
->refs
, i
, r1
)
2289 && VEC_iterate (dref
, ch2
->refs
, i
, r2
)); i
++)
2291 nw
= XCNEW (struct dref_d
);
2292 nw
->stmt
= stmt_combining_refs (r1
, r2
);
2293 nw
->distance
= r1
->distance
;
2295 VEC_safe_push (dref
, heap
, new_chain
->refs
, nw
);
2298 new_chain
->has_max_use_after
= false;
2299 root_stmt
= get_chain_root (new_chain
)->stmt
;
2300 for (i
= 1; VEC_iterate (dref
, new_chain
->refs
, i
, nw
); i
++)
2302 if (nw
->distance
== new_chain
->length
2303 && !stmt_dominates_stmt_p (nw
->stmt
, root_stmt
))
2305 new_chain
->has_max_use_after
= true;
2310 ch1
->combined
= true;
2311 ch2
->combined
= true;
2315 /* Try to combine the CHAINS. */
2318 try_combine_chains (VEC (chain_p
, heap
) **chains
)
2321 chain_p ch1
, ch2
, cch
;
2322 VEC (chain_p
, heap
) *worklist
= NULL
;
2324 FOR_EACH_VEC_ELT (chain_p
, *chains
, i
, ch1
)
2325 if (chain_can_be_combined_p (ch1
))
2326 VEC_safe_push (chain_p
, heap
, worklist
, ch1
);
2328 while (!VEC_empty (chain_p
, worklist
))
2330 ch1
= VEC_pop (chain_p
, worklist
);
2331 if (!chain_can_be_combined_p (ch1
))
2334 FOR_EACH_VEC_ELT (chain_p
, *chains
, j
, ch2
)
2336 if (!chain_can_be_combined_p (ch2
))
2339 cch
= combine_chains (ch1
, ch2
);
2342 VEC_safe_push (chain_p
, heap
, worklist
, cch
);
2343 VEC_safe_push (chain_p
, heap
, *chains
, cch
);
2350 /* Prepare initializers for CHAIN in LOOP. Returns false if this is
2351 impossible because one of these initializers may trap, true otherwise. */
2354 prepare_initializers_chain (struct loop
*loop
, chain_p chain
)
2356 unsigned i
, n
= (chain
->type
== CT_INVARIANT
) ? 1 : chain
->length
;
2357 struct data_reference
*dr
= get_chain_root (chain
)->ref
;
2361 edge entry
= loop_preheader_edge (loop
);
2363 /* Find the initializers for the variables, and check that they cannot
2365 chain
->inits
= VEC_alloc (tree
, heap
, n
);
2366 for (i
= 0; i
< n
; i
++)
2367 VEC_quick_push (tree
, chain
->inits
, NULL_TREE
);
2369 /* If we have replaced some looparound phi nodes, use their initializers
2370 instead of creating our own. */
2371 FOR_EACH_VEC_ELT (dref
, chain
->refs
, i
, laref
)
2373 if (gimple_code (laref
->stmt
) != GIMPLE_PHI
)
2376 gcc_assert (laref
->distance
> 0);
2377 VEC_replace (tree
, chain
->inits
, n
- laref
->distance
,
2378 PHI_ARG_DEF_FROM_EDGE (laref
->stmt
, entry
));
2381 for (i
= 0; i
< n
; i
++)
2383 if (VEC_index (tree
, chain
->inits
, i
) != NULL_TREE
)
2386 init
= ref_at_iteration (loop
, DR_REF (dr
), (int) i
- n
);
2390 if (!chain
->all_always_accessed
&& tree_could_trap_p (init
))
2393 init
= force_gimple_operand (init
, &stmts
, false, NULL_TREE
);
2395 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
2397 VEC_replace (tree
, chain
->inits
, i
, init
);
2403 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2404 be used because the initializers might trap. */
2407 prepare_initializers (struct loop
*loop
, VEC (chain_p
, heap
) *chains
)
2412 for (i
= 0; i
< VEC_length (chain_p
, chains
); )
2414 chain
= VEC_index (chain_p
, chains
, i
);
2415 if (prepare_initializers_chain (loop
, chain
))
2419 release_chain (chain
);
2420 VEC_unordered_remove (chain_p
, chains
, i
);
2425 /* Performs predictive commoning for LOOP. Returns true if LOOP was
2429 tree_predictive_commoning_loop (struct loop
*loop
)
2431 VEC (loop_p
, heap
) *loop_nest
;
2432 VEC (data_reference_p
, heap
) *datarefs
;
2433 VEC (ddr_p
, heap
) *dependences
;
2434 struct component
*components
;
2435 VEC (chain_p
, heap
) *chains
= NULL
;
2436 unsigned unroll_factor
;
2437 struct tree_niter_desc desc
;
2438 bool unroll
= false;
2442 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2443 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
2445 /* Find the data references and split them into components according to their
2446 dependence relations. */
2447 datarefs
= VEC_alloc (data_reference_p
, heap
, 10);
2448 dependences
= VEC_alloc (ddr_p
, heap
, 10);
2449 loop_nest
= VEC_alloc (loop_p
, heap
, 3);
2450 if (! compute_data_dependences_for_loop (loop
, true, &loop_nest
, &datarefs
,
2453 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2454 fprintf (dump_file
, "Cannot analyze data dependencies\n");
2455 VEC_free (loop_p
, heap
, loop_nest
);
2456 free_data_refs (datarefs
);
2457 free_dependence_relations (dependences
);
2461 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2462 dump_data_dependence_relations (dump_file
, dependences
);
2464 components
= split_data_refs_to_components (loop
, datarefs
, dependences
);
2465 VEC_free (loop_p
, heap
, loop_nest
);
2466 free_dependence_relations (dependences
);
2469 free_data_refs (datarefs
);
2473 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2475 fprintf (dump_file
, "Initial state:\n\n");
2476 dump_components (dump_file
, components
);
2479 /* Find the suitable components and split them into chains. */
2480 components
= filter_suitable_components (loop
, components
);
2482 tmp_vars
= BITMAP_ALLOC (NULL
);
2483 looparound_phis
= BITMAP_ALLOC (NULL
);
2484 determine_roots (loop
, components
, &chains
);
2485 release_components (components
);
2489 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2491 "Predictive commoning failed: no suitable chains\n");
2494 prepare_initializers (loop
, chains
);
2496 /* Try to combine the chains that are always worked with together. */
2497 try_combine_chains (&chains
);
2499 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2501 fprintf (dump_file
, "Before commoning:\n\n");
2502 dump_chains (dump_file
, chains
);
2505 /* Determine the unroll factor, and if the loop should be unrolled, ensure
2506 that its number of iterations is divisible by the factor. */
2507 unroll_factor
= determine_unroll_factor (chains
);
2509 unroll
= (unroll_factor
> 1
2510 && can_unroll_loop_p (loop
, unroll_factor
, &desc
));
2511 exit
= single_dom_exit (loop
);
2513 /* Execute the predictive commoning transformations, and possibly unroll the
2517 struct epcc_data dta
;
2519 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2520 fprintf (dump_file
, "Unrolling %u times.\n", unroll_factor
);
2522 dta
.chains
= chains
;
2523 dta
.tmp_vars
= tmp_vars
;
2525 update_ssa (TODO_update_ssa_only_virtuals
);
2527 /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2528 execute_pred_commoning_cbck is called may cause phi nodes to be
2529 reallocated, which is a problem since CHAINS may point to these
2530 statements. To fix this, we store the ssa names defined by the
2531 phi nodes here instead of the phi nodes themselves, and restore
2532 the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
2533 replace_phis_by_defined_names (chains
);
2535 tree_transform_and_unroll_loop (loop
, unroll_factor
, exit
, &desc
,
2536 execute_pred_commoning_cbck
, &dta
);
2537 eliminate_temp_copies (loop
, tmp_vars
);
2541 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2543 "Executing predictive commoning without unrolling.\n");
2544 execute_pred_commoning (loop
, chains
, tmp_vars
);
2548 release_chains (chains
);
2549 free_data_refs (datarefs
);
2550 BITMAP_FREE (tmp_vars
);
2551 BITMAP_FREE (looparound_phis
);
2553 free_affine_expand_cache (&name_expansions
);
2558 /* Runs predictive commoning. */
2561 tree_predictive_commoning (void)
2563 bool unrolled
= false;
2568 initialize_original_copy_tables ();
2569 FOR_EACH_LOOP (li
, loop
, LI_ONLY_INNERMOST
)
2570 if (optimize_loop_for_speed_p (loop
))
2572 unrolled
|= tree_predictive_commoning_loop (loop
);
2578 ret
= TODO_cleanup_cfg
;
2580 free_original_copy_tables ();