* tree-if-conv.c: Fix various typos in comments.
[official-gcc.git] / gcc / tree-predcom.c
blobea0d30cfa0d1b54f50b966bce0052ac219203740
1 /* Predictive commoning.
2 Copyright (C) 2005-2015 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 "backend.h"
191 #include "predict.h"
192 #include "tree.h"
193 #include "gimple.h"
194 #include "rtl.h"
195 #include "ssa.h"
196 #include "alias.h"
197 #include "fold-const.h"
198 #include "tm_p.h"
199 #include "cfgloop.h"
200 #include "internal-fn.h"
201 #include "tree-eh.h"
202 #include "gimplify.h"
203 #include "gimple-iterator.h"
204 #include "gimplify-me.h"
205 #include "tree-ssa-loop-ivopts.h"
206 #include "tree-ssa-loop-manip.h"
207 #include "tree-ssa-loop-niter.h"
208 #include "tree-ssa-loop.h"
209 #include "tree-into-ssa.h"
210 #include "flags.h"
211 #include "insn-config.h"
212 #include "expmed.h"
213 #include "dojump.h"
214 #include "explow.h"
215 #include "calls.h"
216 #include "emit-rtl.h"
217 #include "varasm.h"
218 #include "stmt.h"
219 #include "expr.h"
220 #include "tree-dfa.h"
221 #include "tree-ssa.h"
222 #include "tree-data-ref.h"
223 #include "tree-scalar-evolution.h"
224 #include "tree-chrec.h"
225 #include "params.h"
226 #include "gimple-pretty-print.h"
227 #include "tree-pass.h"
228 #include "tree-affine.h"
229 #include "tree-inline.h"
230 #include "wide-int-print.h"
232 /* The maximum number of iterations between the considered memory
233 references. */
235 #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
237 /* Data references (or phi nodes that carry data reference values across
238 loop iterations). */
240 typedef struct dref_d
242 /* The reference itself. */
243 struct data_reference *ref;
245 /* The statement in that the reference appears. */
246 gimple stmt;
248 /* In case that STMT is a phi node, this field is set to the SSA name
249 defined by it in replace_phis_by_defined_names (in order to avoid
250 pointing to phi node that got reallocated in the meantime). */
251 tree name_defined_by_phi;
253 /* Distance of the reference from the root of the chain (in number of
254 iterations of the loop). */
255 unsigned distance;
257 /* Number of iterations offset from the first reference in the component. */
258 widest_int offset;
260 /* Number of the reference in a component, in dominance ordering. */
261 unsigned pos;
263 /* True if the memory reference is always accessed when the loop is
264 entered. */
265 unsigned always_accessed : 1;
266 } *dref;
269 /* Type of the chain of the references. */
271 enum chain_type
273 /* The addresses of the references in the chain are constant. */
274 CT_INVARIANT,
276 /* There are only loads in the chain. */
277 CT_LOAD,
279 /* Root of the chain is store, the rest are loads. */
280 CT_STORE_LOAD,
282 /* A combination of two chains. */
283 CT_COMBINATION
286 /* Chains of data references. */
288 typedef struct chain
290 /* Type of the chain. */
291 enum chain_type type;
293 /* For combination chains, the operator and the two chains that are
294 combined, and the type of the result. */
295 enum tree_code op;
296 tree rslt_type;
297 struct chain *ch1, *ch2;
299 /* The references in the chain. */
300 vec<dref> refs;
302 /* The maximum distance of the reference in the chain from the root. */
303 unsigned length;
305 /* The variables used to copy the value throughout iterations. */
306 vec<tree> vars;
308 /* Initializers for the variables. */
309 vec<tree> inits;
311 /* True if there is a use of a variable with the maximal distance
312 that comes after the root in the loop. */
313 unsigned has_max_use_after : 1;
315 /* True if all the memory references in the chain are always accessed. */
316 unsigned all_always_accessed : 1;
318 /* True if this chain was combined together with some other chain. */
319 unsigned combined : 1;
320 } *chain_p;
323 /* Describes the knowledge about the step of the memory references in
324 the component. */
326 enum ref_step_type
328 /* The step is zero. */
329 RS_INVARIANT,
331 /* The step is nonzero. */
332 RS_NONZERO,
334 /* The step may or may not be nonzero. */
335 RS_ANY
338 /* Components of the data dependence graph. */
340 struct component
342 /* The references in the component. */
343 vec<dref> refs;
345 /* What we know about the step of the references in the component. */
346 enum ref_step_type comp_step;
348 /* Next component in the list. */
349 struct component *next;
352 /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */
354 static bitmap looparound_phis;
356 /* Cache used by tree_to_aff_combination_expand. */
358 static hash_map<tree, name_expansion *> *name_expansions;
360 /* Dumps data reference REF to FILE. */
362 extern void dump_dref (FILE *, dref);
363 void
364 dump_dref (FILE *file, dref ref)
366 if (ref->ref)
368 fprintf (file, " ");
369 print_generic_expr (file, DR_REF (ref->ref), TDF_SLIM);
370 fprintf (file, " (id %u%s)\n", ref->pos,
371 DR_IS_READ (ref->ref) ? "" : ", write");
373 fprintf (file, " offset ");
374 print_decs (ref->offset, file);
375 fprintf (file, "\n");
377 fprintf (file, " distance %u\n", ref->distance);
379 else
381 if (gimple_code (ref->stmt) == GIMPLE_PHI)
382 fprintf (file, " looparound ref\n");
383 else
384 fprintf (file, " combination ref\n");
385 fprintf (file, " in statement ");
386 print_gimple_stmt (file, ref->stmt, 0, TDF_SLIM);
387 fprintf (file, "\n");
388 fprintf (file, " distance %u\n", ref->distance);
393 /* Dumps CHAIN to FILE. */
395 extern void dump_chain (FILE *, chain_p);
396 void
397 dump_chain (FILE *file, chain_p chain)
399 dref a;
400 const char *chain_type;
401 unsigned i;
402 tree var;
404 switch (chain->type)
406 case CT_INVARIANT:
407 chain_type = "Load motion";
408 break;
410 case CT_LOAD:
411 chain_type = "Loads-only";
412 break;
414 case CT_STORE_LOAD:
415 chain_type = "Store-loads";
416 break;
418 case CT_COMBINATION:
419 chain_type = "Combination";
420 break;
422 default:
423 gcc_unreachable ();
426 fprintf (file, "%s chain %p%s\n", chain_type, (void *) chain,
427 chain->combined ? " (combined)" : "");
428 if (chain->type != CT_INVARIANT)
429 fprintf (file, " max distance %u%s\n", chain->length,
430 chain->has_max_use_after ? "" : ", may reuse first");
432 if (chain->type == CT_COMBINATION)
434 fprintf (file, " equal to %p %s %p in type ",
435 (void *) chain->ch1, op_symbol_code (chain->op),
436 (void *) chain->ch2);
437 print_generic_expr (file, chain->rslt_type, TDF_SLIM);
438 fprintf (file, "\n");
441 if (chain->vars.exists ())
443 fprintf (file, " vars");
444 FOR_EACH_VEC_ELT (chain->vars, i, var)
446 fprintf (file, " ");
447 print_generic_expr (file, var, TDF_SLIM);
449 fprintf (file, "\n");
452 if (chain->inits.exists ())
454 fprintf (file, " inits");
455 FOR_EACH_VEC_ELT (chain->inits, i, var)
457 fprintf (file, " ");
458 print_generic_expr (file, var, TDF_SLIM);
460 fprintf (file, "\n");
463 fprintf (file, " references:\n");
464 FOR_EACH_VEC_ELT (chain->refs, i, a)
465 dump_dref (file, a);
467 fprintf (file, "\n");
470 /* Dumps CHAINS to FILE. */
472 extern void dump_chains (FILE *, vec<chain_p> );
473 void
474 dump_chains (FILE *file, vec<chain_p> chains)
476 chain_p chain;
477 unsigned i;
479 FOR_EACH_VEC_ELT (chains, i, chain)
480 dump_chain (file, chain);
483 /* Dumps COMP to FILE. */
485 extern void dump_component (FILE *, struct component *);
486 void
487 dump_component (FILE *file, struct component *comp)
489 dref a;
490 unsigned i;
492 fprintf (file, "Component%s:\n",
493 comp->comp_step == RS_INVARIANT ? " (invariant)" : "");
494 FOR_EACH_VEC_ELT (comp->refs, i, a)
495 dump_dref (file, a);
496 fprintf (file, "\n");
499 /* Dumps COMPS to FILE. */
501 extern void dump_components (FILE *, struct component *);
502 void
503 dump_components (FILE *file, struct component *comps)
505 struct component *comp;
507 for (comp = comps; comp; comp = comp->next)
508 dump_component (file, comp);
511 /* Frees a chain CHAIN. */
513 static void
514 release_chain (chain_p chain)
516 dref ref;
517 unsigned i;
519 if (chain == NULL)
520 return;
522 FOR_EACH_VEC_ELT (chain->refs, i, ref)
523 free (ref);
525 chain->refs.release ();
526 chain->vars.release ();
527 chain->inits.release ();
529 free (chain);
532 /* Frees CHAINS. */
534 static void
535 release_chains (vec<chain_p> chains)
537 unsigned i;
538 chain_p chain;
540 FOR_EACH_VEC_ELT (chains, i, chain)
541 release_chain (chain);
542 chains.release ();
545 /* Frees a component COMP. */
547 static void
548 release_component (struct component *comp)
550 comp->refs.release ();
551 free (comp);
554 /* Frees list of components COMPS. */
556 static void
557 release_components (struct component *comps)
559 struct component *act, *next;
561 for (act = comps; act; act = next)
563 next = act->next;
564 release_component (act);
568 /* Finds a root of tree given by FATHERS containing A, and performs path
569 shortening. */
571 static unsigned
572 component_of (unsigned fathers[], unsigned a)
574 unsigned root, n;
576 for (root = a; root != fathers[root]; root = fathers[root])
577 continue;
579 for (; a != root; a = n)
581 n = fathers[a];
582 fathers[a] = root;
585 return root;
588 /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the
589 components, A and B are components to merge. */
591 static void
592 merge_comps (unsigned fathers[], unsigned sizes[], unsigned a, unsigned b)
594 unsigned ca = component_of (fathers, a);
595 unsigned cb = component_of (fathers, b);
597 if (ca == cb)
598 return;
600 if (sizes[ca] < sizes[cb])
602 sizes[cb] += sizes[ca];
603 fathers[ca] = cb;
605 else
607 sizes[ca] += sizes[cb];
608 fathers[cb] = ca;
612 /* Returns true if A is a reference that is suitable for predictive commoning
613 in the innermost loop that contains it. REF_STEP is set according to the
614 step of the reference A. */
616 static bool
617 suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step)
619 tree ref = DR_REF (a), step = DR_STEP (a);
621 if (!step
622 || TREE_THIS_VOLATILE (ref)
623 || !is_gimple_reg_type (TREE_TYPE (ref))
624 || tree_could_throw_p (ref))
625 return false;
627 if (integer_zerop (step))
628 *ref_step = RS_INVARIANT;
629 else if (integer_nonzerop (step))
630 *ref_step = RS_NONZERO;
631 else
632 *ref_step = RS_ANY;
634 return true;
637 /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
639 static void
640 aff_combination_dr_offset (struct data_reference *dr, aff_tree *offset)
642 tree type = TREE_TYPE (DR_OFFSET (dr));
643 aff_tree delta;
645 tree_to_aff_combination_expand (DR_OFFSET (dr), type, offset,
646 &name_expansions);
647 aff_combination_const (&delta, type, wi::to_widest (DR_INIT (dr)));
648 aff_combination_add (offset, &delta);
651 /* Determines number of iterations of the innermost enclosing loop before B
652 refers to exactly the same location as A and stores it to OFF. If A and
653 B do not have the same step, they never meet, or anything else fails,
654 returns false, otherwise returns true. Both A and B are assumed to
655 satisfy suitable_reference_p. */
657 static bool
658 determine_offset (struct data_reference *a, struct data_reference *b,
659 widest_int *off)
661 aff_tree diff, baseb, step;
662 tree typea, typeb;
664 /* Check that both the references access the location in the same type. */
665 typea = TREE_TYPE (DR_REF (a));
666 typeb = TREE_TYPE (DR_REF (b));
667 if (!useless_type_conversion_p (typeb, typea))
668 return false;
670 /* Check whether the base address and the step of both references is the
671 same. */
672 if (!operand_equal_p (DR_STEP (a), DR_STEP (b), 0)
673 || !operand_equal_p (DR_BASE_ADDRESS (a), DR_BASE_ADDRESS (b), 0))
674 return false;
676 if (integer_zerop (DR_STEP (a)))
678 /* If the references have loop invariant address, check that they access
679 exactly the same location. */
680 *off = 0;
681 return (operand_equal_p (DR_OFFSET (a), DR_OFFSET (b), 0)
682 && operand_equal_p (DR_INIT (a), DR_INIT (b), 0));
685 /* Compare the offsets of the addresses, and check whether the difference
686 is a multiple of step. */
687 aff_combination_dr_offset (a, &diff);
688 aff_combination_dr_offset (b, &baseb);
689 aff_combination_scale (&baseb, -1);
690 aff_combination_add (&diff, &baseb);
692 tree_to_aff_combination_expand (DR_STEP (a), TREE_TYPE (DR_STEP (a)),
693 &step, &name_expansions);
694 return aff_combination_constant_multiple_p (&diff, &step, off);
697 /* Returns the last basic block in LOOP for that we are sure that
698 it is executed whenever the loop is entered. */
700 static basic_block
701 last_always_executed_block (struct loop *loop)
703 unsigned i;
704 vec<edge> exits = get_loop_exit_edges (loop);
705 edge ex;
706 basic_block last = loop->latch;
708 FOR_EACH_VEC_ELT (exits, i, ex)
709 last = nearest_common_dominator (CDI_DOMINATORS, last, ex->src);
710 exits.release ();
712 return last;
715 /* Splits dependence graph on DATAREFS described by DEPENDS to components. */
717 static struct component *
718 split_data_refs_to_components (struct loop *loop,
719 vec<data_reference_p> datarefs,
720 vec<ddr_p> depends)
722 unsigned i, n = datarefs.length ();
723 unsigned ca, ia, ib, bad;
724 unsigned *comp_father = XNEWVEC (unsigned, n + 1);
725 unsigned *comp_size = XNEWVEC (unsigned, n + 1);
726 struct component **comps;
727 struct data_reference *dr, *dra, *drb;
728 struct data_dependence_relation *ddr;
729 struct component *comp_list = NULL, *comp;
730 dref dataref;
731 basic_block last_always_executed = last_always_executed_block (loop);
733 FOR_EACH_VEC_ELT (datarefs, i, dr)
735 if (!DR_REF (dr))
737 /* A fake reference for call or asm_expr that may clobber memory;
738 just fail. */
739 goto end;
741 /* predcom pass isn't prepared to handle calls with data references. */
742 if (is_gimple_call (DR_STMT (dr)))
743 goto end;
744 dr->aux = (void *) (size_t) i;
745 comp_father[i] = i;
746 comp_size[i] = 1;
749 /* A component reserved for the "bad" data references. */
750 comp_father[n] = n;
751 comp_size[n] = 1;
753 FOR_EACH_VEC_ELT (datarefs, i, dr)
755 enum ref_step_type dummy;
757 if (!suitable_reference_p (dr, &dummy))
759 ia = (unsigned) (size_t) dr->aux;
760 merge_comps (comp_father, comp_size, n, ia);
764 FOR_EACH_VEC_ELT (depends, i, ddr)
766 widest_int dummy_off;
768 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
769 continue;
771 dra = DDR_A (ddr);
772 drb = DDR_B (ddr);
773 ia = component_of (comp_father, (unsigned) (size_t) dra->aux);
774 ib = component_of (comp_father, (unsigned) (size_t) drb->aux);
775 if (ia == ib)
776 continue;
778 bad = component_of (comp_father, n);
780 /* If both A and B are reads, we may ignore unsuitable dependences. */
781 if (DR_IS_READ (dra) && DR_IS_READ (drb))
783 if (ia == bad || ib == bad
784 || !determine_offset (dra, drb, &dummy_off))
785 continue;
787 /* If A is read and B write or vice versa and there is unsuitable
788 dependence, instead of merging both components into a component
789 that will certainly not pass suitable_component_p, just put the
790 read into bad component, perhaps at least the write together with
791 all the other data refs in it's component will be optimizable. */
792 else if (DR_IS_READ (dra) && ib != bad)
794 if (ia == bad)
795 continue;
796 else if (!determine_offset (dra, drb, &dummy_off))
798 merge_comps (comp_father, comp_size, bad, ia);
799 continue;
802 else if (DR_IS_READ (drb) && ia != bad)
804 if (ib == bad)
805 continue;
806 else if (!determine_offset (dra, drb, &dummy_off))
808 merge_comps (comp_father, comp_size, bad, ib);
809 continue;
813 merge_comps (comp_father, comp_size, ia, ib);
816 comps = XCNEWVEC (struct component *, n);
817 bad = component_of (comp_father, n);
818 FOR_EACH_VEC_ELT (datarefs, i, dr)
820 ia = (unsigned) (size_t) dr->aux;
821 ca = component_of (comp_father, ia);
822 if (ca == bad)
823 continue;
825 comp = comps[ca];
826 if (!comp)
828 comp = XCNEW (struct component);
829 comp->refs.create (comp_size[ca]);
830 comps[ca] = comp;
833 dataref = XCNEW (struct dref_d);
834 dataref->ref = dr;
835 dataref->stmt = DR_STMT (dr);
836 dataref->offset = 0;
837 dataref->distance = 0;
839 dataref->always_accessed
840 = dominated_by_p (CDI_DOMINATORS, last_always_executed,
841 gimple_bb (dataref->stmt));
842 dataref->pos = comp->refs.length ();
843 comp->refs.quick_push (dataref);
846 for (i = 0; i < n; i++)
848 comp = comps[i];
849 if (comp)
851 comp->next = comp_list;
852 comp_list = comp;
855 free (comps);
857 end:
858 free (comp_father);
859 free (comp_size);
860 return comp_list;
863 /* Returns true if the component COMP satisfies the conditions
864 described in 2) at the beginning of this file. LOOP is the current
865 loop. */
867 static bool
868 suitable_component_p (struct loop *loop, struct component *comp)
870 unsigned i;
871 dref a, first;
872 basic_block ba, bp = loop->header;
873 bool ok, has_write = false;
875 FOR_EACH_VEC_ELT (comp->refs, i, a)
877 ba = gimple_bb (a->stmt);
879 if (!just_once_each_iteration_p (loop, ba))
880 return false;
882 gcc_assert (dominated_by_p (CDI_DOMINATORS, ba, bp));
883 bp = ba;
885 if (DR_IS_WRITE (a->ref))
886 has_write = true;
889 first = comp->refs[0];
890 ok = suitable_reference_p (first->ref, &comp->comp_step);
891 gcc_assert (ok);
892 first->offset = 0;
894 for (i = 1; comp->refs.iterate (i, &a); i++)
896 if (!determine_offset (first->ref, a->ref, &a->offset))
897 return false;
899 #ifdef ENABLE_CHECKING
901 enum ref_step_type a_step;
902 ok = suitable_reference_p (a->ref, &a_step);
903 gcc_assert (ok && a_step == comp->comp_step);
905 #endif
908 /* If there is a write inside the component, we must know whether the
909 step is nonzero or not -- we would not otherwise be able to recognize
910 whether the value accessed by reads comes from the OFFSET-th iteration
911 or the previous one. */
912 if (has_write && comp->comp_step == RS_ANY)
913 return false;
915 return true;
918 /* Check the conditions on references inside each of components COMPS,
919 and remove the unsuitable components from the list. The new list
920 of components is returned. The conditions are described in 2) at
921 the beginning of this file. LOOP is the current loop. */
923 static struct component *
924 filter_suitable_components (struct loop *loop, struct component *comps)
926 struct component **comp, *act;
928 for (comp = &comps; *comp; )
930 act = *comp;
931 if (suitable_component_p (loop, act))
932 comp = &act->next;
933 else
935 dref ref;
936 unsigned i;
938 *comp = act->next;
939 FOR_EACH_VEC_ELT (act->refs, i, ref)
940 free (ref);
941 release_component (act);
945 return comps;
948 /* Compares two drefs A and B by their offset and position. Callback for
949 qsort. */
951 static int
952 order_drefs (const void *a, const void *b)
954 const dref *const da = (const dref *) a;
955 const dref *const db = (const dref *) b;
956 int offcmp = wi::cmps ((*da)->offset, (*db)->offset);
958 if (offcmp != 0)
959 return offcmp;
961 return (*da)->pos - (*db)->pos;
964 /* Returns root of the CHAIN. */
966 static inline dref
967 get_chain_root (chain_p chain)
969 return chain->refs[0];
972 /* Adds REF to the chain CHAIN. */
974 static void
975 add_ref_to_chain (chain_p chain, dref ref)
977 dref root = get_chain_root (chain);
979 gcc_assert (wi::les_p (root->offset, ref->offset));
980 widest_int dist = ref->offset - root->offset;
981 if (wi::leu_p (MAX_DISTANCE, dist))
983 free (ref);
984 return;
986 gcc_assert (wi::fits_uhwi_p (dist));
988 chain->refs.safe_push (ref);
990 ref->distance = dist.to_uhwi ();
992 if (ref->distance >= chain->length)
994 chain->length = ref->distance;
995 chain->has_max_use_after = false;
998 if (ref->distance == chain->length
999 && ref->pos > root->pos)
1000 chain->has_max_use_after = true;
1002 chain->all_always_accessed &= ref->always_accessed;
1005 /* Returns the chain for invariant component COMP. */
1007 static chain_p
1008 make_invariant_chain (struct component *comp)
1010 chain_p chain = XCNEW (struct chain);
1011 unsigned i;
1012 dref ref;
1014 chain->type = CT_INVARIANT;
1016 chain->all_always_accessed = true;
1018 FOR_EACH_VEC_ELT (comp->refs, i, ref)
1020 chain->refs.safe_push (ref);
1021 chain->all_always_accessed &= ref->always_accessed;
1024 return chain;
1027 /* Make a new chain rooted at REF. */
1029 static chain_p
1030 make_rooted_chain (dref ref)
1032 chain_p chain = XCNEW (struct chain);
1034 chain->type = DR_IS_READ (ref->ref) ? CT_LOAD : CT_STORE_LOAD;
1036 chain->refs.safe_push (ref);
1037 chain->all_always_accessed = ref->always_accessed;
1039 ref->distance = 0;
1041 return chain;
1044 /* Returns true if CHAIN is not trivial. */
1046 static bool
1047 nontrivial_chain_p (chain_p chain)
1049 return chain != NULL && chain->refs.length () > 1;
1052 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1053 is no such name. */
1055 static tree
1056 name_for_ref (dref ref)
1058 tree name;
1060 if (is_gimple_assign (ref->stmt))
1062 if (!ref->ref || DR_IS_READ (ref->ref))
1063 name = gimple_assign_lhs (ref->stmt);
1064 else
1065 name = gimple_assign_rhs1 (ref->stmt);
1067 else
1068 name = PHI_RESULT (ref->stmt);
1070 return (TREE_CODE (name) == SSA_NAME ? name : NULL_TREE);
1073 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1074 iterations of the innermost enclosing loop). */
1076 static bool
1077 valid_initializer_p (struct data_reference *ref,
1078 unsigned distance, struct data_reference *root)
1080 aff_tree diff, base, step;
1081 widest_int off;
1083 /* Both REF and ROOT must be accessing the same object. */
1084 if (!operand_equal_p (DR_BASE_ADDRESS (ref), DR_BASE_ADDRESS (root), 0))
1085 return false;
1087 /* The initializer is defined outside of loop, hence its address must be
1088 invariant inside the loop. */
1089 gcc_assert (integer_zerop (DR_STEP (ref)));
1091 /* If the address of the reference is invariant, initializer must access
1092 exactly the same location. */
1093 if (integer_zerop (DR_STEP (root)))
1094 return (operand_equal_p (DR_OFFSET (ref), DR_OFFSET (root), 0)
1095 && operand_equal_p (DR_INIT (ref), DR_INIT (root), 0));
1097 /* Verify that this index of REF is equal to the root's index at
1098 -DISTANCE-th iteration. */
1099 aff_combination_dr_offset (root, &diff);
1100 aff_combination_dr_offset (ref, &base);
1101 aff_combination_scale (&base, -1);
1102 aff_combination_add (&diff, &base);
1104 tree_to_aff_combination_expand (DR_STEP (root), TREE_TYPE (DR_STEP (root)),
1105 &step, &name_expansions);
1106 if (!aff_combination_constant_multiple_p (&diff, &step, &off))
1107 return false;
1109 if (off != distance)
1110 return false;
1112 return true;
1115 /* Finds looparound phi node of LOOP that copies the value of REF, and if its
1116 initial value is correct (equal to initial value of REF shifted by one
1117 iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT
1118 is the root of the current chain. */
1120 static gphi *
1121 find_looparound_phi (struct loop *loop, dref ref, dref root)
1123 tree name, init, init_ref;
1124 gphi *phi = NULL;
1125 gimple init_stmt;
1126 edge latch = loop_latch_edge (loop);
1127 struct data_reference init_dr;
1128 gphi_iterator psi;
1130 if (is_gimple_assign (ref->stmt))
1132 if (DR_IS_READ (ref->ref))
1133 name = gimple_assign_lhs (ref->stmt);
1134 else
1135 name = gimple_assign_rhs1 (ref->stmt);
1137 else
1138 name = PHI_RESULT (ref->stmt);
1139 if (!name)
1140 return NULL;
1142 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1144 phi = psi.phi ();
1145 if (PHI_ARG_DEF_FROM_EDGE (phi, latch) == name)
1146 break;
1149 if (gsi_end_p (psi))
1150 return NULL;
1152 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1153 if (TREE_CODE (init) != SSA_NAME)
1154 return NULL;
1155 init_stmt = SSA_NAME_DEF_STMT (init);
1156 if (gimple_code (init_stmt) != GIMPLE_ASSIGN)
1157 return NULL;
1158 gcc_assert (gimple_assign_lhs (init_stmt) == init);
1160 init_ref = gimple_assign_rhs1 (init_stmt);
1161 if (!REFERENCE_CLASS_P (init_ref)
1162 && !DECL_P (init_ref))
1163 return NULL;
1165 /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1166 loop enclosing PHI). */
1167 memset (&init_dr, 0, sizeof (struct data_reference));
1168 DR_REF (&init_dr) = init_ref;
1169 DR_STMT (&init_dr) = phi;
1170 if (!dr_analyze_innermost (&init_dr, loop))
1171 return NULL;
1173 if (!valid_initializer_p (&init_dr, ref->distance + 1, root->ref))
1174 return NULL;
1176 return phi;
1179 /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1181 static void
1182 insert_looparound_copy (chain_p chain, dref ref, gphi *phi)
1184 dref nw = XCNEW (struct dref_d), aref;
1185 unsigned i;
1187 nw->stmt = phi;
1188 nw->distance = ref->distance + 1;
1189 nw->always_accessed = 1;
1191 FOR_EACH_VEC_ELT (chain->refs, i, aref)
1192 if (aref->distance >= nw->distance)
1193 break;
1194 chain->refs.safe_insert (i, nw);
1196 if (nw->distance > chain->length)
1198 chain->length = nw->distance;
1199 chain->has_max_use_after = false;
1203 /* For references in CHAIN that are copied around the LOOP (created previously
1204 by PRE, or by user), add the results of such copies to the chain. This
1205 enables us to remove the copies by unrolling, and may need less registers
1206 (also, it may allow us to combine chains together). */
1208 static void
1209 add_looparound_copies (struct loop *loop, chain_p chain)
1211 unsigned i;
1212 dref ref, root = get_chain_root (chain);
1213 gphi *phi;
1215 FOR_EACH_VEC_ELT (chain->refs, i, ref)
1217 phi = find_looparound_phi (loop, ref, root);
1218 if (!phi)
1219 continue;
1221 bitmap_set_bit (looparound_phis, SSA_NAME_VERSION (PHI_RESULT (phi)));
1222 insert_looparound_copy (chain, ref, phi);
1226 /* Find roots of the values and determine distances in the component COMP.
1227 The references are redistributed into CHAINS. LOOP is the current
1228 loop. */
1230 static void
1231 determine_roots_comp (struct loop *loop,
1232 struct component *comp,
1233 vec<chain_p> *chains)
1235 unsigned i;
1236 dref a;
1237 chain_p chain = NULL;
1238 widest_int last_ofs = 0;
1240 /* Invariants are handled specially. */
1241 if (comp->comp_step == RS_INVARIANT)
1243 chain = make_invariant_chain (comp);
1244 chains->safe_push (chain);
1245 return;
1248 comp->refs.qsort (order_drefs);
1250 FOR_EACH_VEC_ELT (comp->refs, i, a)
1252 if (!chain || DR_IS_WRITE (a->ref)
1253 || wi::leu_p (MAX_DISTANCE, a->offset - last_ofs))
1255 if (nontrivial_chain_p (chain))
1257 add_looparound_copies (loop, chain);
1258 chains->safe_push (chain);
1260 else
1261 release_chain (chain);
1262 chain = make_rooted_chain (a);
1263 last_ofs = a->offset;
1264 continue;
1267 add_ref_to_chain (chain, a);
1270 if (nontrivial_chain_p (chain))
1272 add_looparound_copies (loop, chain);
1273 chains->safe_push (chain);
1275 else
1276 release_chain (chain);
1279 /* Find roots of the values and determine distances in components COMPS, and
1280 separates the references to CHAINS. LOOP is the current loop. */
1282 static void
1283 determine_roots (struct loop *loop,
1284 struct component *comps, vec<chain_p> *chains)
1286 struct component *comp;
1288 for (comp = comps; comp; comp = comp->next)
1289 determine_roots_comp (loop, comp, chains);
1292 /* Replace the reference in statement STMT with temporary variable
1293 NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of
1294 the reference in the statement. IN_LHS is true if the reference
1295 is in the lhs of STMT, false if it is in rhs. */
1297 static void
1298 replace_ref_with (gimple stmt, tree new_tree, bool set, bool in_lhs)
1300 tree val;
1301 gassign *new_stmt;
1302 gimple_stmt_iterator bsi, psi;
1304 if (gimple_code (stmt) == GIMPLE_PHI)
1306 gcc_assert (!in_lhs && !set);
1308 val = PHI_RESULT (stmt);
1309 bsi = gsi_after_labels (gimple_bb (stmt));
1310 psi = gsi_for_stmt (stmt);
1311 remove_phi_node (&psi, false);
1313 /* Turn the phi node into GIMPLE_ASSIGN. */
1314 new_stmt = gimple_build_assign (val, new_tree);
1315 gsi_insert_before (&bsi, new_stmt, GSI_NEW_STMT);
1316 return;
1319 /* Since the reference is of gimple_reg type, it should only
1320 appear as lhs or rhs of modify statement. */
1321 gcc_assert (is_gimple_assign (stmt));
1323 bsi = gsi_for_stmt (stmt);
1325 /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */
1326 if (!set)
1328 gcc_assert (!in_lhs);
1329 gimple_assign_set_rhs_from_tree (&bsi, new_tree);
1330 stmt = gsi_stmt (bsi);
1331 update_stmt (stmt);
1332 return;
1335 if (in_lhs)
1337 /* We have statement
1339 OLD = VAL
1341 If OLD is a memory reference, then VAL is gimple_val, and we transform
1342 this to
1344 OLD = VAL
1345 NEW = VAL
1347 Otherwise, we are replacing a combination chain,
1348 VAL is the expression that performs the combination, and OLD is an
1349 SSA name. In this case, we transform the assignment to
1351 OLD = VAL
1352 NEW = OLD
1356 val = gimple_assign_lhs (stmt);
1357 if (TREE_CODE (val) != SSA_NAME)
1359 val = gimple_assign_rhs1 (stmt);
1360 gcc_assert (gimple_assign_single_p (stmt));
1361 if (TREE_CLOBBER_P (val))
1362 val = get_or_create_ssa_default_def (cfun, SSA_NAME_VAR (new_tree));
1363 else
1364 gcc_assert (gimple_assign_copy_p (stmt));
1367 else
1369 /* VAL = OLD
1371 is transformed to
1373 VAL = OLD
1374 NEW = VAL */
1376 val = gimple_assign_lhs (stmt);
1379 new_stmt = gimple_build_assign (new_tree, unshare_expr (val));
1380 gsi_insert_after (&bsi, new_stmt, GSI_NEW_STMT);
1383 /* Returns a memory reference to DR in the ITER-th iteration of
1384 the loop it was analyzed in. Append init stmts to STMTS. */
1386 static tree
1387 ref_at_iteration (data_reference_p dr, int iter, gimple_seq *stmts)
1389 tree off = DR_OFFSET (dr);
1390 tree coff = DR_INIT (dr);
1391 if (iter == 0)
1393 else if (TREE_CODE (DR_STEP (dr)) == INTEGER_CST)
1394 coff = size_binop (PLUS_EXPR, coff,
1395 size_binop (MULT_EXPR, DR_STEP (dr), ssize_int (iter)));
1396 else
1397 off = size_binop (PLUS_EXPR, off,
1398 size_binop (MULT_EXPR, DR_STEP (dr), ssize_int (iter)));
1399 tree addr = fold_build_pointer_plus (DR_BASE_ADDRESS (dr), off);
1400 addr = force_gimple_operand_1 (unshare_expr (addr), stmts,
1401 is_gimple_mem_ref_addr, NULL_TREE);
1402 tree alias_ptr = fold_convert (reference_alias_ptr_type (DR_REF (dr)), coff);
1403 /* While data-ref analysis punts on bit offsets it still handles
1404 bitfield accesses at byte boundaries. Cope with that. Note that
1405 we cannot simply re-apply the outer COMPONENT_REF because the
1406 byte-granular portion of it is already applied via DR_INIT and
1407 DR_OFFSET, so simply build a BIT_FIELD_REF knowing that the bits
1408 start at offset zero. */
1409 if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
1410 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
1412 tree field = TREE_OPERAND (DR_REF (dr), 1);
1413 return build3 (BIT_FIELD_REF, TREE_TYPE (DR_REF (dr)),
1414 build2 (MEM_REF, DECL_BIT_FIELD_TYPE (field),
1415 addr, alias_ptr),
1416 DECL_SIZE (field), bitsize_zero_node);
1418 else
1419 return fold_build2 (MEM_REF, TREE_TYPE (DR_REF (dr)), addr, alias_ptr);
1422 /* Get the initialization expression for the INDEX-th temporary variable
1423 of CHAIN. */
1425 static tree
1426 get_init_expr (chain_p chain, unsigned index)
1428 if (chain->type == CT_COMBINATION)
1430 tree e1 = get_init_expr (chain->ch1, index);
1431 tree e2 = get_init_expr (chain->ch2, index);
1433 return fold_build2 (chain->op, chain->rslt_type, e1, e2);
1435 else
1436 return chain->inits[index];
1439 /* Returns a new temporary variable used for the I-th variable carrying
1440 value of REF. The variable's uid is marked in TMP_VARS. */
1442 static tree
1443 predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars)
1445 tree type = TREE_TYPE (ref);
1446 /* We never access the components of the temporary variable in predictive
1447 commoning. */
1448 tree var = create_tmp_reg (type, get_lsm_tmp_name (ref, i));
1449 bitmap_set_bit (tmp_vars, DECL_UID (var));
1450 return var;
1453 /* Creates the variables for CHAIN, as well as phi nodes for them and
1454 initialization on entry to LOOP. Uids of the newly created
1455 temporary variables are marked in TMP_VARS. */
1457 static void
1458 initialize_root_vars (struct loop *loop, chain_p chain, bitmap tmp_vars)
1460 unsigned i;
1461 unsigned n = chain->length;
1462 dref root = get_chain_root (chain);
1463 bool reuse_first = !chain->has_max_use_after;
1464 tree ref, init, var, next;
1465 gphi *phi;
1466 gimple_seq stmts;
1467 edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1469 /* If N == 0, then all the references are within the single iteration. And
1470 since this is an nonempty chain, reuse_first cannot be true. */
1471 gcc_assert (n > 0 || !reuse_first);
1473 chain->vars.create (n + 1);
1475 if (chain->type == CT_COMBINATION)
1476 ref = gimple_assign_lhs (root->stmt);
1477 else
1478 ref = DR_REF (root->ref);
1480 for (i = 0; i < n + (reuse_first ? 0 : 1); i++)
1482 var = predcom_tmp_var (ref, i, tmp_vars);
1483 chain->vars.quick_push (var);
1485 if (reuse_first)
1486 chain->vars.quick_push (chain->vars[0]);
1488 FOR_EACH_VEC_ELT (chain->vars, i, var)
1489 chain->vars[i] = make_ssa_name (var);
1491 for (i = 0; i < n; i++)
1493 var = chain->vars[i];
1494 next = chain->vars[i + 1];
1495 init = get_init_expr (chain, i);
1497 init = force_gimple_operand (init, &stmts, true, NULL_TREE);
1498 if (stmts)
1499 gsi_insert_seq_on_edge_immediate (entry, stmts);
1501 phi = create_phi_node (var, loop->header);
1502 add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
1503 add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
1507 /* Create the variables and initialization statement for root of chain
1508 CHAIN. Uids of the newly created temporary variables are marked
1509 in TMP_VARS. */
1511 static void
1512 initialize_root (struct loop *loop, chain_p chain, bitmap tmp_vars)
1514 dref root = get_chain_root (chain);
1515 bool in_lhs = (chain->type == CT_STORE_LOAD
1516 || chain->type == CT_COMBINATION);
1518 initialize_root_vars (loop, chain, tmp_vars);
1519 replace_ref_with (root->stmt,
1520 chain->vars[chain->length],
1521 true, in_lhs);
1524 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1525 initialization on entry to LOOP if necessary. The ssa name for the variable
1526 is stored in VARS. If WRITTEN is true, also a phi node to copy its value
1527 around the loop is created. Uid of the newly created temporary variable
1528 is marked in TMP_VARS. INITS is the list containing the (single)
1529 initializer. */
1531 static void
1532 initialize_root_vars_lm (struct loop *loop, dref root, bool written,
1533 vec<tree> *vars, vec<tree> inits,
1534 bitmap tmp_vars)
1536 unsigned i;
1537 tree ref = DR_REF (root->ref), init, var, next;
1538 gimple_seq stmts;
1539 gphi *phi;
1540 edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1542 /* Find the initializer for the variable, and check that it cannot
1543 trap. */
1544 init = inits[0];
1546 vars->create (written ? 2 : 1);
1547 var = predcom_tmp_var (ref, 0, tmp_vars);
1548 vars->quick_push (var);
1549 if (written)
1550 vars->quick_push ((*vars)[0]);
1552 FOR_EACH_VEC_ELT (*vars, i, var)
1553 (*vars)[i] = make_ssa_name (var);
1555 var = (*vars)[0];
1557 init = force_gimple_operand (init, &stmts, written, NULL_TREE);
1558 if (stmts)
1559 gsi_insert_seq_on_edge_immediate (entry, stmts);
1561 if (written)
1563 next = (*vars)[1];
1564 phi = create_phi_node (var, loop->header);
1565 add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
1566 add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
1568 else
1570 gassign *init_stmt = gimple_build_assign (var, init);
1571 gsi_insert_on_edge_immediate (entry, init_stmt);
1576 /* Execute load motion for references in chain CHAIN. Uids of the newly
1577 created temporary variables are marked in TMP_VARS. */
1579 static void
1580 execute_load_motion (struct loop *loop, chain_p chain, bitmap tmp_vars)
1582 auto_vec<tree> vars;
1583 dref a;
1584 unsigned n_writes = 0, ridx, i;
1585 tree var;
1587 gcc_assert (chain->type == CT_INVARIANT);
1588 gcc_assert (!chain->combined);
1589 FOR_EACH_VEC_ELT (chain->refs, i, a)
1590 if (DR_IS_WRITE (a->ref))
1591 n_writes++;
1593 /* If there are no reads in the loop, there is nothing to do. */
1594 if (n_writes == chain->refs.length ())
1595 return;
1597 initialize_root_vars_lm (loop, get_chain_root (chain), n_writes > 0,
1598 &vars, chain->inits, tmp_vars);
1600 ridx = 0;
1601 FOR_EACH_VEC_ELT (chain->refs, i, a)
1603 bool is_read = DR_IS_READ (a->ref);
1605 if (DR_IS_WRITE (a->ref))
1607 n_writes--;
1608 if (n_writes)
1610 var = vars[0];
1611 var = make_ssa_name (SSA_NAME_VAR (var));
1612 vars[0] = var;
1614 else
1615 ridx = 1;
1618 replace_ref_with (a->stmt, vars[ridx],
1619 !is_read, !is_read);
1623 /* Returns the single statement in that NAME is used, excepting
1624 the looparound phi nodes contained in one of the chains. If there is no
1625 such statement, or more statements, NULL is returned. */
1627 static gimple
1628 single_nonlooparound_use (tree name)
1630 use_operand_p use;
1631 imm_use_iterator it;
1632 gimple stmt, ret = NULL;
1634 FOR_EACH_IMM_USE_FAST (use, it, name)
1636 stmt = USE_STMT (use);
1638 if (gimple_code (stmt) == GIMPLE_PHI)
1640 /* Ignore uses in looparound phi nodes. Uses in other phi nodes
1641 could not be processed anyway, so just fail for them. */
1642 if (bitmap_bit_p (looparound_phis,
1643 SSA_NAME_VERSION (PHI_RESULT (stmt))))
1644 continue;
1646 return NULL;
1648 else if (is_gimple_debug (stmt))
1649 continue;
1650 else if (ret != NULL)
1651 return NULL;
1652 else
1653 ret = stmt;
1656 return ret;
1659 /* Remove statement STMT, as well as the chain of assignments in that it is
1660 used. */
1662 static void
1663 remove_stmt (gimple stmt)
1665 tree name;
1666 gimple next;
1667 gimple_stmt_iterator psi;
1669 if (gimple_code (stmt) == GIMPLE_PHI)
1671 name = PHI_RESULT (stmt);
1672 next = single_nonlooparound_use (name);
1673 reset_debug_uses (stmt);
1674 psi = gsi_for_stmt (stmt);
1675 remove_phi_node (&psi, true);
1677 if (!next
1678 || !gimple_assign_ssa_name_copy_p (next)
1679 || gimple_assign_rhs1 (next) != name)
1680 return;
1682 stmt = next;
1685 while (1)
1687 gimple_stmt_iterator bsi;
1689 bsi = gsi_for_stmt (stmt);
1691 name = gimple_assign_lhs (stmt);
1692 gcc_assert (TREE_CODE (name) == SSA_NAME);
1694 next = single_nonlooparound_use (name);
1695 reset_debug_uses (stmt);
1697 unlink_stmt_vdef (stmt);
1698 gsi_remove (&bsi, true);
1699 release_defs (stmt);
1701 if (!next
1702 || !gimple_assign_ssa_name_copy_p (next)
1703 || gimple_assign_rhs1 (next) != name)
1704 return;
1706 stmt = next;
1710 /* Perform the predictive commoning optimization for a chain CHAIN.
1711 Uids of the newly created temporary variables are marked in TMP_VARS.*/
1713 static void
1714 execute_pred_commoning_chain (struct loop *loop, chain_p chain,
1715 bitmap tmp_vars)
1717 unsigned i;
1718 dref a;
1719 tree var;
1721 if (chain->combined)
1723 /* For combined chains, just remove the statements that are used to
1724 compute the values of the expression (except for the root one).
1725 We delay this until after all chains are processed. */
1727 else
1729 /* For non-combined chains, set up the variables that hold its value,
1730 and replace the uses of the original references by these
1731 variables. */
1732 initialize_root (loop, chain, tmp_vars);
1733 for (i = 1; chain->refs.iterate (i, &a); i++)
1735 var = chain->vars[chain->length - a->distance];
1736 replace_ref_with (a->stmt, var, false, false);
1741 /* Determines the unroll factor necessary to remove as many temporary variable
1742 copies as possible. CHAINS is the list of chains that will be
1743 optimized. */
1745 static unsigned
1746 determine_unroll_factor (vec<chain_p> chains)
1748 chain_p chain;
1749 unsigned factor = 1, af, nfactor, i;
1750 unsigned max = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
1752 FOR_EACH_VEC_ELT (chains, i, chain)
1754 if (chain->type == CT_INVARIANT)
1755 continue;
1757 if (chain->combined)
1759 /* For combined chains, we can't handle unrolling if we replace
1760 looparound PHIs. */
1761 dref a;
1762 unsigned j;
1763 for (j = 1; chain->refs.iterate (j, &a); j++)
1764 if (gimple_code (a->stmt) == GIMPLE_PHI)
1765 return 1;
1766 continue;
1769 /* The best unroll factor for this chain is equal to the number of
1770 temporary variables that we create for it. */
1771 af = chain->length;
1772 if (chain->has_max_use_after)
1773 af++;
1775 nfactor = factor * af / gcd (factor, af);
1776 if (nfactor <= max)
1777 factor = nfactor;
1780 return factor;
1783 /* Perform the predictive commoning optimization for CHAINS.
1784 Uids of the newly created temporary variables are marked in TMP_VARS. */
1786 static void
1787 execute_pred_commoning (struct loop *loop, vec<chain_p> chains,
1788 bitmap tmp_vars)
1790 chain_p chain;
1791 unsigned i;
1793 FOR_EACH_VEC_ELT (chains, i, chain)
1795 if (chain->type == CT_INVARIANT)
1796 execute_load_motion (loop, chain, tmp_vars);
1797 else
1798 execute_pred_commoning_chain (loop, chain, tmp_vars);
1801 FOR_EACH_VEC_ELT (chains, i, chain)
1803 if (chain->type == CT_INVARIANT)
1805 else if (chain->combined)
1807 /* For combined chains, just remove the statements that are used to
1808 compute the values of the expression (except for the root one). */
1809 dref a;
1810 unsigned j;
1811 for (j = 1; chain->refs.iterate (j, &a); j++)
1812 remove_stmt (a->stmt);
1816 update_ssa (TODO_update_ssa_only_virtuals);
1819 /* For each reference in CHAINS, if its defining statement is
1820 phi node, record the ssa name that is defined by it. */
1822 static void
1823 replace_phis_by_defined_names (vec<chain_p> chains)
1825 chain_p chain;
1826 dref a;
1827 unsigned i, j;
1829 FOR_EACH_VEC_ELT (chains, i, chain)
1830 FOR_EACH_VEC_ELT (chain->refs, j, a)
1832 if (gimple_code (a->stmt) == GIMPLE_PHI)
1834 a->name_defined_by_phi = PHI_RESULT (a->stmt);
1835 a->stmt = NULL;
1840 /* For each reference in CHAINS, if name_defined_by_phi is not
1841 NULL, use it to set the stmt field. */
1843 static void
1844 replace_names_by_phis (vec<chain_p> chains)
1846 chain_p chain;
1847 dref a;
1848 unsigned i, j;
1850 FOR_EACH_VEC_ELT (chains, i, chain)
1851 FOR_EACH_VEC_ELT (chain->refs, j, a)
1852 if (a->stmt == NULL)
1854 a->stmt = SSA_NAME_DEF_STMT (a->name_defined_by_phi);
1855 gcc_assert (gimple_code (a->stmt) == GIMPLE_PHI);
1856 a->name_defined_by_phi = NULL_TREE;
1860 /* Wrapper over execute_pred_commoning, to pass it as a callback
1861 to tree_transform_and_unroll_loop. */
1863 struct epcc_data
1865 vec<chain_p> chains;
1866 bitmap tmp_vars;
1869 static void
1870 execute_pred_commoning_cbck (struct loop *loop, void *data)
1872 struct epcc_data *const dta = (struct epcc_data *) data;
1874 /* Restore phi nodes that were replaced by ssa names before
1875 tree_transform_and_unroll_loop (see detailed description in
1876 tree_predictive_commoning_loop). */
1877 replace_names_by_phis (dta->chains);
1878 execute_pred_commoning (loop, dta->chains, dta->tmp_vars);
1881 /* Base NAME and all the names in the chain of phi nodes that use it
1882 on variable VAR. The phi nodes are recognized by being in the copies of
1883 the header of the LOOP. */
1885 static void
1886 base_names_in_chain_on (struct loop *loop, tree name, tree var)
1888 gimple stmt, phi;
1889 imm_use_iterator iter;
1891 replace_ssa_name_symbol (name, var);
1893 while (1)
1895 phi = NULL;
1896 FOR_EACH_IMM_USE_STMT (stmt, iter, name)
1898 if (gimple_code (stmt) == GIMPLE_PHI
1899 && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1901 phi = stmt;
1902 BREAK_FROM_IMM_USE_STMT (iter);
1905 if (!phi)
1906 return;
1908 name = PHI_RESULT (phi);
1909 replace_ssa_name_symbol (name, var);
1913 /* Given an unrolled LOOP after predictive commoning, remove the
1914 register copies arising from phi nodes by changing the base
1915 variables of SSA names. TMP_VARS is the set of the temporary variables
1916 for those we want to perform this. */
1918 static void
1919 eliminate_temp_copies (struct loop *loop, bitmap tmp_vars)
1921 edge e;
1922 gphi *phi;
1923 gimple stmt;
1924 tree name, use, var;
1925 gphi_iterator psi;
1927 e = loop_latch_edge (loop);
1928 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1930 phi = psi.phi ();
1931 name = PHI_RESULT (phi);
1932 var = SSA_NAME_VAR (name);
1933 if (!var || !bitmap_bit_p (tmp_vars, DECL_UID (var)))
1934 continue;
1935 use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1936 gcc_assert (TREE_CODE (use) == SSA_NAME);
1938 /* Base all the ssa names in the ud and du chain of NAME on VAR. */
1939 stmt = SSA_NAME_DEF_STMT (use);
1940 while (gimple_code (stmt) == GIMPLE_PHI
1941 /* In case we could not unroll the loop enough to eliminate
1942 all copies, we may reach the loop header before the defining
1943 statement (in that case, some register copies will be present
1944 in loop latch in the final code, corresponding to the newly
1945 created looparound phi nodes). */
1946 && gimple_bb (stmt) != loop->header)
1948 gcc_assert (single_pred_p (gimple_bb (stmt)));
1949 use = PHI_ARG_DEF (stmt, 0);
1950 stmt = SSA_NAME_DEF_STMT (use);
1953 base_names_in_chain_on (loop, use, var);
1957 /* Returns true if CHAIN is suitable to be combined. */
1959 static bool
1960 chain_can_be_combined_p (chain_p chain)
1962 return (!chain->combined
1963 && (chain->type == CT_LOAD || chain->type == CT_COMBINATION));
1966 /* Returns the modify statement that uses NAME. Skips over assignment
1967 statements, NAME is replaced with the actual name used in the returned
1968 statement. */
1970 static gimple
1971 find_use_stmt (tree *name)
1973 gimple stmt;
1974 tree rhs, lhs;
1976 /* Skip over assignments. */
1977 while (1)
1979 stmt = single_nonlooparound_use (*name);
1980 if (!stmt)
1981 return NULL;
1983 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1984 return NULL;
1986 lhs = gimple_assign_lhs (stmt);
1987 if (TREE_CODE (lhs) != SSA_NAME)
1988 return NULL;
1990 if (gimple_assign_copy_p (stmt))
1992 rhs = gimple_assign_rhs1 (stmt);
1993 if (rhs != *name)
1994 return NULL;
1996 *name = lhs;
1998 else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
1999 == GIMPLE_BINARY_RHS)
2000 return stmt;
2001 else
2002 return NULL;
2006 /* Returns true if we may perform reassociation for operation CODE in TYPE. */
2008 static bool
2009 may_reassociate_p (tree type, enum tree_code code)
2011 if (FLOAT_TYPE_P (type)
2012 && !flag_unsafe_math_optimizations)
2013 return false;
2015 return (commutative_tree_code (code)
2016 && associative_tree_code (code));
2019 /* If the operation used in STMT is associative and commutative, go through the
2020 tree of the same operations and returns its root. Distance to the root
2021 is stored in DISTANCE. */
2023 static gimple
2024 find_associative_operation_root (gimple stmt, unsigned *distance)
2026 tree lhs;
2027 gimple next;
2028 enum tree_code code = gimple_assign_rhs_code (stmt);
2029 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
2030 unsigned dist = 0;
2032 if (!may_reassociate_p (type, code))
2033 return NULL;
2035 while (1)
2037 lhs = gimple_assign_lhs (stmt);
2038 gcc_assert (TREE_CODE (lhs) == SSA_NAME);
2040 next = find_use_stmt (&lhs);
2041 if (!next
2042 || gimple_assign_rhs_code (next) != code)
2043 break;
2045 stmt = next;
2046 dist++;
2049 if (distance)
2050 *distance = dist;
2051 return stmt;
2054 /* Returns the common statement in that NAME1 and NAME2 have a use. If there
2055 is no such statement, returns NULL_TREE. In case the operation used on
2056 NAME1 and NAME2 is associative and commutative, returns the root of the
2057 tree formed by this operation instead of the statement that uses NAME1 or
2058 NAME2. */
2060 static gimple
2061 find_common_use_stmt (tree *name1, tree *name2)
2063 gimple stmt1, stmt2;
2065 stmt1 = find_use_stmt (name1);
2066 if (!stmt1)
2067 return NULL;
2069 stmt2 = find_use_stmt (name2);
2070 if (!stmt2)
2071 return NULL;
2073 if (stmt1 == stmt2)
2074 return stmt1;
2076 stmt1 = find_associative_operation_root (stmt1, NULL);
2077 if (!stmt1)
2078 return NULL;
2079 stmt2 = find_associative_operation_root (stmt2, NULL);
2080 if (!stmt2)
2081 return NULL;
2083 return (stmt1 == stmt2 ? stmt1 : NULL);
2086 /* Checks whether R1 and R2 are combined together using CODE, with the result
2087 in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2088 if it is true. If CODE is ERROR_MARK, set these values instead. */
2090 static bool
2091 combinable_refs_p (dref r1, dref r2,
2092 enum tree_code *code, bool *swap, tree *rslt_type)
2094 enum tree_code acode;
2095 bool aswap;
2096 tree atype;
2097 tree name1, name2;
2098 gimple stmt;
2100 name1 = name_for_ref (r1);
2101 name2 = name_for_ref (r2);
2102 gcc_assert (name1 != NULL_TREE && name2 != NULL_TREE);
2104 stmt = find_common_use_stmt (&name1, &name2);
2106 if (!stmt
2107 /* A simple post-dominance check - make sure the combination
2108 is executed under the same condition as the references. */
2109 || (gimple_bb (stmt) != gimple_bb (r1->stmt)
2110 && gimple_bb (stmt) != gimple_bb (r2->stmt)))
2111 return false;
2113 acode = gimple_assign_rhs_code (stmt);
2114 aswap = (!commutative_tree_code (acode)
2115 && gimple_assign_rhs1 (stmt) != name1);
2116 atype = TREE_TYPE (gimple_assign_lhs (stmt));
2118 if (*code == ERROR_MARK)
2120 *code = acode;
2121 *swap = aswap;
2122 *rslt_type = atype;
2123 return true;
2126 return (*code == acode
2127 && *swap == aswap
2128 && *rslt_type == atype);
2131 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2132 an assignment of the remaining operand. */
2134 static void
2135 remove_name_from_operation (gimple stmt, tree op)
2137 tree other_op;
2138 gimple_stmt_iterator si;
2140 gcc_assert (is_gimple_assign (stmt));
2142 if (gimple_assign_rhs1 (stmt) == op)
2143 other_op = gimple_assign_rhs2 (stmt);
2144 else
2145 other_op = gimple_assign_rhs1 (stmt);
2147 si = gsi_for_stmt (stmt);
2148 gimple_assign_set_rhs_from_tree (&si, other_op);
2150 /* We should not have reallocated STMT. */
2151 gcc_assert (gsi_stmt (si) == stmt);
2153 update_stmt (stmt);
2156 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2157 are combined in a single statement, and returns this statement. */
2159 static gimple
2160 reassociate_to_the_same_stmt (tree name1, tree name2)
2162 gimple stmt1, stmt2, root1, root2, s1, s2;
2163 gassign *new_stmt, *tmp_stmt;
2164 tree new_name, tmp_name, var, r1, r2;
2165 unsigned dist1, dist2;
2166 enum tree_code code;
2167 tree type = TREE_TYPE (name1);
2168 gimple_stmt_iterator bsi;
2170 stmt1 = find_use_stmt (&name1);
2171 stmt2 = find_use_stmt (&name2);
2172 root1 = find_associative_operation_root (stmt1, &dist1);
2173 root2 = find_associative_operation_root (stmt2, &dist2);
2174 code = gimple_assign_rhs_code (stmt1);
2176 gcc_assert (root1 && root2 && root1 == root2
2177 && code == gimple_assign_rhs_code (stmt2));
2179 /* Find the root of the nearest expression in that both NAME1 and NAME2
2180 are used. */
2181 r1 = name1;
2182 s1 = stmt1;
2183 r2 = name2;
2184 s2 = stmt2;
2186 while (dist1 > dist2)
2188 s1 = find_use_stmt (&r1);
2189 r1 = gimple_assign_lhs (s1);
2190 dist1--;
2192 while (dist2 > dist1)
2194 s2 = find_use_stmt (&r2);
2195 r2 = gimple_assign_lhs (s2);
2196 dist2--;
2199 while (s1 != s2)
2201 s1 = find_use_stmt (&r1);
2202 r1 = gimple_assign_lhs (s1);
2203 s2 = find_use_stmt (&r2);
2204 r2 = gimple_assign_lhs (s2);
2207 /* Remove NAME1 and NAME2 from the statements in that they are used
2208 currently. */
2209 remove_name_from_operation (stmt1, name1);
2210 remove_name_from_operation (stmt2, name2);
2212 /* Insert the new statement combining NAME1 and NAME2 before S1, and
2213 combine it with the rhs of S1. */
2214 var = create_tmp_reg (type, "predreastmp");
2215 new_name = make_ssa_name (var);
2216 new_stmt = gimple_build_assign (new_name, code, name1, name2);
2218 var = create_tmp_reg (type, "predreastmp");
2219 tmp_name = make_ssa_name (var);
2221 /* Rhs of S1 may now be either a binary expression with operation
2222 CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2223 so that name1 or name2 was removed from it). */
2224 tmp_stmt = gimple_build_assign (tmp_name, gimple_assign_rhs_code (s1),
2225 gimple_assign_rhs1 (s1),
2226 gimple_assign_rhs2 (s1));
2228 bsi = gsi_for_stmt (s1);
2229 gimple_assign_set_rhs_with_ops (&bsi, code, new_name, tmp_name);
2230 s1 = gsi_stmt (bsi);
2231 update_stmt (s1);
2233 gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
2234 gsi_insert_before (&bsi, tmp_stmt, GSI_SAME_STMT);
2236 return new_stmt;
2239 /* Returns the statement that combines references R1 and R2. In case R1
2240 and R2 are not used in the same statement, but they are used with an
2241 associative and commutative operation in the same expression, reassociate
2242 the expression so that they are used in the same statement. */
2244 static gimple
2245 stmt_combining_refs (dref r1, dref r2)
2247 gimple stmt1, stmt2;
2248 tree name1 = name_for_ref (r1);
2249 tree name2 = name_for_ref (r2);
2251 stmt1 = find_use_stmt (&name1);
2252 stmt2 = find_use_stmt (&name2);
2253 if (stmt1 == stmt2)
2254 return stmt1;
2256 return reassociate_to_the_same_stmt (name1, name2);
2259 /* Tries to combine chains CH1 and CH2 together. If this succeeds, the
2260 description of the new chain is returned, otherwise we return NULL. */
2262 static chain_p
2263 combine_chains (chain_p ch1, chain_p ch2)
2265 dref r1, r2, nw;
2266 enum tree_code op = ERROR_MARK;
2267 bool swap = false;
2268 chain_p new_chain;
2269 unsigned i;
2270 gimple root_stmt;
2271 tree rslt_type = NULL_TREE;
2273 if (ch1 == ch2)
2274 return NULL;
2275 if (ch1->length != ch2->length)
2276 return NULL;
2278 if (ch1->refs.length () != ch2->refs.length ())
2279 return NULL;
2281 for (i = 0; (ch1->refs.iterate (i, &r1)
2282 && ch2->refs.iterate (i, &r2)); i++)
2284 if (r1->distance != r2->distance)
2285 return NULL;
2287 if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type))
2288 return NULL;
2291 if (swap)
2292 std::swap (ch1, ch2);
2294 new_chain = XCNEW (struct chain);
2295 new_chain->type = CT_COMBINATION;
2296 new_chain->op = op;
2297 new_chain->ch1 = ch1;
2298 new_chain->ch2 = ch2;
2299 new_chain->rslt_type = rslt_type;
2300 new_chain->length = ch1->length;
2302 for (i = 0; (ch1->refs.iterate (i, &r1)
2303 && ch2->refs.iterate (i, &r2)); i++)
2305 nw = XCNEW (struct dref_d);
2306 nw->stmt = stmt_combining_refs (r1, r2);
2307 nw->distance = r1->distance;
2309 new_chain->refs.safe_push (nw);
2312 new_chain->has_max_use_after = false;
2313 root_stmt = get_chain_root (new_chain)->stmt;
2314 for (i = 1; new_chain->refs.iterate (i, &nw); i++)
2316 if (nw->distance == new_chain->length
2317 && !stmt_dominates_stmt_p (nw->stmt, root_stmt))
2319 new_chain->has_max_use_after = true;
2320 break;
2324 ch1->combined = true;
2325 ch2->combined = true;
2326 return new_chain;
2329 /* Try to combine the CHAINS. */
2331 static void
2332 try_combine_chains (vec<chain_p> *chains)
2334 unsigned i, j;
2335 chain_p ch1, ch2, cch;
2336 auto_vec<chain_p> worklist;
2338 FOR_EACH_VEC_ELT (*chains, i, ch1)
2339 if (chain_can_be_combined_p (ch1))
2340 worklist.safe_push (ch1);
2342 while (!worklist.is_empty ())
2344 ch1 = worklist.pop ();
2345 if (!chain_can_be_combined_p (ch1))
2346 continue;
2348 FOR_EACH_VEC_ELT (*chains, j, ch2)
2350 if (!chain_can_be_combined_p (ch2))
2351 continue;
2353 cch = combine_chains (ch1, ch2);
2354 if (cch)
2356 worklist.safe_push (cch);
2357 chains->safe_push (cch);
2358 break;
2364 /* Prepare initializers for CHAIN in LOOP. Returns false if this is
2365 impossible because one of these initializers may trap, true otherwise. */
2367 static bool
2368 prepare_initializers_chain (struct loop *loop, chain_p chain)
2370 unsigned i, n = (chain->type == CT_INVARIANT) ? 1 : chain->length;
2371 struct data_reference *dr = get_chain_root (chain)->ref;
2372 tree init;
2373 dref laref;
2374 edge entry = loop_preheader_edge (loop);
2376 /* Find the initializers for the variables, and check that they cannot
2377 trap. */
2378 chain->inits.create (n);
2379 for (i = 0; i < n; i++)
2380 chain->inits.quick_push (NULL_TREE);
2382 /* If we have replaced some looparound phi nodes, use their initializers
2383 instead of creating our own. */
2384 FOR_EACH_VEC_ELT (chain->refs, i, laref)
2386 if (gimple_code (laref->stmt) != GIMPLE_PHI)
2387 continue;
2389 gcc_assert (laref->distance > 0);
2390 chain->inits[n - laref->distance]
2391 = PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry);
2394 for (i = 0; i < n; i++)
2396 gimple_seq stmts = NULL;
2398 if (chain->inits[i] != NULL_TREE)
2399 continue;
2401 init = ref_at_iteration (dr, (int) i - n, &stmts);
2402 if (!chain->all_always_accessed && tree_could_trap_p (init))
2404 gimple_seq_discard (stmts);
2405 return false;
2408 if (stmts)
2409 gsi_insert_seq_on_edge_immediate (entry, stmts);
2411 chain->inits[i] = init;
2414 return true;
2417 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2418 be used because the initializers might trap. */
2420 static void
2421 prepare_initializers (struct loop *loop, vec<chain_p> chains)
2423 chain_p chain;
2424 unsigned i;
2426 for (i = 0; i < chains.length (); )
2428 chain = chains[i];
2429 if (prepare_initializers_chain (loop, chain))
2430 i++;
2431 else
2433 release_chain (chain);
2434 chains.unordered_remove (i);
2439 /* Performs predictive commoning for LOOP. Returns true if LOOP was
2440 unrolled. */
2442 static bool
2443 tree_predictive_commoning_loop (struct loop *loop)
2445 vec<data_reference_p> datarefs;
2446 vec<ddr_p> dependences;
2447 struct component *components;
2448 vec<chain_p> chains = vNULL;
2449 unsigned unroll_factor;
2450 struct tree_niter_desc desc;
2451 bool unroll = false;
2452 edge exit;
2453 bitmap tmp_vars;
2455 if (dump_file && (dump_flags & TDF_DETAILS))
2456 fprintf (dump_file, "Processing loop %d\n", loop->num);
2458 /* Find the data references and split them into components according to their
2459 dependence relations. */
2460 auto_vec<loop_p, 3> loop_nest;
2461 dependences.create (10);
2462 datarefs.create (10);
2463 if (! compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs,
2464 &dependences))
2466 if (dump_file && (dump_flags & TDF_DETAILS))
2467 fprintf (dump_file, "Cannot analyze data dependencies\n");
2468 free_data_refs (datarefs);
2469 free_dependence_relations (dependences);
2470 return false;
2473 if (dump_file && (dump_flags & TDF_DETAILS))
2474 dump_data_dependence_relations (dump_file, dependences);
2476 components = split_data_refs_to_components (loop, datarefs, dependences);
2477 loop_nest.release ();
2478 free_dependence_relations (dependences);
2479 if (!components)
2481 free_data_refs (datarefs);
2482 free_affine_expand_cache (&name_expansions);
2483 return false;
2486 if (dump_file && (dump_flags & TDF_DETAILS))
2488 fprintf (dump_file, "Initial state:\n\n");
2489 dump_components (dump_file, components);
2492 /* Find the suitable components and split them into chains. */
2493 components = filter_suitable_components (loop, components);
2495 tmp_vars = BITMAP_ALLOC (NULL);
2496 looparound_phis = BITMAP_ALLOC (NULL);
2497 determine_roots (loop, components, &chains);
2498 release_components (components);
2500 if (!chains.exists ())
2502 if (dump_file && (dump_flags & TDF_DETAILS))
2503 fprintf (dump_file,
2504 "Predictive commoning failed: no suitable chains\n");
2505 goto end;
2507 prepare_initializers (loop, chains);
2509 /* Try to combine the chains that are always worked with together. */
2510 try_combine_chains (&chains);
2512 if (dump_file && (dump_flags & TDF_DETAILS))
2514 fprintf (dump_file, "Before commoning:\n\n");
2515 dump_chains (dump_file, chains);
2518 /* Determine the unroll factor, and if the loop should be unrolled, ensure
2519 that its number of iterations is divisible by the factor. */
2520 unroll_factor = determine_unroll_factor (chains);
2521 scev_reset ();
2522 unroll = (unroll_factor > 1
2523 && can_unroll_loop_p (loop, unroll_factor, &desc));
2524 exit = single_dom_exit (loop);
2526 /* Execute the predictive commoning transformations, and possibly unroll the
2527 loop. */
2528 if (unroll)
2530 struct epcc_data dta;
2532 if (dump_file && (dump_flags & TDF_DETAILS))
2533 fprintf (dump_file, "Unrolling %u times.\n", unroll_factor);
2535 dta.chains = chains;
2536 dta.tmp_vars = tmp_vars;
2538 update_ssa (TODO_update_ssa_only_virtuals);
2540 /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2541 execute_pred_commoning_cbck is called may cause phi nodes to be
2542 reallocated, which is a problem since CHAINS may point to these
2543 statements. To fix this, we store the ssa names defined by the
2544 phi nodes here instead of the phi nodes themselves, and restore
2545 the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
2546 replace_phis_by_defined_names (chains);
2548 tree_transform_and_unroll_loop (loop, unroll_factor, exit, &desc,
2549 execute_pred_commoning_cbck, &dta);
2550 eliminate_temp_copies (loop, tmp_vars);
2552 else
2554 if (dump_file && (dump_flags & TDF_DETAILS))
2555 fprintf (dump_file,
2556 "Executing predictive commoning without unrolling.\n");
2557 execute_pred_commoning (loop, chains, tmp_vars);
2560 end: ;
2561 release_chains (chains);
2562 free_data_refs (datarefs);
2563 BITMAP_FREE (tmp_vars);
2564 BITMAP_FREE (looparound_phis);
2566 free_affine_expand_cache (&name_expansions);
2568 return unroll;
2571 /* Runs predictive commoning. */
2573 unsigned
2574 tree_predictive_commoning (void)
2576 bool unrolled = false;
2577 struct loop *loop;
2578 unsigned ret = 0;
2580 initialize_original_copy_tables ();
2581 FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
2582 if (optimize_loop_for_speed_p (loop))
2584 unrolled |= tree_predictive_commoning_loop (loop);
2587 if (unrolled)
2589 scev_reset ();
2590 ret = TODO_cleanup_cfg;
2592 free_original_copy_tables ();
2594 return ret;
2597 /* Predictive commoning Pass. */
2599 static unsigned
2600 run_tree_predictive_commoning (struct function *fun)
2602 if (number_of_loops (fun) <= 1)
2603 return 0;
2605 return tree_predictive_commoning ();
2608 namespace {
2610 const pass_data pass_data_predcom =
2612 GIMPLE_PASS, /* type */
2613 "pcom", /* name */
2614 OPTGROUP_LOOP, /* optinfo_flags */
2615 TV_PREDCOM, /* tv_id */
2616 PROP_cfg, /* properties_required */
2617 0, /* properties_provided */
2618 0, /* properties_destroyed */
2619 0, /* todo_flags_start */
2620 TODO_update_ssa_only_virtuals, /* todo_flags_finish */
2623 class pass_predcom : public gimple_opt_pass
2625 public:
2626 pass_predcom (gcc::context *ctxt)
2627 : gimple_opt_pass (pass_data_predcom, ctxt)
2630 /* opt_pass methods: */
2631 virtual bool gate (function *) { return flag_predictive_commoning != 0; }
2632 virtual unsigned int execute (function *fun)
2634 return run_tree_predictive_commoning (fun);
2637 }; // class pass_predcom
2639 } // anon namespace
2641 gimple_opt_pass *
2642 make_pass_predcom (gcc::context *ctxt)
2644 return new pass_predcom (ctxt);