tree-predcom.c: use gimple_phi in various places
[official-gcc.git] / gcc / tree-predcom.c
blobdfda10ecf1da2a994cc705004eb83a0e6c32e5a9
1 /* Predictive commoning.
2 Copyright (C) 2005-2014 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
9 later version.
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
14 for more details.
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];
36 b[10] = b[10] + i;
37 c[i] = c[99 - i];
38 d[i] = d[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
82 reuse),
84 a[i] --> (*) 2, a[i+1] --> (*) 1, a[i+2] (*)
85 b[10] --> (*) 1, b[10] (*)
87 4) The chains are combined together if possible. If the corresponding
88 elements of two chains are always combined together with the same
89 operator, we remember just the result of this combination, instead
90 of remembering the values separately. We may need to perform
91 reassociation to enable combining, for example
93 e[i] + f[i+1] + e[i+1] + f[i]
95 can be reassociated as
97 (e[i] + f[i]) + (e[i+1] + f[i+1])
99 and we can combine the chains for e and f into one chain.
101 5) For each root reference (end of the chain) R, let N be maximum distance
102 of a reference reusing its value. Variables R0 up to RN are created,
103 together with phi nodes that transfer values from R1 .. RN to
104 R0 .. R(N-1).
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++)
119 f = phi (a[0], s);
120 s = phi (a[1], f);
121 x = phi (b[10], x);
123 f = f + s;
124 a[i+2] = f;
125 x = x + i;
126 b[10] = x;
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)
144 f = phi (a[0], f);
145 s = phi (a[1], s);
146 x = phi (b[10], x);
148 f = f + s;
149 a[i+2] = f;
150 x = x + i;
151 b[10] = x;
153 s = s + f;
154 a[i+3] = s;
155 x = x + i;
156 b[10] = x;
159 TODO -- stores killing other stores can be taken into account, e.g.,
160 for (i = 0; i < n; i++)
162 a[i] = 1;
163 a[i+2] = 2;
166 can be replaced with
168 t0 = a[0];
169 t1 = a[1];
170 for (i = 0; i < n; i++)
172 a[i] = 1;
173 t2 = 2;
174 t0 = t1;
175 t1 = t2;
177 a[n] = t0;
178 a[n+1] = t1;
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. */
187 #include "config.h"
188 #include "system.h"
189 #include "coretypes.h"
190 #include "tm.h"
191 #include "tree.h"
192 #include "tm_p.h"
193 #include "cfgloop.h"
194 #include "basic-block.h"
195 #include "tree-ssa-alias.h"
196 #include "internal-fn.h"
197 #include "tree-eh.h"
198 #include "gimple-expr.h"
199 #include "is-a.h"
200 #include "gimple.h"
201 #include "gimplify.h"
202 #include "gimple-iterator.h"
203 #include "gimplify-me.h"
204 #include "gimple-ssa.h"
205 #include "tree-phinodes.h"
206 #include "ssa-iterators.h"
207 #include "stringpool.h"
208 #include "tree-ssanames.h"
209 #include "tree-ssa-loop-ivopts.h"
210 #include "tree-ssa-loop-manip.h"
211 #include "tree-ssa-loop-niter.h"
212 #include "tree-ssa-loop.h"
213 #include "tree-into-ssa.h"
214 #include "expr.h"
215 #include "tree-dfa.h"
216 #include "tree-ssa.h"
217 #include "tree-data-ref.h"
218 #include "tree-scalar-evolution.h"
219 #include "tree-chrec.h"
220 #include "params.h"
221 #include "gimple-pretty-print.h"
222 #include "tree-pass.h"
223 #include "tree-affine.h"
224 #include "tree-inline.h"
225 #include "wide-int-print.h"
227 /* The maximum number of iterations between the considered memory
228 references. */
230 #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
232 /* Data references (or phi nodes that carry data reference values across
233 loop iterations). */
235 typedef struct dref_d
237 /* The reference itself. */
238 struct data_reference *ref;
240 /* The statement in that the reference appears. */
241 gimple stmt;
243 /* In case that STMT is a phi node, this field is set to the SSA name
244 defined by it in replace_phis_by_defined_names (in order to avoid
245 pointing to phi node that got reallocated in the meantime). */
246 tree name_defined_by_phi;
248 /* Distance of the reference from the root of the chain (in number of
249 iterations of the loop). */
250 unsigned distance;
252 /* Number of iterations offset from the first reference in the component. */
253 widest_int offset;
255 /* Number of the reference in a component, in dominance ordering. */
256 unsigned pos;
258 /* True if the memory reference is always accessed when the loop is
259 entered. */
260 unsigned always_accessed : 1;
261 } *dref;
264 /* Type of the chain of the references. */
266 enum chain_type
268 /* The addresses of the references in the chain are constant. */
269 CT_INVARIANT,
271 /* There are only loads in the chain. */
272 CT_LOAD,
274 /* Root of the chain is store, the rest are loads. */
275 CT_STORE_LOAD,
277 /* A combination of two chains. */
278 CT_COMBINATION
281 /* Chains of data references. */
283 typedef struct chain
285 /* Type of the chain. */
286 enum chain_type type;
288 /* For combination chains, the operator and the two chains that are
289 combined, and the type of the result. */
290 enum tree_code op;
291 tree rslt_type;
292 struct chain *ch1, *ch2;
294 /* The references in the chain. */
295 vec<dref> refs;
297 /* The maximum distance of the reference in the chain from the root. */
298 unsigned length;
300 /* The variables used to copy the value throughout iterations. */
301 vec<tree> vars;
303 /* Initializers for the variables. */
304 vec<tree> inits;
306 /* True if there is a use of a variable with the maximal distance
307 that comes after the root in the loop. */
308 unsigned has_max_use_after : 1;
310 /* True if all the memory references in the chain are always accessed. */
311 unsigned all_always_accessed : 1;
313 /* True if this chain was combined together with some other chain. */
314 unsigned combined : 1;
315 } *chain_p;
318 /* Describes the knowledge about the step of the memory references in
319 the component. */
321 enum ref_step_type
323 /* The step is zero. */
324 RS_INVARIANT,
326 /* The step is nonzero. */
327 RS_NONZERO,
329 /* The step may or may not be nonzero. */
330 RS_ANY
333 /* Components of the data dependence graph. */
335 struct component
337 /* The references in the component. */
338 vec<dref> refs;
340 /* What we know about the step of the references in the component. */
341 enum ref_step_type comp_step;
343 /* Next component in the list. */
344 struct component *next;
347 /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */
349 static bitmap looparound_phis;
351 /* Cache used by tree_to_aff_combination_expand. */
353 static hash_map<tree, name_expansion *> *name_expansions;
355 /* Dumps data reference REF to FILE. */
357 extern void dump_dref (FILE *, dref);
358 void
359 dump_dref (FILE *file, dref ref)
361 if (ref->ref)
363 fprintf (file, " ");
364 print_generic_expr (file, DR_REF (ref->ref), TDF_SLIM);
365 fprintf (file, " (id %u%s)\n", ref->pos,
366 DR_IS_READ (ref->ref) ? "" : ", write");
368 fprintf (file, " offset ");
369 print_decs (ref->offset, file);
370 fprintf (file, "\n");
372 fprintf (file, " distance %u\n", ref->distance);
374 else
376 if (gimple_code (ref->stmt) == GIMPLE_PHI)
377 fprintf (file, " looparound ref\n");
378 else
379 fprintf (file, " combination ref\n");
380 fprintf (file, " in statement ");
381 print_gimple_stmt (file, ref->stmt, 0, TDF_SLIM);
382 fprintf (file, "\n");
383 fprintf (file, " distance %u\n", ref->distance);
388 /* Dumps CHAIN to FILE. */
390 extern void dump_chain (FILE *, chain_p);
391 void
392 dump_chain (FILE *file, chain_p chain)
394 dref a;
395 const char *chain_type;
396 unsigned i;
397 tree var;
399 switch (chain->type)
401 case CT_INVARIANT:
402 chain_type = "Load motion";
403 break;
405 case CT_LOAD:
406 chain_type = "Loads-only";
407 break;
409 case CT_STORE_LOAD:
410 chain_type = "Store-loads";
411 break;
413 case CT_COMBINATION:
414 chain_type = "Combination";
415 break;
417 default:
418 gcc_unreachable ();
421 fprintf (file, "%s chain %p%s\n", chain_type, (void *) chain,
422 chain->combined ? " (combined)" : "");
423 if (chain->type != CT_INVARIANT)
424 fprintf (file, " max distance %u%s\n", chain->length,
425 chain->has_max_use_after ? "" : ", may reuse first");
427 if (chain->type == CT_COMBINATION)
429 fprintf (file, " equal to %p %s %p in type ",
430 (void *) chain->ch1, op_symbol_code (chain->op),
431 (void *) chain->ch2);
432 print_generic_expr (file, chain->rslt_type, TDF_SLIM);
433 fprintf (file, "\n");
436 if (chain->vars.exists ())
438 fprintf (file, " vars");
439 FOR_EACH_VEC_ELT (chain->vars, i, var)
441 fprintf (file, " ");
442 print_generic_expr (file, var, TDF_SLIM);
444 fprintf (file, "\n");
447 if (chain->inits.exists ())
449 fprintf (file, " inits");
450 FOR_EACH_VEC_ELT (chain->inits, i, var)
452 fprintf (file, " ");
453 print_generic_expr (file, var, TDF_SLIM);
455 fprintf (file, "\n");
458 fprintf (file, " references:\n");
459 FOR_EACH_VEC_ELT (chain->refs, i, a)
460 dump_dref (file, a);
462 fprintf (file, "\n");
465 /* Dumps CHAINS to FILE. */
467 extern void dump_chains (FILE *, vec<chain_p> );
468 void
469 dump_chains (FILE *file, vec<chain_p> chains)
471 chain_p chain;
472 unsigned i;
474 FOR_EACH_VEC_ELT (chains, i, chain)
475 dump_chain (file, chain);
478 /* Dumps COMP to FILE. */
480 extern void dump_component (FILE *, struct component *);
481 void
482 dump_component (FILE *file, struct component *comp)
484 dref a;
485 unsigned i;
487 fprintf (file, "Component%s:\n",
488 comp->comp_step == RS_INVARIANT ? " (invariant)" : "");
489 FOR_EACH_VEC_ELT (comp->refs, i, a)
490 dump_dref (file, a);
491 fprintf (file, "\n");
494 /* Dumps COMPS to FILE. */
496 extern void dump_components (FILE *, struct component *);
497 void
498 dump_components (FILE *file, struct component *comps)
500 struct component *comp;
502 for (comp = comps; comp; comp = comp->next)
503 dump_component (file, comp);
506 /* Frees a chain CHAIN. */
508 static void
509 release_chain (chain_p chain)
511 dref ref;
512 unsigned i;
514 if (chain == NULL)
515 return;
517 FOR_EACH_VEC_ELT (chain->refs, i, ref)
518 free (ref);
520 chain->refs.release ();
521 chain->vars.release ();
522 chain->inits.release ();
524 free (chain);
527 /* Frees CHAINS. */
529 static void
530 release_chains (vec<chain_p> chains)
532 unsigned i;
533 chain_p chain;
535 FOR_EACH_VEC_ELT (chains, i, chain)
536 release_chain (chain);
537 chains.release ();
540 /* Frees a component COMP. */
542 static void
543 release_component (struct component *comp)
545 comp->refs.release ();
546 free (comp);
549 /* Frees list of components COMPS. */
551 static void
552 release_components (struct component *comps)
554 struct component *act, *next;
556 for (act = comps; act; act = next)
558 next = act->next;
559 release_component (act);
563 /* Finds a root of tree given by FATHERS containing A, and performs path
564 shortening. */
566 static unsigned
567 component_of (unsigned fathers[], unsigned a)
569 unsigned root, n;
571 for (root = a; root != fathers[root]; root = fathers[root])
572 continue;
574 for (; a != root; a = n)
576 n = fathers[a];
577 fathers[a] = root;
580 return root;
583 /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the
584 components, A and B are components to merge. */
586 static void
587 merge_comps (unsigned fathers[], unsigned sizes[], unsigned a, unsigned b)
589 unsigned ca = component_of (fathers, a);
590 unsigned cb = component_of (fathers, b);
592 if (ca == cb)
593 return;
595 if (sizes[ca] < sizes[cb])
597 sizes[cb] += sizes[ca];
598 fathers[ca] = cb;
600 else
602 sizes[ca] += sizes[cb];
603 fathers[cb] = ca;
607 /* Returns true if A is a reference that is suitable for predictive commoning
608 in the innermost loop that contains it. REF_STEP is set according to the
609 step of the reference A. */
611 static bool
612 suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step)
614 tree ref = DR_REF (a), step = DR_STEP (a);
616 if (!step
617 || TREE_THIS_VOLATILE (ref)
618 || !is_gimple_reg_type (TREE_TYPE (ref))
619 || tree_could_throw_p (ref))
620 return false;
622 if (integer_zerop (step))
623 *ref_step = RS_INVARIANT;
624 else if (integer_nonzerop (step))
625 *ref_step = RS_NONZERO;
626 else
627 *ref_step = RS_ANY;
629 return true;
632 /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
634 static void
635 aff_combination_dr_offset (struct data_reference *dr, aff_tree *offset)
637 tree type = TREE_TYPE (DR_OFFSET (dr));
638 aff_tree delta;
640 tree_to_aff_combination_expand (DR_OFFSET (dr), type, offset,
641 &name_expansions);
642 aff_combination_const (&delta, type, wi::to_widest (DR_INIT (dr)));
643 aff_combination_add (offset, &delta);
646 /* Determines number of iterations of the innermost enclosing loop before B
647 refers to exactly the same location as A and stores it to OFF. If A and
648 B do not have the same step, they never meet, or anything else fails,
649 returns false, otherwise returns true. Both A and B are assumed to
650 satisfy suitable_reference_p. */
652 static bool
653 determine_offset (struct data_reference *a, struct data_reference *b,
654 widest_int *off)
656 aff_tree diff, baseb, step;
657 tree typea, typeb;
659 /* Check that both the references access the location in the same type. */
660 typea = TREE_TYPE (DR_REF (a));
661 typeb = TREE_TYPE (DR_REF (b));
662 if (!useless_type_conversion_p (typeb, typea))
663 return false;
665 /* Check whether the base address and the step of both references is the
666 same. */
667 if (!operand_equal_p (DR_STEP (a), DR_STEP (b), 0)
668 || !operand_equal_p (DR_BASE_ADDRESS (a), DR_BASE_ADDRESS (b), 0))
669 return false;
671 if (integer_zerop (DR_STEP (a)))
673 /* If the references have loop invariant address, check that they access
674 exactly the same location. */
675 *off = 0;
676 return (operand_equal_p (DR_OFFSET (a), DR_OFFSET (b), 0)
677 && operand_equal_p (DR_INIT (a), DR_INIT (b), 0));
680 /* Compare the offsets of the addresses, and check whether the difference
681 is a multiple of step. */
682 aff_combination_dr_offset (a, &diff);
683 aff_combination_dr_offset (b, &baseb);
684 aff_combination_scale (&baseb, -1);
685 aff_combination_add (&diff, &baseb);
687 tree_to_aff_combination_expand (DR_STEP (a), TREE_TYPE (DR_STEP (a)),
688 &step, &name_expansions);
689 return aff_combination_constant_multiple_p (&diff, &step, off);
692 /* Returns the last basic block in LOOP for that we are sure that
693 it is executed whenever the loop is entered. */
695 static basic_block
696 last_always_executed_block (struct loop *loop)
698 unsigned i;
699 vec<edge> exits = get_loop_exit_edges (loop);
700 edge ex;
701 basic_block last = loop->latch;
703 FOR_EACH_VEC_ELT (exits, i, ex)
704 last = nearest_common_dominator (CDI_DOMINATORS, last, ex->src);
705 exits.release ();
707 return last;
710 /* Splits dependence graph on DATAREFS described by DEPENDS to components. */
712 static struct component *
713 split_data_refs_to_components (struct loop *loop,
714 vec<data_reference_p> datarefs,
715 vec<ddr_p> depends)
717 unsigned i, n = datarefs.length ();
718 unsigned ca, ia, ib, bad;
719 unsigned *comp_father = XNEWVEC (unsigned, n + 1);
720 unsigned *comp_size = XNEWVEC (unsigned, n + 1);
721 struct component **comps;
722 struct data_reference *dr, *dra, *drb;
723 struct data_dependence_relation *ddr;
724 struct component *comp_list = NULL, *comp;
725 dref dataref;
726 basic_block last_always_executed = last_always_executed_block (loop);
728 FOR_EACH_VEC_ELT (datarefs, i, dr)
730 if (!DR_REF (dr))
732 /* A fake reference for call or asm_expr that may clobber memory;
733 just fail. */
734 goto end;
736 /* predcom pass isn't prepared to handle calls with data references. */
737 if (is_gimple_call (DR_STMT (dr)))
738 goto end;
739 dr->aux = (void *) (size_t) i;
740 comp_father[i] = i;
741 comp_size[i] = 1;
744 /* A component reserved for the "bad" data references. */
745 comp_father[n] = n;
746 comp_size[n] = 1;
748 FOR_EACH_VEC_ELT (datarefs, i, dr)
750 enum ref_step_type dummy;
752 if (!suitable_reference_p (dr, &dummy))
754 ia = (unsigned) (size_t) dr->aux;
755 merge_comps (comp_father, comp_size, n, ia);
759 FOR_EACH_VEC_ELT (depends, i, ddr)
761 widest_int dummy_off;
763 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
764 continue;
766 dra = DDR_A (ddr);
767 drb = DDR_B (ddr);
768 ia = component_of (comp_father, (unsigned) (size_t) dra->aux);
769 ib = component_of (comp_father, (unsigned) (size_t) drb->aux);
770 if (ia == ib)
771 continue;
773 bad = component_of (comp_father, n);
775 /* If both A and B are reads, we may ignore unsuitable dependences. */
776 if (DR_IS_READ (dra) && DR_IS_READ (drb))
778 if (ia == bad || ib == bad
779 || !determine_offset (dra, drb, &dummy_off))
780 continue;
782 /* If A is read and B write or vice versa and there is unsuitable
783 dependence, instead of merging both components into a component
784 that will certainly not pass suitable_component_p, just put the
785 read into bad component, perhaps at least the write together with
786 all the other data refs in it's component will be optimizable. */
787 else if (DR_IS_READ (dra) && ib != bad)
789 if (ia == bad)
790 continue;
791 else if (!determine_offset (dra, drb, &dummy_off))
793 merge_comps (comp_father, comp_size, bad, ia);
794 continue;
797 else if (DR_IS_READ (drb) && ia != bad)
799 if (ib == bad)
800 continue;
801 else if (!determine_offset (dra, drb, &dummy_off))
803 merge_comps (comp_father, comp_size, bad, ib);
804 continue;
808 merge_comps (comp_father, comp_size, ia, ib);
811 comps = XCNEWVEC (struct component *, n);
812 bad = component_of (comp_father, n);
813 FOR_EACH_VEC_ELT (datarefs, i, dr)
815 ia = (unsigned) (size_t) dr->aux;
816 ca = component_of (comp_father, ia);
817 if (ca == bad)
818 continue;
820 comp = comps[ca];
821 if (!comp)
823 comp = XCNEW (struct component);
824 comp->refs.create (comp_size[ca]);
825 comps[ca] = comp;
828 dataref = XCNEW (struct dref_d);
829 dataref->ref = dr;
830 dataref->stmt = DR_STMT (dr);
831 dataref->offset = 0;
832 dataref->distance = 0;
834 dataref->always_accessed
835 = dominated_by_p (CDI_DOMINATORS, last_always_executed,
836 gimple_bb (dataref->stmt));
837 dataref->pos = comp->refs.length ();
838 comp->refs.quick_push (dataref);
841 for (i = 0; i < n; i++)
843 comp = comps[i];
844 if (comp)
846 comp->next = comp_list;
847 comp_list = comp;
850 free (comps);
852 end:
853 free (comp_father);
854 free (comp_size);
855 return comp_list;
858 /* Returns true if the component COMP satisfies the conditions
859 described in 2) at the beginning of this file. LOOP is the current
860 loop. */
862 static bool
863 suitable_component_p (struct loop *loop, struct component *comp)
865 unsigned i;
866 dref a, first;
867 basic_block ba, bp = loop->header;
868 bool ok, has_write = false;
870 FOR_EACH_VEC_ELT (comp->refs, i, a)
872 ba = gimple_bb (a->stmt);
874 if (!just_once_each_iteration_p (loop, ba))
875 return false;
877 gcc_assert (dominated_by_p (CDI_DOMINATORS, ba, bp));
878 bp = ba;
880 if (DR_IS_WRITE (a->ref))
881 has_write = true;
884 first = comp->refs[0];
885 ok = suitable_reference_p (first->ref, &comp->comp_step);
886 gcc_assert (ok);
887 first->offset = 0;
889 for (i = 1; comp->refs.iterate (i, &a); i++)
891 if (!determine_offset (first->ref, a->ref, &a->offset))
892 return false;
894 #ifdef ENABLE_CHECKING
896 enum ref_step_type a_step;
897 ok = suitable_reference_p (a->ref, &a_step);
898 gcc_assert (ok && a_step == comp->comp_step);
900 #endif
903 /* If there is a write inside the component, we must know whether the
904 step is nonzero or not -- we would not otherwise be able to recognize
905 whether the value accessed by reads comes from the OFFSET-th iteration
906 or the previous one. */
907 if (has_write && comp->comp_step == RS_ANY)
908 return false;
910 return true;
913 /* Check the conditions on references inside each of components COMPS,
914 and remove the unsuitable components from the list. The new list
915 of components is returned. The conditions are described in 2) at
916 the beginning of this file. LOOP is the current loop. */
918 static struct component *
919 filter_suitable_components (struct loop *loop, struct component *comps)
921 struct component **comp, *act;
923 for (comp = &comps; *comp; )
925 act = *comp;
926 if (suitable_component_p (loop, act))
927 comp = &act->next;
928 else
930 dref ref;
931 unsigned i;
933 *comp = act->next;
934 FOR_EACH_VEC_ELT (act->refs, i, ref)
935 free (ref);
936 release_component (act);
940 return comps;
943 /* Compares two drefs A and B by their offset and position. Callback for
944 qsort. */
946 static int
947 order_drefs (const void *a, const void *b)
949 const dref *const da = (const dref *) a;
950 const dref *const db = (const dref *) b;
951 int offcmp = wi::cmps ((*da)->offset, (*db)->offset);
953 if (offcmp != 0)
954 return offcmp;
956 return (*da)->pos - (*db)->pos;
959 /* Returns root of the CHAIN. */
961 static inline dref
962 get_chain_root (chain_p chain)
964 return chain->refs[0];
967 /* Adds REF to the chain CHAIN. */
969 static void
970 add_ref_to_chain (chain_p chain, dref ref)
972 dref root = get_chain_root (chain);
974 gcc_assert (wi::les_p (root->offset, ref->offset));
975 widest_int dist = ref->offset - root->offset;
976 if (wi::leu_p (MAX_DISTANCE, dist))
978 free (ref);
979 return;
981 gcc_assert (wi::fits_uhwi_p (dist));
983 chain->refs.safe_push (ref);
985 ref->distance = dist.to_uhwi ();
987 if (ref->distance >= chain->length)
989 chain->length = ref->distance;
990 chain->has_max_use_after = false;
993 if (ref->distance == chain->length
994 && ref->pos > root->pos)
995 chain->has_max_use_after = true;
997 chain->all_always_accessed &= ref->always_accessed;
1000 /* Returns the chain for invariant component COMP. */
1002 static chain_p
1003 make_invariant_chain (struct component *comp)
1005 chain_p chain = XCNEW (struct chain);
1006 unsigned i;
1007 dref ref;
1009 chain->type = CT_INVARIANT;
1011 chain->all_always_accessed = true;
1013 FOR_EACH_VEC_ELT (comp->refs, i, ref)
1015 chain->refs.safe_push (ref);
1016 chain->all_always_accessed &= ref->always_accessed;
1019 return chain;
1022 /* Make a new chain rooted at REF. */
1024 static chain_p
1025 make_rooted_chain (dref ref)
1027 chain_p chain = XCNEW (struct chain);
1029 chain->type = DR_IS_READ (ref->ref) ? CT_LOAD : CT_STORE_LOAD;
1031 chain->refs.safe_push (ref);
1032 chain->all_always_accessed = ref->always_accessed;
1034 ref->distance = 0;
1036 return chain;
1039 /* Returns true if CHAIN is not trivial. */
1041 static bool
1042 nontrivial_chain_p (chain_p chain)
1044 return chain != NULL && chain->refs.length () > 1;
1047 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1048 is no such name. */
1050 static tree
1051 name_for_ref (dref ref)
1053 tree name;
1055 if (is_gimple_assign (ref->stmt))
1057 if (!ref->ref || DR_IS_READ (ref->ref))
1058 name = gimple_assign_lhs (ref->stmt);
1059 else
1060 name = gimple_assign_rhs1 (ref->stmt);
1062 else
1063 name = PHI_RESULT (ref->stmt);
1065 return (TREE_CODE (name) == SSA_NAME ? name : NULL_TREE);
1068 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1069 iterations of the innermost enclosing loop). */
1071 static bool
1072 valid_initializer_p (struct data_reference *ref,
1073 unsigned distance, struct data_reference *root)
1075 aff_tree diff, base, step;
1076 widest_int off;
1078 /* Both REF and ROOT must be accessing the same object. */
1079 if (!operand_equal_p (DR_BASE_ADDRESS (ref), DR_BASE_ADDRESS (root), 0))
1080 return false;
1082 /* The initializer is defined outside of loop, hence its address must be
1083 invariant inside the loop. */
1084 gcc_assert (integer_zerop (DR_STEP (ref)));
1086 /* If the address of the reference is invariant, initializer must access
1087 exactly the same location. */
1088 if (integer_zerop (DR_STEP (root)))
1089 return (operand_equal_p (DR_OFFSET (ref), DR_OFFSET (root), 0)
1090 && operand_equal_p (DR_INIT (ref), DR_INIT (root), 0));
1092 /* Verify that this index of REF is equal to the root's index at
1093 -DISTANCE-th iteration. */
1094 aff_combination_dr_offset (root, &diff);
1095 aff_combination_dr_offset (ref, &base);
1096 aff_combination_scale (&base, -1);
1097 aff_combination_add (&diff, &base);
1099 tree_to_aff_combination_expand (DR_STEP (root), TREE_TYPE (DR_STEP (root)),
1100 &step, &name_expansions);
1101 if (!aff_combination_constant_multiple_p (&diff, &step, &off))
1102 return false;
1104 if (off != distance)
1105 return false;
1107 return true;
1110 /* Finds looparound phi node of LOOP that copies the value of REF, and if its
1111 initial value is correct (equal to initial value of REF shifted by one
1112 iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT
1113 is the root of the current chain. */
1115 static gimple_phi
1116 find_looparound_phi (struct loop *loop, dref ref, dref root)
1118 tree name, init, init_ref;
1119 gimple_phi phi = NULL;
1120 gimple init_stmt;
1121 edge latch = loop_latch_edge (loop);
1122 struct data_reference init_dr;
1123 gimple_phi_iterator psi;
1125 if (is_gimple_assign (ref->stmt))
1127 if (DR_IS_READ (ref->ref))
1128 name = gimple_assign_lhs (ref->stmt);
1129 else
1130 name = gimple_assign_rhs1 (ref->stmt);
1132 else
1133 name = PHI_RESULT (ref->stmt);
1134 if (!name)
1135 return NULL;
1137 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1139 phi = psi.phi ();
1140 if (PHI_ARG_DEF_FROM_EDGE (phi, latch) == name)
1141 break;
1144 if (gsi_end_p (psi))
1145 return NULL;
1147 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1148 if (TREE_CODE (init) != SSA_NAME)
1149 return NULL;
1150 init_stmt = SSA_NAME_DEF_STMT (init);
1151 if (gimple_code (init_stmt) != GIMPLE_ASSIGN)
1152 return NULL;
1153 gcc_assert (gimple_assign_lhs (init_stmt) == init);
1155 init_ref = gimple_assign_rhs1 (init_stmt);
1156 if (!REFERENCE_CLASS_P (init_ref)
1157 && !DECL_P (init_ref))
1158 return NULL;
1160 /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1161 loop enclosing PHI). */
1162 memset (&init_dr, 0, sizeof (struct data_reference));
1163 DR_REF (&init_dr) = init_ref;
1164 DR_STMT (&init_dr) = phi;
1165 if (!dr_analyze_innermost (&init_dr, loop))
1166 return NULL;
1168 if (!valid_initializer_p (&init_dr, ref->distance + 1, root->ref))
1169 return NULL;
1171 return phi;
1174 /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1176 static void
1177 insert_looparound_copy (chain_p chain, dref ref, gimple_phi phi)
1179 dref nw = XCNEW (struct dref_d), aref;
1180 unsigned i;
1182 nw->stmt = phi;
1183 nw->distance = ref->distance + 1;
1184 nw->always_accessed = 1;
1186 FOR_EACH_VEC_ELT (chain->refs, i, aref)
1187 if (aref->distance >= nw->distance)
1188 break;
1189 chain->refs.safe_insert (i, nw);
1191 if (nw->distance > chain->length)
1193 chain->length = nw->distance;
1194 chain->has_max_use_after = false;
1198 /* For references in CHAIN that are copied around the LOOP (created previously
1199 by PRE, or by user), add the results of such copies to the chain. This
1200 enables us to remove the copies by unrolling, and may need less registers
1201 (also, it may allow us to combine chains together). */
1203 static void
1204 add_looparound_copies (struct loop *loop, chain_p chain)
1206 unsigned i;
1207 dref ref, root = get_chain_root (chain);
1208 gimple_phi phi;
1210 FOR_EACH_VEC_ELT (chain->refs, i, ref)
1212 phi = find_looparound_phi (loop, ref, root);
1213 if (!phi)
1214 continue;
1216 bitmap_set_bit (looparound_phis, SSA_NAME_VERSION (PHI_RESULT (phi)));
1217 insert_looparound_copy (chain, ref, phi);
1221 /* Find roots of the values and determine distances in the component COMP.
1222 The references are redistributed into CHAINS. LOOP is the current
1223 loop. */
1225 static void
1226 determine_roots_comp (struct loop *loop,
1227 struct component *comp,
1228 vec<chain_p> *chains)
1230 unsigned i;
1231 dref a;
1232 chain_p chain = NULL;
1233 widest_int last_ofs = 0;
1235 /* Invariants are handled specially. */
1236 if (comp->comp_step == RS_INVARIANT)
1238 chain = make_invariant_chain (comp);
1239 chains->safe_push (chain);
1240 return;
1243 comp->refs.qsort (order_drefs);
1245 FOR_EACH_VEC_ELT (comp->refs, i, a)
1247 if (!chain || DR_IS_WRITE (a->ref)
1248 || wi::leu_p (MAX_DISTANCE, a->offset - last_ofs))
1250 if (nontrivial_chain_p (chain))
1252 add_looparound_copies (loop, chain);
1253 chains->safe_push (chain);
1255 else
1256 release_chain (chain);
1257 chain = make_rooted_chain (a);
1258 last_ofs = a->offset;
1259 continue;
1262 add_ref_to_chain (chain, a);
1265 if (nontrivial_chain_p (chain))
1267 add_looparound_copies (loop, chain);
1268 chains->safe_push (chain);
1270 else
1271 release_chain (chain);
1274 /* Find roots of the values and determine distances in components COMPS, and
1275 separates the references to CHAINS. LOOP is the current loop. */
1277 static void
1278 determine_roots (struct loop *loop,
1279 struct component *comps, vec<chain_p> *chains)
1281 struct component *comp;
1283 for (comp = comps; comp; comp = comp->next)
1284 determine_roots_comp (loop, comp, chains);
1287 /* Replace the reference in statement STMT with temporary variable
1288 NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of
1289 the reference in the statement. IN_LHS is true if the reference
1290 is in the lhs of STMT, false if it is in rhs. */
1292 static void
1293 replace_ref_with (gimple stmt, tree new_tree, bool set, bool in_lhs)
1295 tree val;
1296 gimple new_stmt;
1297 gimple_stmt_iterator bsi, psi;
1299 if (gimple_code (stmt) == GIMPLE_PHI)
1301 gcc_assert (!in_lhs && !set);
1303 val = PHI_RESULT (stmt);
1304 bsi = gsi_after_labels (gimple_bb (stmt));
1305 psi = gsi_for_stmt (stmt);
1306 remove_phi_node (&psi, false);
1308 /* Turn the phi node into GIMPLE_ASSIGN. */
1309 new_stmt = gimple_build_assign (val, new_tree);
1310 gsi_insert_before (&bsi, new_stmt, GSI_NEW_STMT);
1311 return;
1314 /* Since the reference is of gimple_reg type, it should only
1315 appear as lhs or rhs of modify statement. */
1316 gcc_assert (is_gimple_assign (stmt));
1318 bsi = gsi_for_stmt (stmt);
1320 /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */
1321 if (!set)
1323 gcc_assert (!in_lhs);
1324 gimple_assign_set_rhs_from_tree (&bsi, new_tree);
1325 stmt = gsi_stmt (bsi);
1326 update_stmt (stmt);
1327 return;
1330 if (in_lhs)
1332 /* We have statement
1334 OLD = VAL
1336 If OLD is a memory reference, then VAL is gimple_val, and we transform
1337 this to
1339 OLD = VAL
1340 NEW = VAL
1342 Otherwise, we are replacing a combination chain,
1343 VAL is the expression that performs the combination, and OLD is an
1344 SSA name. In this case, we transform the assignment to
1346 OLD = VAL
1347 NEW = OLD
1351 val = gimple_assign_lhs (stmt);
1352 if (TREE_CODE (val) != SSA_NAME)
1354 val = gimple_assign_rhs1 (stmt);
1355 gcc_assert (gimple_assign_single_p (stmt));
1356 if (TREE_CLOBBER_P (val))
1357 val = get_or_create_ssa_default_def (cfun, SSA_NAME_VAR (new_tree));
1358 else
1359 gcc_assert (gimple_assign_copy_p (stmt));
1362 else
1364 /* VAL = OLD
1366 is transformed to
1368 VAL = OLD
1369 NEW = VAL */
1371 val = gimple_assign_lhs (stmt);
1374 new_stmt = gimple_build_assign (new_tree, unshare_expr (val));
1375 gsi_insert_after (&bsi, new_stmt, GSI_NEW_STMT);
1378 /* Returns a memory reference to DR in the ITER-th iteration of
1379 the loop it was analyzed in. Append init stmts to STMTS. */
1381 static tree
1382 ref_at_iteration (data_reference_p dr, int iter, gimple_seq *stmts)
1384 tree off = DR_OFFSET (dr);
1385 tree coff = DR_INIT (dr);
1386 if (iter == 0)
1388 else if (TREE_CODE (DR_STEP (dr)) == INTEGER_CST)
1389 coff = size_binop (PLUS_EXPR, coff,
1390 size_binop (MULT_EXPR, DR_STEP (dr), ssize_int (iter)));
1391 else
1392 off = size_binop (PLUS_EXPR, off,
1393 size_binop (MULT_EXPR, DR_STEP (dr), ssize_int (iter)));
1394 tree addr = fold_build_pointer_plus (DR_BASE_ADDRESS (dr), off);
1395 addr = force_gimple_operand_1 (addr, stmts, is_gimple_mem_ref_addr,
1396 NULL_TREE);
1397 tree alias_ptr = fold_convert (reference_alias_ptr_type (DR_REF (dr)), coff);
1398 /* While data-ref analysis punts on bit offsets it still handles
1399 bitfield accesses at byte boundaries. Cope with that. Note that
1400 we cannot simply re-apply the outer COMPONENT_REF because the
1401 byte-granular portion of it is already applied via DR_INIT and
1402 DR_OFFSET, so simply build a BIT_FIELD_REF knowing that the bits
1403 start at offset zero. */
1404 if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
1405 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
1407 tree field = TREE_OPERAND (DR_REF (dr), 1);
1408 return build3 (BIT_FIELD_REF, TREE_TYPE (DR_REF (dr)),
1409 build2 (MEM_REF, DECL_BIT_FIELD_TYPE (field),
1410 addr, alias_ptr),
1411 DECL_SIZE (field), bitsize_zero_node);
1413 else
1414 return fold_build2 (MEM_REF, TREE_TYPE (DR_REF (dr)), addr, alias_ptr);
1417 /* Get the initialization expression for the INDEX-th temporary variable
1418 of CHAIN. */
1420 static tree
1421 get_init_expr (chain_p chain, unsigned index)
1423 if (chain->type == CT_COMBINATION)
1425 tree e1 = get_init_expr (chain->ch1, index);
1426 tree e2 = get_init_expr (chain->ch2, index);
1428 return fold_build2 (chain->op, chain->rslt_type, e1, e2);
1430 else
1431 return chain->inits[index];
1434 /* Returns a new temporary variable used for the I-th variable carrying
1435 value of REF. The variable's uid is marked in TMP_VARS. */
1437 static tree
1438 predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars)
1440 tree type = TREE_TYPE (ref);
1441 /* We never access the components of the temporary variable in predictive
1442 commoning. */
1443 tree var = create_tmp_reg (type, get_lsm_tmp_name (ref, i));
1444 bitmap_set_bit (tmp_vars, DECL_UID (var));
1445 return var;
1448 /* Creates the variables for CHAIN, as well as phi nodes for them and
1449 initialization on entry to LOOP. Uids of the newly created
1450 temporary variables are marked in TMP_VARS. */
1452 static void
1453 initialize_root_vars (struct loop *loop, chain_p chain, bitmap tmp_vars)
1455 unsigned i;
1456 unsigned n = chain->length;
1457 dref root = get_chain_root (chain);
1458 bool reuse_first = !chain->has_max_use_after;
1459 tree ref, init, var, next;
1460 gimple_phi phi;
1461 gimple_seq stmts;
1462 edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1464 /* If N == 0, then all the references are within the single iteration. And
1465 since this is an nonempty chain, reuse_first cannot be true. */
1466 gcc_assert (n > 0 || !reuse_first);
1468 chain->vars.create (n + 1);
1470 if (chain->type == CT_COMBINATION)
1471 ref = gimple_assign_lhs (root->stmt);
1472 else
1473 ref = DR_REF (root->ref);
1475 for (i = 0; i < n + (reuse_first ? 0 : 1); i++)
1477 var = predcom_tmp_var (ref, i, tmp_vars);
1478 chain->vars.quick_push (var);
1480 if (reuse_first)
1481 chain->vars.quick_push (chain->vars[0]);
1483 FOR_EACH_VEC_ELT (chain->vars, i, var)
1484 chain->vars[i] = make_ssa_name (var, NULL);
1486 for (i = 0; i < n; i++)
1488 var = chain->vars[i];
1489 next = chain->vars[i + 1];
1490 init = get_init_expr (chain, i);
1492 init = force_gimple_operand (init, &stmts, true, NULL_TREE);
1493 if (stmts)
1494 gsi_insert_seq_on_edge_immediate (entry, stmts);
1496 phi = create_phi_node (var, loop->header);
1497 add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
1498 add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
1502 /* Create the variables and initialization statement for root of chain
1503 CHAIN. Uids of the newly created temporary variables are marked
1504 in TMP_VARS. */
1506 static void
1507 initialize_root (struct loop *loop, chain_p chain, bitmap tmp_vars)
1509 dref root = get_chain_root (chain);
1510 bool in_lhs = (chain->type == CT_STORE_LOAD
1511 || chain->type == CT_COMBINATION);
1513 initialize_root_vars (loop, chain, tmp_vars);
1514 replace_ref_with (root->stmt,
1515 chain->vars[chain->length],
1516 true, in_lhs);
1519 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1520 initialization on entry to LOOP if necessary. The ssa name for the variable
1521 is stored in VARS. If WRITTEN is true, also a phi node to copy its value
1522 around the loop is created. Uid of the newly created temporary variable
1523 is marked in TMP_VARS. INITS is the list containing the (single)
1524 initializer. */
1526 static void
1527 initialize_root_vars_lm (struct loop *loop, dref root, bool written,
1528 vec<tree> *vars, vec<tree> inits,
1529 bitmap tmp_vars)
1531 unsigned i;
1532 tree ref = DR_REF (root->ref), init, var, next;
1533 gimple_seq stmts;
1534 gimple_phi phi;
1535 edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1537 /* Find the initializer for the variable, and check that it cannot
1538 trap. */
1539 init = inits[0];
1541 vars->create (written ? 2 : 1);
1542 var = predcom_tmp_var (ref, 0, tmp_vars);
1543 vars->quick_push (var);
1544 if (written)
1545 vars->quick_push ((*vars)[0]);
1547 FOR_EACH_VEC_ELT (*vars, i, var)
1548 (*vars)[i] = make_ssa_name (var, NULL);
1550 var = (*vars)[0];
1552 init = force_gimple_operand (init, &stmts, written, NULL_TREE);
1553 if (stmts)
1554 gsi_insert_seq_on_edge_immediate (entry, stmts);
1556 if (written)
1558 next = (*vars)[1];
1559 phi = create_phi_node (var, loop->header);
1560 add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
1561 add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
1563 else
1565 gimple init_stmt = gimple_build_assign (var, init);
1566 gsi_insert_on_edge_immediate (entry, init_stmt);
1571 /* Execute load motion for references in chain CHAIN. Uids of the newly
1572 created temporary variables are marked in TMP_VARS. */
1574 static void
1575 execute_load_motion (struct loop *loop, chain_p chain, bitmap tmp_vars)
1577 auto_vec<tree> vars;
1578 dref a;
1579 unsigned n_writes = 0, ridx, i;
1580 tree var;
1582 gcc_assert (chain->type == CT_INVARIANT);
1583 gcc_assert (!chain->combined);
1584 FOR_EACH_VEC_ELT (chain->refs, i, a)
1585 if (DR_IS_WRITE (a->ref))
1586 n_writes++;
1588 /* If there are no reads in the loop, there is nothing to do. */
1589 if (n_writes == chain->refs.length ())
1590 return;
1592 initialize_root_vars_lm (loop, get_chain_root (chain), n_writes > 0,
1593 &vars, chain->inits, tmp_vars);
1595 ridx = 0;
1596 FOR_EACH_VEC_ELT (chain->refs, i, a)
1598 bool is_read = DR_IS_READ (a->ref);
1600 if (DR_IS_WRITE (a->ref))
1602 n_writes--;
1603 if (n_writes)
1605 var = vars[0];
1606 var = make_ssa_name (SSA_NAME_VAR (var), NULL);
1607 vars[0] = var;
1609 else
1610 ridx = 1;
1613 replace_ref_with (a->stmt, vars[ridx],
1614 !is_read, !is_read);
1618 /* Returns the single statement in that NAME is used, excepting
1619 the looparound phi nodes contained in one of the chains. If there is no
1620 such statement, or more statements, NULL is returned. */
1622 static gimple
1623 single_nonlooparound_use (tree name)
1625 use_operand_p use;
1626 imm_use_iterator it;
1627 gimple stmt, ret = NULL;
1629 FOR_EACH_IMM_USE_FAST (use, it, name)
1631 stmt = USE_STMT (use);
1633 if (gimple_code (stmt) == GIMPLE_PHI)
1635 /* Ignore uses in looparound phi nodes. Uses in other phi nodes
1636 could not be processed anyway, so just fail for them. */
1637 if (bitmap_bit_p (looparound_phis,
1638 SSA_NAME_VERSION (PHI_RESULT (stmt))))
1639 continue;
1641 return NULL;
1643 else if (is_gimple_debug (stmt))
1644 continue;
1645 else if (ret != NULL)
1646 return NULL;
1647 else
1648 ret = stmt;
1651 return ret;
1654 /* Remove statement STMT, as well as the chain of assignments in that it is
1655 used. */
1657 static void
1658 remove_stmt (gimple stmt)
1660 tree name;
1661 gimple next;
1662 gimple_stmt_iterator psi;
1664 if (gimple_code (stmt) == GIMPLE_PHI)
1666 name = PHI_RESULT (stmt);
1667 next = single_nonlooparound_use (name);
1668 reset_debug_uses (stmt);
1669 psi = gsi_for_stmt (stmt);
1670 remove_phi_node (&psi, true);
1672 if (!next
1673 || !gimple_assign_ssa_name_copy_p (next)
1674 || gimple_assign_rhs1 (next) != name)
1675 return;
1677 stmt = next;
1680 while (1)
1682 gimple_stmt_iterator bsi;
1684 bsi = gsi_for_stmt (stmt);
1686 name = gimple_assign_lhs (stmt);
1687 gcc_assert (TREE_CODE (name) == SSA_NAME);
1689 next = single_nonlooparound_use (name);
1690 reset_debug_uses (stmt);
1692 unlink_stmt_vdef (stmt);
1693 gsi_remove (&bsi, true);
1694 release_defs (stmt);
1696 if (!next
1697 || !gimple_assign_ssa_name_copy_p (next)
1698 || gimple_assign_rhs1 (next) != name)
1699 return;
1701 stmt = next;
1705 /* Perform the predictive commoning optimization for a chain CHAIN.
1706 Uids of the newly created temporary variables are marked in TMP_VARS.*/
1708 static void
1709 execute_pred_commoning_chain (struct loop *loop, chain_p chain,
1710 bitmap tmp_vars)
1712 unsigned i;
1713 dref a;
1714 tree var;
1716 if (chain->combined)
1718 /* For combined chains, just remove the statements that are used to
1719 compute the values of the expression (except for the root one). */
1720 for (i = 1; chain->refs.iterate (i, &a); i++)
1721 remove_stmt (a->stmt);
1723 else
1725 /* For non-combined chains, set up the variables that hold its value,
1726 and replace the uses of the original references by these
1727 variables. */
1728 initialize_root (loop, chain, tmp_vars);
1729 for (i = 1; chain->refs.iterate (i, &a); i++)
1731 var = chain->vars[chain->length - a->distance];
1732 replace_ref_with (a->stmt, var, false, false);
1737 /* Determines the unroll factor necessary to remove as many temporary variable
1738 copies as possible. CHAINS is the list of chains that will be
1739 optimized. */
1741 static unsigned
1742 determine_unroll_factor (vec<chain_p> chains)
1744 chain_p chain;
1745 unsigned factor = 1, af, nfactor, i;
1746 unsigned max = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
1748 FOR_EACH_VEC_ELT (chains, i, chain)
1750 if (chain->type == CT_INVARIANT || chain->combined)
1751 continue;
1753 /* The best unroll factor for this chain is equal to the number of
1754 temporary variables that we create for it. */
1755 af = chain->length;
1756 if (chain->has_max_use_after)
1757 af++;
1759 nfactor = factor * af / gcd (factor, af);
1760 if (nfactor <= max)
1761 factor = nfactor;
1764 return factor;
1767 /* Perform the predictive commoning optimization for CHAINS.
1768 Uids of the newly created temporary variables are marked in TMP_VARS. */
1770 static void
1771 execute_pred_commoning (struct loop *loop, vec<chain_p> chains,
1772 bitmap tmp_vars)
1774 chain_p chain;
1775 unsigned i;
1777 FOR_EACH_VEC_ELT (chains, i, chain)
1779 if (chain->type == CT_INVARIANT)
1780 execute_load_motion (loop, chain, tmp_vars);
1781 else
1782 execute_pred_commoning_chain (loop, chain, tmp_vars);
1785 update_ssa (TODO_update_ssa_only_virtuals);
1788 /* For each reference in CHAINS, if its defining statement is
1789 phi node, record the ssa name that is defined by it. */
1791 static void
1792 replace_phis_by_defined_names (vec<chain_p> chains)
1794 chain_p chain;
1795 dref a;
1796 unsigned i, j;
1798 FOR_EACH_VEC_ELT (chains, i, chain)
1799 FOR_EACH_VEC_ELT (chain->refs, j, a)
1801 if (gimple_code (a->stmt) == GIMPLE_PHI)
1803 a->name_defined_by_phi = PHI_RESULT (a->stmt);
1804 a->stmt = NULL;
1809 /* For each reference in CHAINS, if name_defined_by_phi is not
1810 NULL, use it to set the stmt field. */
1812 static void
1813 replace_names_by_phis (vec<chain_p> chains)
1815 chain_p chain;
1816 dref a;
1817 unsigned i, j;
1819 FOR_EACH_VEC_ELT (chains, i, chain)
1820 FOR_EACH_VEC_ELT (chain->refs, j, a)
1821 if (a->stmt == NULL)
1823 a->stmt = SSA_NAME_DEF_STMT (a->name_defined_by_phi);
1824 gcc_assert (gimple_code (a->stmt) == GIMPLE_PHI);
1825 a->name_defined_by_phi = NULL_TREE;
1829 /* Wrapper over execute_pred_commoning, to pass it as a callback
1830 to tree_transform_and_unroll_loop. */
1832 struct epcc_data
1834 vec<chain_p> chains;
1835 bitmap tmp_vars;
1838 static void
1839 execute_pred_commoning_cbck (struct loop *loop, void *data)
1841 struct epcc_data *const dta = (struct epcc_data *) data;
1843 /* Restore phi nodes that were replaced by ssa names before
1844 tree_transform_and_unroll_loop (see detailed description in
1845 tree_predictive_commoning_loop). */
1846 replace_names_by_phis (dta->chains);
1847 execute_pred_commoning (loop, dta->chains, dta->tmp_vars);
1850 /* Base NAME and all the names in the chain of phi nodes that use it
1851 on variable VAR. The phi nodes are recognized by being in the copies of
1852 the header of the LOOP. */
1854 static void
1855 base_names_in_chain_on (struct loop *loop, tree name, tree var)
1857 gimple stmt, phi;
1858 imm_use_iterator iter;
1860 replace_ssa_name_symbol (name, var);
1862 while (1)
1864 phi = NULL;
1865 FOR_EACH_IMM_USE_STMT (stmt, iter, name)
1867 if (gimple_code (stmt) == GIMPLE_PHI
1868 && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1870 phi = stmt;
1871 BREAK_FROM_IMM_USE_STMT (iter);
1874 if (!phi)
1875 return;
1877 name = PHI_RESULT (phi);
1878 replace_ssa_name_symbol (name, var);
1882 /* Given an unrolled LOOP after predictive commoning, remove the
1883 register copies arising from phi nodes by changing the base
1884 variables of SSA names. TMP_VARS is the set of the temporary variables
1885 for those we want to perform this. */
1887 static void
1888 eliminate_temp_copies (struct loop *loop, bitmap tmp_vars)
1890 edge e;
1891 gimple_phi phi;
1892 gimple stmt;
1893 tree name, use, var;
1894 gimple_phi_iterator psi;
1896 e = loop_latch_edge (loop);
1897 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1899 phi = psi.phi ();
1900 name = PHI_RESULT (phi);
1901 var = SSA_NAME_VAR (name);
1902 if (!var || !bitmap_bit_p (tmp_vars, DECL_UID (var)))
1903 continue;
1904 use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1905 gcc_assert (TREE_CODE (use) == SSA_NAME);
1907 /* Base all the ssa names in the ud and du chain of NAME on VAR. */
1908 stmt = SSA_NAME_DEF_STMT (use);
1909 while (gimple_code (stmt) == GIMPLE_PHI
1910 /* In case we could not unroll the loop enough to eliminate
1911 all copies, we may reach the loop header before the defining
1912 statement (in that case, some register copies will be present
1913 in loop latch in the final code, corresponding to the newly
1914 created looparound phi nodes). */
1915 && gimple_bb (stmt) != loop->header)
1917 gcc_assert (single_pred_p (gimple_bb (stmt)));
1918 use = PHI_ARG_DEF (stmt, 0);
1919 stmt = SSA_NAME_DEF_STMT (use);
1922 base_names_in_chain_on (loop, use, var);
1926 /* Returns true if CHAIN is suitable to be combined. */
1928 static bool
1929 chain_can_be_combined_p (chain_p chain)
1931 return (!chain->combined
1932 && (chain->type == CT_LOAD || chain->type == CT_COMBINATION));
1935 /* Returns the modify statement that uses NAME. Skips over assignment
1936 statements, NAME is replaced with the actual name used in the returned
1937 statement. */
1939 static gimple
1940 find_use_stmt (tree *name)
1942 gimple stmt;
1943 tree rhs, lhs;
1945 /* Skip over assignments. */
1946 while (1)
1948 stmt = single_nonlooparound_use (*name);
1949 if (!stmt)
1950 return NULL;
1952 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1953 return NULL;
1955 lhs = gimple_assign_lhs (stmt);
1956 if (TREE_CODE (lhs) != SSA_NAME)
1957 return NULL;
1959 if (gimple_assign_copy_p (stmt))
1961 rhs = gimple_assign_rhs1 (stmt);
1962 if (rhs != *name)
1963 return NULL;
1965 *name = lhs;
1967 else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
1968 == GIMPLE_BINARY_RHS)
1969 return stmt;
1970 else
1971 return NULL;
1975 /* Returns true if we may perform reassociation for operation CODE in TYPE. */
1977 static bool
1978 may_reassociate_p (tree type, enum tree_code code)
1980 if (FLOAT_TYPE_P (type)
1981 && !flag_unsafe_math_optimizations)
1982 return false;
1984 return (commutative_tree_code (code)
1985 && associative_tree_code (code));
1988 /* If the operation used in STMT is associative and commutative, go through the
1989 tree of the same operations and returns its root. Distance to the root
1990 is stored in DISTANCE. */
1992 static gimple
1993 find_associative_operation_root (gimple stmt, unsigned *distance)
1995 tree lhs;
1996 gimple next;
1997 enum tree_code code = gimple_assign_rhs_code (stmt);
1998 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
1999 unsigned dist = 0;
2001 if (!may_reassociate_p (type, code))
2002 return NULL;
2004 while (1)
2006 lhs = gimple_assign_lhs (stmt);
2007 gcc_assert (TREE_CODE (lhs) == SSA_NAME);
2009 next = find_use_stmt (&lhs);
2010 if (!next
2011 || gimple_assign_rhs_code (next) != code)
2012 break;
2014 stmt = next;
2015 dist++;
2018 if (distance)
2019 *distance = dist;
2020 return stmt;
2023 /* Returns the common statement in that NAME1 and NAME2 have a use. If there
2024 is no such statement, returns NULL_TREE. In case the operation used on
2025 NAME1 and NAME2 is associative and commutative, returns the root of the
2026 tree formed by this operation instead of the statement that uses NAME1 or
2027 NAME2. */
2029 static gimple
2030 find_common_use_stmt (tree *name1, tree *name2)
2032 gimple stmt1, stmt2;
2034 stmt1 = find_use_stmt (name1);
2035 if (!stmt1)
2036 return NULL;
2038 stmt2 = find_use_stmt (name2);
2039 if (!stmt2)
2040 return NULL;
2042 if (stmt1 == stmt2)
2043 return stmt1;
2045 stmt1 = find_associative_operation_root (stmt1, NULL);
2046 if (!stmt1)
2047 return NULL;
2048 stmt2 = find_associative_operation_root (stmt2, NULL);
2049 if (!stmt2)
2050 return NULL;
2052 return (stmt1 == stmt2 ? stmt1 : NULL);
2055 /* Checks whether R1 and R2 are combined together using CODE, with the result
2056 in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2057 if it is true. If CODE is ERROR_MARK, set these values instead. */
2059 static bool
2060 combinable_refs_p (dref r1, dref r2,
2061 enum tree_code *code, bool *swap, tree *rslt_type)
2063 enum tree_code acode;
2064 bool aswap;
2065 tree atype;
2066 tree name1, name2;
2067 gimple stmt;
2069 name1 = name_for_ref (r1);
2070 name2 = name_for_ref (r2);
2071 gcc_assert (name1 != NULL_TREE && name2 != NULL_TREE);
2073 stmt = find_common_use_stmt (&name1, &name2);
2075 if (!stmt
2076 /* A simple post-dominance check - make sure the combination
2077 is executed under the same condition as the references. */
2078 || (gimple_bb (stmt) != gimple_bb (r1->stmt)
2079 && gimple_bb (stmt) != gimple_bb (r2->stmt)))
2080 return false;
2082 acode = gimple_assign_rhs_code (stmt);
2083 aswap = (!commutative_tree_code (acode)
2084 && gimple_assign_rhs1 (stmt) != name1);
2085 atype = TREE_TYPE (gimple_assign_lhs (stmt));
2087 if (*code == ERROR_MARK)
2089 *code = acode;
2090 *swap = aswap;
2091 *rslt_type = atype;
2092 return true;
2095 return (*code == acode
2096 && *swap == aswap
2097 && *rslt_type == atype);
2100 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2101 an assignment of the remaining operand. */
2103 static void
2104 remove_name_from_operation (gimple stmt, tree op)
2106 tree other_op;
2107 gimple_stmt_iterator si;
2109 gcc_assert (is_gimple_assign (stmt));
2111 if (gimple_assign_rhs1 (stmt) == op)
2112 other_op = gimple_assign_rhs2 (stmt);
2113 else
2114 other_op = gimple_assign_rhs1 (stmt);
2116 si = gsi_for_stmt (stmt);
2117 gimple_assign_set_rhs_from_tree (&si, other_op);
2119 /* We should not have reallocated STMT. */
2120 gcc_assert (gsi_stmt (si) == stmt);
2122 update_stmt (stmt);
2125 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2126 are combined in a single statement, and returns this statement. */
2128 static gimple
2129 reassociate_to_the_same_stmt (tree name1, tree name2)
2131 gimple stmt1, stmt2, root1, root2, s1, s2;
2132 gimple new_stmt, tmp_stmt;
2133 tree new_name, tmp_name, var, r1, r2;
2134 unsigned dist1, dist2;
2135 enum tree_code code;
2136 tree type = TREE_TYPE (name1);
2137 gimple_stmt_iterator bsi;
2139 stmt1 = find_use_stmt (&name1);
2140 stmt2 = find_use_stmt (&name2);
2141 root1 = find_associative_operation_root (stmt1, &dist1);
2142 root2 = find_associative_operation_root (stmt2, &dist2);
2143 code = gimple_assign_rhs_code (stmt1);
2145 gcc_assert (root1 && root2 && root1 == root2
2146 && code == gimple_assign_rhs_code (stmt2));
2148 /* Find the root of the nearest expression in that both NAME1 and NAME2
2149 are used. */
2150 r1 = name1;
2151 s1 = stmt1;
2152 r2 = name2;
2153 s2 = stmt2;
2155 while (dist1 > dist2)
2157 s1 = find_use_stmt (&r1);
2158 r1 = gimple_assign_lhs (s1);
2159 dist1--;
2161 while (dist2 > dist1)
2163 s2 = find_use_stmt (&r2);
2164 r2 = gimple_assign_lhs (s2);
2165 dist2--;
2168 while (s1 != s2)
2170 s1 = find_use_stmt (&r1);
2171 r1 = gimple_assign_lhs (s1);
2172 s2 = find_use_stmt (&r2);
2173 r2 = gimple_assign_lhs (s2);
2176 /* Remove NAME1 and NAME2 from the statements in that they are used
2177 currently. */
2178 remove_name_from_operation (stmt1, name1);
2179 remove_name_from_operation (stmt2, name2);
2181 /* Insert the new statement combining NAME1 and NAME2 before S1, and
2182 combine it with the rhs of S1. */
2183 var = create_tmp_reg (type, "predreastmp");
2184 new_name = make_ssa_name (var, NULL);
2185 new_stmt = gimple_build_assign_with_ops (code, new_name, name1, name2);
2187 var = create_tmp_reg (type, "predreastmp");
2188 tmp_name = make_ssa_name (var, NULL);
2190 /* Rhs of S1 may now be either a binary expression with operation
2191 CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2192 so that name1 or name2 was removed from it). */
2193 tmp_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (s1),
2194 tmp_name,
2195 gimple_assign_rhs1 (s1),
2196 gimple_assign_rhs2 (s1));
2198 bsi = gsi_for_stmt (s1);
2199 gimple_assign_set_rhs_with_ops (&bsi, code, new_name, tmp_name);
2200 s1 = gsi_stmt (bsi);
2201 update_stmt (s1);
2203 gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
2204 gsi_insert_before (&bsi, tmp_stmt, GSI_SAME_STMT);
2206 return new_stmt;
2209 /* Returns the statement that combines references R1 and R2. In case R1
2210 and R2 are not used in the same statement, but they are used with an
2211 associative and commutative operation in the same expression, reassociate
2212 the expression so that they are used in the same statement. */
2214 static gimple
2215 stmt_combining_refs (dref r1, dref r2)
2217 gimple stmt1, stmt2;
2218 tree name1 = name_for_ref (r1);
2219 tree name2 = name_for_ref (r2);
2221 stmt1 = find_use_stmt (&name1);
2222 stmt2 = find_use_stmt (&name2);
2223 if (stmt1 == stmt2)
2224 return stmt1;
2226 return reassociate_to_the_same_stmt (name1, name2);
2229 /* Tries to combine chains CH1 and CH2 together. If this succeeds, the
2230 description of the new chain is returned, otherwise we return NULL. */
2232 static chain_p
2233 combine_chains (chain_p ch1, chain_p ch2)
2235 dref r1, r2, nw;
2236 enum tree_code op = ERROR_MARK;
2237 bool swap = false;
2238 chain_p new_chain;
2239 unsigned i;
2240 gimple root_stmt;
2241 tree rslt_type = NULL_TREE;
2243 if (ch1 == ch2)
2244 return NULL;
2245 if (ch1->length != ch2->length)
2246 return NULL;
2248 if (ch1->refs.length () != ch2->refs.length ())
2249 return NULL;
2251 for (i = 0; (ch1->refs.iterate (i, &r1)
2252 && ch2->refs.iterate (i, &r2)); i++)
2254 if (r1->distance != r2->distance)
2255 return NULL;
2257 if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type))
2258 return NULL;
2261 if (swap)
2263 chain_p tmp = ch1;
2264 ch1 = ch2;
2265 ch2 = tmp;
2268 new_chain = XCNEW (struct chain);
2269 new_chain->type = CT_COMBINATION;
2270 new_chain->op = op;
2271 new_chain->ch1 = ch1;
2272 new_chain->ch2 = ch2;
2273 new_chain->rslt_type = rslt_type;
2274 new_chain->length = ch1->length;
2276 for (i = 0; (ch1->refs.iterate (i, &r1)
2277 && ch2->refs.iterate (i, &r2)); i++)
2279 nw = XCNEW (struct dref_d);
2280 nw->stmt = stmt_combining_refs (r1, r2);
2281 nw->distance = r1->distance;
2283 new_chain->refs.safe_push (nw);
2286 new_chain->has_max_use_after = false;
2287 root_stmt = get_chain_root (new_chain)->stmt;
2288 for (i = 1; new_chain->refs.iterate (i, &nw); i++)
2290 if (nw->distance == new_chain->length
2291 && !stmt_dominates_stmt_p (nw->stmt, root_stmt))
2293 new_chain->has_max_use_after = true;
2294 break;
2298 ch1->combined = true;
2299 ch2->combined = true;
2300 return new_chain;
2303 /* Try to combine the CHAINS. */
2305 static void
2306 try_combine_chains (vec<chain_p> *chains)
2308 unsigned i, j;
2309 chain_p ch1, ch2, cch;
2310 auto_vec<chain_p> worklist;
2312 FOR_EACH_VEC_ELT (*chains, i, ch1)
2313 if (chain_can_be_combined_p (ch1))
2314 worklist.safe_push (ch1);
2316 while (!worklist.is_empty ())
2318 ch1 = worklist.pop ();
2319 if (!chain_can_be_combined_p (ch1))
2320 continue;
2322 FOR_EACH_VEC_ELT (*chains, j, ch2)
2324 if (!chain_can_be_combined_p (ch2))
2325 continue;
2327 cch = combine_chains (ch1, ch2);
2328 if (cch)
2330 worklist.safe_push (cch);
2331 chains->safe_push (cch);
2332 break;
2338 /* Prepare initializers for CHAIN in LOOP. Returns false if this is
2339 impossible because one of these initializers may trap, true otherwise. */
2341 static bool
2342 prepare_initializers_chain (struct loop *loop, chain_p chain)
2344 unsigned i, n = (chain->type == CT_INVARIANT) ? 1 : chain->length;
2345 struct data_reference *dr = get_chain_root (chain)->ref;
2346 tree init;
2347 gimple_seq stmts;
2348 dref laref;
2349 edge entry = loop_preheader_edge (loop);
2351 /* Find the initializers for the variables, and check that they cannot
2352 trap. */
2353 chain->inits.create (n);
2354 for (i = 0; i < n; i++)
2355 chain->inits.quick_push (NULL_TREE);
2357 /* If we have replaced some looparound phi nodes, use their initializers
2358 instead of creating our own. */
2359 FOR_EACH_VEC_ELT (chain->refs, i, laref)
2361 if (gimple_code (laref->stmt) != GIMPLE_PHI)
2362 continue;
2364 gcc_assert (laref->distance > 0);
2365 chain->inits[n - laref->distance]
2366 = PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry);
2369 for (i = 0; i < n; i++)
2371 if (chain->inits[i] != NULL_TREE)
2372 continue;
2374 init = ref_at_iteration (dr, (int) i - n, &stmts);
2375 if (!chain->all_always_accessed && tree_could_trap_p (init))
2376 return false;
2378 if (stmts)
2379 gsi_insert_seq_on_edge_immediate (entry, stmts);
2381 chain->inits[i] = init;
2384 return true;
2387 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2388 be used because the initializers might trap. */
2390 static void
2391 prepare_initializers (struct loop *loop, vec<chain_p> chains)
2393 chain_p chain;
2394 unsigned i;
2396 for (i = 0; i < chains.length (); )
2398 chain = chains[i];
2399 if (prepare_initializers_chain (loop, chain))
2400 i++;
2401 else
2403 release_chain (chain);
2404 chains.unordered_remove (i);
2409 /* Performs predictive commoning for LOOP. Returns true if LOOP was
2410 unrolled. */
2412 static bool
2413 tree_predictive_commoning_loop (struct loop *loop)
2415 vec<data_reference_p> datarefs;
2416 vec<ddr_p> dependences;
2417 struct component *components;
2418 vec<chain_p> chains = vNULL;
2419 unsigned unroll_factor;
2420 struct tree_niter_desc desc;
2421 bool unroll = false;
2422 edge exit;
2423 bitmap tmp_vars;
2425 if (dump_file && (dump_flags & TDF_DETAILS))
2426 fprintf (dump_file, "Processing loop %d\n", loop->num);
2428 /* Find the data references and split them into components according to their
2429 dependence relations. */
2430 auto_vec<loop_p, 3> loop_nest;
2431 dependences.create (10);
2432 datarefs.create (10);
2433 if (! compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs,
2434 &dependences))
2436 if (dump_file && (dump_flags & TDF_DETAILS))
2437 fprintf (dump_file, "Cannot analyze data dependencies\n");
2438 free_data_refs (datarefs);
2439 free_dependence_relations (dependences);
2440 return false;
2443 if (dump_file && (dump_flags & TDF_DETAILS))
2444 dump_data_dependence_relations (dump_file, dependences);
2446 components = split_data_refs_to_components (loop, datarefs, dependences);
2447 loop_nest.release ();
2448 free_dependence_relations (dependences);
2449 if (!components)
2451 free_data_refs (datarefs);
2452 free_affine_expand_cache (&name_expansions);
2453 return false;
2456 if (dump_file && (dump_flags & TDF_DETAILS))
2458 fprintf (dump_file, "Initial state:\n\n");
2459 dump_components (dump_file, components);
2462 /* Find the suitable components and split them into chains. */
2463 components = filter_suitable_components (loop, components);
2465 tmp_vars = BITMAP_ALLOC (NULL);
2466 looparound_phis = BITMAP_ALLOC (NULL);
2467 determine_roots (loop, components, &chains);
2468 release_components (components);
2470 if (!chains.exists ())
2472 if (dump_file && (dump_flags & TDF_DETAILS))
2473 fprintf (dump_file,
2474 "Predictive commoning failed: no suitable chains\n");
2475 goto end;
2477 prepare_initializers (loop, chains);
2479 /* Try to combine the chains that are always worked with together. */
2480 try_combine_chains (&chains);
2482 if (dump_file && (dump_flags & TDF_DETAILS))
2484 fprintf (dump_file, "Before commoning:\n\n");
2485 dump_chains (dump_file, chains);
2488 /* Determine the unroll factor, and if the loop should be unrolled, ensure
2489 that its number of iterations is divisible by the factor. */
2490 unroll_factor = determine_unroll_factor (chains);
2491 scev_reset ();
2492 unroll = (unroll_factor > 1
2493 && can_unroll_loop_p (loop, unroll_factor, &desc));
2494 exit = single_dom_exit (loop);
2496 /* Execute the predictive commoning transformations, and possibly unroll the
2497 loop. */
2498 if (unroll)
2500 struct epcc_data dta;
2502 if (dump_file && (dump_flags & TDF_DETAILS))
2503 fprintf (dump_file, "Unrolling %u times.\n", unroll_factor);
2505 dta.chains = chains;
2506 dta.tmp_vars = tmp_vars;
2508 update_ssa (TODO_update_ssa_only_virtuals);
2510 /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2511 execute_pred_commoning_cbck is called may cause phi nodes to be
2512 reallocated, which is a problem since CHAINS may point to these
2513 statements. To fix this, we store the ssa names defined by the
2514 phi nodes here instead of the phi nodes themselves, and restore
2515 the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
2516 replace_phis_by_defined_names (chains);
2518 tree_transform_and_unroll_loop (loop, unroll_factor, exit, &desc,
2519 execute_pred_commoning_cbck, &dta);
2520 eliminate_temp_copies (loop, tmp_vars);
2522 else
2524 if (dump_file && (dump_flags & TDF_DETAILS))
2525 fprintf (dump_file,
2526 "Executing predictive commoning without unrolling.\n");
2527 execute_pred_commoning (loop, chains, tmp_vars);
2530 end: ;
2531 release_chains (chains);
2532 free_data_refs (datarefs);
2533 BITMAP_FREE (tmp_vars);
2534 BITMAP_FREE (looparound_phis);
2536 free_affine_expand_cache (&name_expansions);
2538 return unroll;
2541 /* Runs predictive commoning. */
2543 unsigned
2544 tree_predictive_commoning (void)
2546 bool unrolled = false;
2547 struct loop *loop;
2548 unsigned ret = 0;
2550 initialize_original_copy_tables ();
2551 FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
2552 if (optimize_loop_for_speed_p (loop))
2554 unrolled |= tree_predictive_commoning_loop (loop);
2557 if (unrolled)
2559 scev_reset ();
2560 ret = TODO_cleanup_cfg;
2562 free_original_copy_tables ();
2564 return ret;
2567 /* Predictive commoning Pass. */
2569 static unsigned
2570 run_tree_predictive_commoning (struct function *fun)
2572 if (number_of_loops (fun) <= 1)
2573 return 0;
2575 return tree_predictive_commoning ();
2578 namespace {
2580 const pass_data pass_data_predcom =
2582 GIMPLE_PASS, /* type */
2583 "pcom", /* name */
2584 OPTGROUP_LOOP, /* optinfo_flags */
2585 TV_PREDCOM, /* tv_id */
2586 PROP_cfg, /* properties_required */
2587 0, /* properties_provided */
2588 0, /* properties_destroyed */
2589 0, /* todo_flags_start */
2590 TODO_update_ssa_only_virtuals, /* todo_flags_finish */
2593 class pass_predcom : public gimple_opt_pass
2595 public:
2596 pass_predcom (gcc::context *ctxt)
2597 : gimple_opt_pass (pass_data_predcom, ctxt)
2600 /* opt_pass methods: */
2601 virtual bool gate (function *) { return flag_predictive_commoning != 0; }
2602 virtual unsigned int execute (function *fun)
2604 return run_tree_predictive_commoning (fun);
2607 }; // class pass_predcom
2609 } // anon namespace
2611 gimple_opt_pass *
2612 make_pass_predcom (gcc::context *ctxt)
2614 return new pass_predcom (ctxt);