VOP_FSYNC.9: Missing comma
[dragonfly.git] / contrib / gcc-4.7 / gcc / tree-predcom.c
1 /* Predictive commoning.
2    Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011, 2012
3    Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
10 later version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 /* This file implements the predictive commoning optimization.  Predictive
22    commoning can be viewed as CSE around a loop, and with some improvements,
23    as generalized strength reduction-- i.e., reusing values computed in
24    earlier iterations of a loop in the later ones.  So far, the pass only
25    handles the most useful case, that is, reusing values of memory references.
26    If you think this is all just a special case of PRE, you are sort of right;
27    however, concentrating on loops is simpler, and makes it possible to
28    incorporate data dependence analysis to detect the opportunities, perform
29    loop unrolling to avoid copies together with renaming immediately,
30    and if needed, we could also take register pressure into account.
31
32    Let us demonstrate what is done on an example:
33
34    for (i = 0; i < 100; i++)
35      {
36        a[i+2] = a[i] + a[i+1];
37        b[10] = b[10] + i;
38        c[i] = c[99 - i];
39        d[i] = d[i + 1];
40      }
41
42    1) We find data references in the loop, and split them to mutually
43       independent groups (i.e., we find components of a data dependence
44       graph).  We ignore read-read dependences whose distance is not constant.
45       (TODO -- we could also ignore antidependences).  In this example, we
46       find the following groups:
47
48       a[i]{read}, a[i+1]{read}, a[i+2]{write}
49       b[10]{read}, b[10]{write}
50       c[99 - i]{read}, c[i]{write}
51       d[i + 1]{read}, d[i]{write}
52
53    2) Inside each of the group, we verify several conditions:
54       a) all the references must differ in indices only, and the indices
55          must all have the same step
56       b) the references must dominate loop latch (and thus, they must be
57          ordered by dominance relation).
58       c) the distance of the indices must be a small multiple of the step
59       We are then able to compute the difference of the references (# of
60       iterations before they point to the same place as the first of them).
61       Also, in case there are writes in the loop, we split the groups into
62       chains whose head is the write whose values are used by the reads in
63       the same chain.  The chains are then processed independently,
64       making the further transformations simpler.  Also, the shorter chains
65       need the same number of registers, but may require lower unrolling
66       factor in order to get rid of the copies on the loop latch.
67
68       In our example, we get the following chains (the chain for c is invalid).
69
70       a[i]{read,+0}, a[i+1]{read,-1}, a[i+2]{write,-2}
71       b[10]{read,+0}, b[10]{write,+0}
72       d[i + 1]{read,+0}, d[i]{write,+1}
73
74    3) For each read, we determine the read or write whose value it reuses,
75       together with the distance of this reuse.  I.e. we take the last
76       reference before it with distance 0, or the last of the references
77       with the smallest positive distance to the read.  Then, we remove
78       the references that are not used in any of these chains, discard the
79       empty groups, and propagate all the links so that they point to the
80       single root reference of the chain (adjusting their distance
81       appropriately).  Some extra care needs to be taken for references with
82       step 0.  In our example (the numbers indicate the distance of the
83       reuse),
84
85       a[i] --> (*) 2, a[i+1] --> (*) 1, a[i+2] (*)
86       b[10] --> (*) 1, b[10] (*)
87
88    4) The chains are combined together if possible.  If the corresponding
89       elements of two chains are always combined together with the same
90       operator, we remember just the result of this combination, instead
91       of remembering the values separately.  We may need to perform
92       reassociation to enable combining, for example
93
94       e[i] + f[i+1] + e[i+1] + f[i]
95
96       can be reassociated as
97
98       (e[i] + f[i]) + (e[i+1] + f[i+1])
99
100       and we can combine the chains for e and f into one chain.
101
102    5) For each root reference (end of the chain) R, let N be maximum distance
103       of a reference reusing its value.  Variables R0 upto RN are created,
104       together with phi nodes that transfer values from R1 .. RN to
105       R0 .. R(N-1).
106       Initial values are loaded to R0..R(N-1) (in case not all references
107       must necessarily be accessed and they may trap, we may fail here;
108       TODO sometimes, the loads could be guarded by a check for the number
109       of iterations).  Values loaded/stored in roots are also copied to
110       RN.  Other reads are replaced with the appropriate variable Ri.
111       Everything is put to SSA form.
112
113       As a small improvement, if R0 is dead after the root (i.e., all uses of
114       the value with the maximum distance dominate the root), we can avoid
115       creating RN and use R0 instead of it.
116
117       In our example, we get (only the parts concerning a and b are shown):
118       for (i = 0; i < 100; i++)
119         {
120           f = phi (a[0], s);
121           s = phi (a[1], f);
122           x = phi (b[10], x);
123
124           f = f + s;
125           a[i+2] = f;
126           x = x + i;
127           b[10] = x;
128         }
129
130    6) Factor F for unrolling is determined as the smallest common multiple of
131       (N + 1) for each root reference (N for references for that we avoided
132       creating RN).  If F and the loop is small enough, loop is unrolled F
133       times.  The stores to RN (R0) in the copies of the loop body are
134       periodically replaced with R0, R1, ... (R1, R2, ...), so that they can
135       be coalesced and the copies can be eliminated.
136
137       TODO -- copy propagation and other optimizations may change the live
138       ranges of the temporary registers and prevent them from being coalesced;
139       this may increase the register pressure.
140
141       In our case, F = 2 and the (main loop of the) result is
142
143       for (i = 0; i < ...; i += 2)
144         {
145           f = phi (a[0], f);
146           s = phi (a[1], s);
147           x = phi (b[10], x);
148
149           f = f + s;
150           a[i+2] = f;
151           x = x + i;
152           b[10] = x;
153
154           s = s + f;
155           a[i+3] = s;
156           x = x + i;
157           b[10] = x;
158        }
159
160    TODO -- stores killing other stores can be taken into account, e.g.,
161    for (i = 0; i < n; i++)
162      {
163        a[i] = 1;
164        a[i+2] = 2;
165      }
166
167    can be replaced with
168
169    t0 = a[0];
170    t1 = a[1];
171    for (i = 0; i < n; i++)
172      {
173        a[i] = 1;
174        t2 = 2;
175        t0 = t1;
176        t1 = t2;
177      }
178    a[n] = t0;
179    a[n+1] = t1;
180
181    The interesting part is that this would generalize store motion; still, since
182    sm is performed elsewhere, it does not seem that important.
183
184    Predictive commoning can be generalized for arbitrary computations (not
185    just memory loads), and also nontrivial transfer functions (e.g., replacing
186    i * i with ii_last + 2 * i + 1), to generalize strength reduction.  */
187
188 #include "config.h"
189 #include "system.h"
190 #include "coretypes.h"
191 #include "tm.h"
192 #include "tree.h"
193 #include "tm_p.h"
194 #include "cfgloop.h"
195 #include "tree-flow.h"
196 #include "ggc.h"
197 #include "tree-data-ref.h"
198 #include "tree-scalar-evolution.h"
199 #include "tree-chrec.h"
200 #include "params.h"
201 #include "tree-pretty-print.h"
202 #include "gimple-pretty-print.h"
203 #include "tree-pass.h"
204 #include "tree-affine.h"
205 #include "tree-inline.h"
206
207 /* The maximum number of iterations between the considered memory
208    references.  */
209
210 #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
211
212 /* Data references (or phi nodes that carry data reference values across
213    loop iterations).  */
214
215 typedef struct dref_d
216 {
217   /* The reference itself.  */
218   struct data_reference *ref;
219
220   /* The statement in that the reference appears.  */
221   gimple stmt;
222
223   /* In case that STMT is a phi node, this field is set to the SSA name
224      defined by it in replace_phis_by_defined_names (in order to avoid
225      pointing to phi node that got reallocated in the meantime).  */
226   tree name_defined_by_phi;
227
228   /* Distance of the reference from the root of the chain (in number of
229      iterations of the loop).  */
230   unsigned distance;
231
232   /* Number of iterations offset from the first reference in the component.  */
233   double_int offset;
234
235   /* Number of the reference in a component, in dominance ordering.  */
236   unsigned pos;
237
238   /* True if the memory reference is always accessed when the loop is
239      entered.  */
240   unsigned always_accessed : 1;
241 } *dref;
242
243 DEF_VEC_P (dref);
244 DEF_VEC_ALLOC_P (dref, heap);
245
246 /* Type of the chain of the references.  */
247
248 enum chain_type
249 {
250   /* The addresses of the references in the chain are constant.  */
251   CT_INVARIANT,
252
253   /* There are only loads in the chain.  */
254   CT_LOAD,
255
256   /* Root of the chain is store, the rest are loads.  */
257   CT_STORE_LOAD,
258
259   /* A combination of two chains.  */
260   CT_COMBINATION
261 };
262
263 /* Chains of data references.  */
264
265 typedef struct chain
266 {
267   /* Type of the chain.  */
268   enum chain_type type;
269
270   /* For combination chains, the operator and the two chains that are
271      combined, and the type of the result.  */
272   enum tree_code op;
273   tree rslt_type;
274   struct chain *ch1, *ch2;
275
276   /* The references in the chain.  */
277   VEC(dref,heap) *refs;
278
279   /* The maximum distance of the reference in the chain from the root.  */
280   unsigned length;
281
282   /* The variables used to copy the value throughout iterations.  */
283   VEC(tree,heap) *vars;
284
285   /* Initializers for the variables.  */
286   VEC(tree,heap) *inits;
287
288   /* True if there is a use of a variable with the maximal distance
289      that comes after the root in the loop.  */
290   unsigned has_max_use_after : 1;
291
292   /* True if all the memory references in the chain are always accessed.  */
293   unsigned all_always_accessed : 1;
294
295   /* True if this chain was combined together with some other chain.  */
296   unsigned combined : 1;
297 } *chain_p;
298
299 DEF_VEC_P (chain_p);
300 DEF_VEC_ALLOC_P (chain_p, heap);
301
302 /* Describes the knowledge about the step of the memory references in
303    the component.  */
304
305 enum ref_step_type
306 {
307   /* The step is zero.  */
308   RS_INVARIANT,
309
310   /* The step is nonzero.  */
311   RS_NONZERO,
312
313   /* The step may or may not be nonzero.  */
314   RS_ANY
315 };
316
317 /* Components of the data dependence graph.  */
318
319 struct component
320 {
321   /* The references in the component.  */
322   VEC(dref,heap) *refs;
323
324   /* What we know about the step of the references in the component.  */
325   enum ref_step_type comp_step;
326
327   /* Next component in the list.  */
328   struct component *next;
329 };
330
331 /* Bitmap of ssa names defined by looparound phi nodes covered by chains.  */
332
333 static bitmap looparound_phis;
334
335 /* Cache used by tree_to_aff_combination_expand.  */
336
337 static struct pointer_map_t *name_expansions;
338
339 /* Dumps data reference REF to FILE.  */
340
341 extern void dump_dref (FILE *, dref);
342 void
343 dump_dref (FILE *file, dref ref)
344 {
345   if (ref->ref)
346     {
347       fprintf (file, "    ");
348       print_generic_expr (file, DR_REF (ref->ref), TDF_SLIM);
349       fprintf (file, " (id %u%s)\n", ref->pos,
350                DR_IS_READ (ref->ref) ? "" : ", write");
351
352       fprintf (file, "      offset ");
353       dump_double_int (file, ref->offset, false);
354       fprintf (file, "\n");
355
356       fprintf (file, "      distance %u\n", ref->distance);
357     }
358   else
359     {
360       if (gimple_code (ref->stmt) == GIMPLE_PHI)
361         fprintf (file, "    looparound ref\n");
362       else
363         fprintf (file, "    combination ref\n");
364       fprintf (file, "      in statement ");
365       print_gimple_stmt (file, ref->stmt, 0, TDF_SLIM);
366       fprintf (file, "\n");
367       fprintf (file, "      distance %u\n", ref->distance);
368     }
369
370 }
371
372 /* Dumps CHAIN to FILE.  */
373
374 extern void dump_chain (FILE *, chain_p);
375 void
376 dump_chain (FILE *file, chain_p chain)
377 {
378   dref a;
379   const char *chain_type;
380   unsigned i;
381   tree var;
382
383   switch (chain->type)
384     {
385     case CT_INVARIANT:
386       chain_type = "Load motion";
387       break;
388
389     case CT_LOAD:
390       chain_type = "Loads-only";
391       break;
392
393     case CT_STORE_LOAD:
394       chain_type = "Store-loads";
395       break;
396
397     case CT_COMBINATION:
398       chain_type = "Combination";
399       break;
400
401     default:
402       gcc_unreachable ();
403     }
404
405   fprintf (file, "%s chain %p%s\n", chain_type, (void *) chain,
406            chain->combined ? " (combined)" : "");
407   if (chain->type != CT_INVARIANT)
408     fprintf (file, "  max distance %u%s\n", chain->length,
409              chain->has_max_use_after ? "" : ", may reuse first");
410
411   if (chain->type == CT_COMBINATION)
412     {
413       fprintf (file, "  equal to %p %s %p in type ",
414                (void *) chain->ch1, op_symbol_code (chain->op),
415                (void *) chain->ch2);
416       print_generic_expr (file, chain->rslt_type, TDF_SLIM);
417       fprintf (file, "\n");
418     }
419
420   if (chain->vars)
421     {
422       fprintf (file, "  vars");
423       FOR_EACH_VEC_ELT (tree, chain->vars, i, var)
424         {
425           fprintf (file, " ");
426           print_generic_expr (file, var, TDF_SLIM);
427         }
428       fprintf (file, "\n");
429     }
430
431   if (chain->inits)
432     {
433       fprintf (file, "  inits");
434       FOR_EACH_VEC_ELT (tree, chain->inits, i, var)
435         {
436           fprintf (file, " ");
437           print_generic_expr (file, var, TDF_SLIM);
438         }
439       fprintf (file, "\n");
440     }
441
442   fprintf (file, "  references:\n");
443   FOR_EACH_VEC_ELT (dref, chain->refs, i, a)
444     dump_dref (file, a);
445
446   fprintf (file, "\n");
447 }
448
449 /* Dumps CHAINS to FILE.  */
450
451 extern void dump_chains (FILE *, VEC (chain_p, heap) *);
452 void
453 dump_chains (FILE *file, VEC (chain_p, heap) *chains)
454 {
455   chain_p chain;
456   unsigned i;
457
458   FOR_EACH_VEC_ELT (chain_p, chains, i, chain)
459     dump_chain (file, chain);
460 }
461
462 /* Dumps COMP to FILE.  */
463
464 extern void dump_component (FILE *, struct component *);
465 void
466 dump_component (FILE *file, struct component *comp)
467 {
468   dref a;
469   unsigned i;
470
471   fprintf (file, "Component%s:\n",
472            comp->comp_step == RS_INVARIANT ? " (invariant)" : "");
473   FOR_EACH_VEC_ELT (dref, comp->refs, i, a)
474     dump_dref (file, a);
475   fprintf (file, "\n");
476 }
477
478 /* Dumps COMPS to FILE.  */
479
480 extern void dump_components (FILE *, struct component *);
481 void
482 dump_components (FILE *file, struct component *comps)
483 {
484   struct component *comp;
485
486   for (comp = comps; comp; comp = comp->next)
487     dump_component (file, comp);
488 }
489
490 /* Frees a chain CHAIN.  */
491
492 static void
493 release_chain (chain_p chain)
494 {
495   dref ref;
496   unsigned i;
497
498   if (chain == NULL)
499     return;
500
501   FOR_EACH_VEC_ELT (dref, chain->refs, i, ref)
502     free (ref);
503
504   VEC_free (dref, heap, chain->refs);
505   VEC_free (tree, heap, chain->vars);
506   VEC_free (tree, heap, chain->inits);
507
508   free (chain);
509 }
510
511 /* Frees CHAINS.  */
512
513 static void
514 release_chains (VEC (chain_p, heap) *chains)
515 {
516   unsigned i;
517   chain_p chain;
518
519   FOR_EACH_VEC_ELT (chain_p, chains, i, chain)
520     release_chain (chain);
521   VEC_free (chain_p, heap, chains);
522 }
523
524 /* Frees a component COMP.  */
525
526 static void
527 release_component (struct component *comp)
528 {
529   VEC_free (dref, heap, comp->refs);
530   free (comp);
531 }
532
533 /* Frees list of components COMPS.  */
534
535 static void
536 release_components (struct component *comps)
537 {
538   struct component *act, *next;
539
540   for (act = comps; act; act = next)
541     {
542       next = act->next;
543       release_component (act);
544     }
545 }
546
547 /* Finds a root of tree given by FATHERS containing A, and performs path
548    shortening.  */
549
550 static unsigned
551 component_of (unsigned fathers[], unsigned a)
552 {
553   unsigned root, n;
554
555   for (root = a; root != fathers[root]; root = fathers[root])
556     continue;
557
558   for (; a != root; a = n)
559     {
560       n = fathers[a];
561       fathers[a] = root;
562     }
563
564   return root;
565 }
566
567 /* Join operation for DFU.  FATHERS gives the tree, SIZES are sizes of the
568    components, A and B are components to merge.  */
569
570 static void
571 merge_comps (unsigned fathers[], unsigned sizes[], unsigned a, unsigned b)
572 {
573   unsigned ca = component_of (fathers, a);
574   unsigned cb = component_of (fathers, b);
575
576   if (ca == cb)
577     return;
578
579   if (sizes[ca] < sizes[cb])
580     {
581       sizes[cb] += sizes[ca];
582       fathers[ca] = cb;
583     }
584   else
585     {
586       sizes[ca] += sizes[cb];
587       fathers[cb] = ca;
588     }
589 }
590
591 /* Returns true if A is a reference that is suitable for predictive commoning
592    in the innermost loop that contains it.  REF_STEP is set according to the
593    step of the reference A.  */
594
595 static bool
596 suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step)
597 {
598   tree ref = DR_REF (a), step = DR_STEP (a);
599
600   if (!step
601       || TREE_THIS_VOLATILE (ref)
602       || !is_gimple_reg_type (TREE_TYPE (ref))
603       || tree_could_throw_p (ref))
604     return false;
605
606   if (integer_zerop (step))
607     *ref_step = RS_INVARIANT;
608   else if (integer_nonzerop (step))
609     *ref_step = RS_NONZERO;
610   else
611     *ref_step = RS_ANY;
612
613   return true;
614 }
615
616 /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET.  */
617
618 static void
619 aff_combination_dr_offset (struct data_reference *dr, aff_tree *offset)
620 {
621   tree type = TREE_TYPE (DR_OFFSET (dr));
622   aff_tree delta;
623
624   tree_to_aff_combination_expand (DR_OFFSET (dr), type, offset,
625                                   &name_expansions);
626   aff_combination_const (&delta, type, tree_to_double_int (DR_INIT (dr)));
627   aff_combination_add (offset, &delta);
628 }
629
630 /* Determines number of iterations of the innermost enclosing loop before B
631    refers to exactly the same location as A and stores it to OFF.  If A and
632    B do not have the same step, they never meet, or anything else fails,
633    returns false, otherwise returns true.  Both A and B are assumed to
634    satisfy suitable_reference_p.  */
635
636 static bool
637 determine_offset (struct data_reference *a, struct data_reference *b,
638                   double_int *off)
639 {
640   aff_tree diff, baseb, step;
641   tree typea, typeb;
642
643   /* Check that both the references access the location in the same type.  */
644   typea = TREE_TYPE (DR_REF (a));
645   typeb = TREE_TYPE (DR_REF (b));
646   if (!useless_type_conversion_p (typeb, typea))
647     return false;
648
649   /* Check whether the base address and the step of both references is the
650      same.  */
651   if (!operand_equal_p (DR_STEP (a), DR_STEP (b), 0)
652       || !operand_equal_p (DR_BASE_ADDRESS (a), DR_BASE_ADDRESS (b), 0))
653     return false;
654
655   if (integer_zerop (DR_STEP (a)))
656     {
657       /* If the references have loop invariant address, check that they access
658          exactly the same location.  */
659       *off = double_int_zero;
660       return (operand_equal_p (DR_OFFSET (a), DR_OFFSET (b), 0)
661               && operand_equal_p (DR_INIT (a), DR_INIT (b), 0));
662     }
663
664   /* Compare the offsets of the addresses, and check whether the difference
665      is a multiple of step.  */
666   aff_combination_dr_offset (a, &diff);
667   aff_combination_dr_offset (b, &baseb);
668   aff_combination_scale (&baseb, double_int_minus_one);
669   aff_combination_add (&diff, &baseb);
670
671   tree_to_aff_combination_expand (DR_STEP (a), TREE_TYPE (DR_STEP (a)),
672                                   &step, &name_expansions);
673   return aff_combination_constant_multiple_p (&diff, &step, off);
674 }
675
676 /* Returns the last basic block in LOOP for that we are sure that
677    it is executed whenever the loop is entered.  */
678
679 static basic_block
680 last_always_executed_block (struct loop *loop)
681 {
682   unsigned i;
683   VEC (edge, heap) *exits = get_loop_exit_edges (loop);
684   edge ex;
685   basic_block last = loop->latch;
686
687   FOR_EACH_VEC_ELT (edge, exits, i, ex)
688     last = nearest_common_dominator (CDI_DOMINATORS, last, ex->src);
689   VEC_free (edge, heap, exits);
690
691   return last;
692 }
693
694 /* Splits dependence graph on DATAREFS described by DEPENDS to components.  */
695
696 static struct component *
697 split_data_refs_to_components (struct loop *loop,
698                                VEC (data_reference_p, heap) *datarefs,
699                                VEC (ddr_p, heap) *depends)
700 {
701   unsigned i, n = VEC_length (data_reference_p, datarefs);
702   unsigned ca, ia, ib, bad;
703   unsigned *comp_father = XNEWVEC (unsigned, n + 1);
704   unsigned *comp_size = XNEWVEC (unsigned, n + 1);
705   struct component **comps;
706   struct data_reference *dr, *dra, *drb;
707   struct data_dependence_relation *ddr;
708   struct component *comp_list = NULL, *comp;
709   dref dataref;
710   basic_block last_always_executed = last_always_executed_block (loop);
711
712   FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
713     {
714       if (!DR_REF (dr))
715         {
716           /* A fake reference for call or asm_expr that may clobber memory;
717              just fail.  */
718           goto end;
719         }
720       dr->aux = (void *) (size_t) i;
721       comp_father[i] = i;
722       comp_size[i] = 1;
723     }
724
725   /* A component reserved for the "bad" data references.  */
726   comp_father[n] = n;
727   comp_size[n] = 1;
728
729   FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
730     {
731       enum ref_step_type dummy;
732
733       if (!suitable_reference_p (dr, &dummy))
734         {
735           ia = (unsigned) (size_t) dr->aux;
736           merge_comps (comp_father, comp_size, n, ia);
737         }
738     }
739
740   FOR_EACH_VEC_ELT (ddr_p, depends, i, ddr)
741     {
742       double_int dummy_off;
743
744       if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
745         continue;
746
747       dra = DDR_A (ddr);
748       drb = DDR_B (ddr);
749       ia = component_of (comp_father, (unsigned) (size_t) dra->aux);
750       ib = component_of (comp_father, (unsigned) (size_t) drb->aux);
751       if (ia == ib)
752         continue;
753
754       bad = component_of (comp_father, n);
755
756       /* If both A and B are reads, we may ignore unsuitable dependences.  */
757       if (DR_IS_READ (dra) && DR_IS_READ (drb)
758           && (ia == bad || ib == bad
759               || !determine_offset (dra, drb, &dummy_off)))
760         continue;
761
762       merge_comps (comp_father, comp_size, ia, ib);
763     }
764
765   comps = XCNEWVEC (struct component *, n);
766   bad = component_of (comp_father, n);
767   FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
768     {
769       ia = (unsigned) (size_t) dr->aux;
770       ca = component_of (comp_father, ia);
771       if (ca == bad)
772         continue;
773
774       comp = comps[ca];
775       if (!comp)
776         {
777           comp = XCNEW (struct component);
778           comp->refs = VEC_alloc (dref, heap, comp_size[ca]);
779           comps[ca] = comp;
780         }
781
782       dataref = XCNEW (struct dref_d);
783       dataref->ref = dr;
784       dataref->stmt = DR_STMT (dr);
785       dataref->offset = double_int_zero;
786       dataref->distance = 0;
787
788       dataref->always_accessed
789               = dominated_by_p (CDI_DOMINATORS, last_always_executed,
790                                 gimple_bb (dataref->stmt));
791       dataref->pos = VEC_length (dref, comp->refs);
792       VEC_quick_push (dref, comp->refs, dataref);
793     }
794
795   for (i = 0; i < n; i++)
796     {
797       comp = comps[i];
798       if (comp)
799         {
800           comp->next = comp_list;
801           comp_list = comp;
802         }
803     }
804   free (comps);
805
806 end:
807   free (comp_father);
808   free (comp_size);
809   return comp_list;
810 }
811
812 /* Returns true if the component COMP satisfies the conditions
813    described in 2) at the beginning of this file.  LOOP is the current
814    loop.  */
815
816 static bool
817 suitable_component_p (struct loop *loop, struct component *comp)
818 {
819   unsigned i;
820   dref a, first;
821   basic_block ba, bp = loop->header;
822   bool ok, has_write = false;
823
824   FOR_EACH_VEC_ELT (dref, comp->refs, i, a)
825     {
826       ba = gimple_bb (a->stmt);
827
828       if (!just_once_each_iteration_p (loop, ba))
829         return false;
830
831       gcc_assert (dominated_by_p (CDI_DOMINATORS, ba, bp));
832       bp = ba;
833
834       if (DR_IS_WRITE (a->ref))
835         has_write = true;
836     }
837
838   first = VEC_index (dref, comp->refs, 0);
839   ok = suitable_reference_p (first->ref, &comp->comp_step);
840   gcc_assert (ok);
841   first->offset = double_int_zero;
842
843   for (i = 1; VEC_iterate (dref, comp->refs, i, a); i++)
844     {
845       if (!determine_offset (first->ref, a->ref, &a->offset))
846         return false;
847
848 #ifdef ENABLE_CHECKING
849       {
850         enum ref_step_type a_step;
851         ok = suitable_reference_p (a->ref, &a_step);
852         gcc_assert (ok && a_step == comp->comp_step);
853       }
854 #endif
855     }
856
857   /* If there is a write inside the component, we must know whether the
858      step is nonzero or not -- we would not otherwise be able to recognize
859      whether the value accessed by reads comes from the OFFSET-th iteration
860      or the previous one.  */
861   if (has_write && comp->comp_step == RS_ANY)
862     return false;
863
864   return true;
865 }
866
867 /* Check the conditions on references inside each of components COMPS,
868    and remove the unsuitable components from the list.  The new list
869    of components is returned.  The conditions are described in 2) at
870    the beginning of this file.  LOOP is the current loop.  */
871
872 static struct component *
873 filter_suitable_components (struct loop *loop, struct component *comps)
874 {
875   struct component **comp, *act;
876
877   for (comp = &comps; *comp; )
878     {
879       act = *comp;
880       if (suitable_component_p (loop, act))
881         comp = &act->next;
882       else
883         {
884           dref ref;
885           unsigned i;
886
887           *comp = act->next;
888           FOR_EACH_VEC_ELT (dref, act->refs, i, ref)
889             free (ref);
890           release_component (act);
891         }
892     }
893
894   return comps;
895 }
896
897 /* Compares two drefs A and B by their offset and position.  Callback for
898    qsort.  */
899
900 static int
901 order_drefs (const void *a, const void *b)
902 {
903   const dref *const da = (const dref *) a;
904   const dref *const db = (const dref *) b;
905   int offcmp = double_int_scmp ((*da)->offset, (*db)->offset);
906
907   if (offcmp != 0)
908     return offcmp;
909
910   return (*da)->pos - (*db)->pos;
911 }
912
913 /* Returns root of the CHAIN.  */
914
915 static inline dref
916 get_chain_root (chain_p chain)
917 {
918   return VEC_index (dref, chain->refs, 0);
919 }
920
921 /* Adds REF to the chain CHAIN.  */
922
923 static void
924 add_ref_to_chain (chain_p chain, dref ref)
925 {
926   dref root = get_chain_root (chain);
927   double_int dist;
928
929   gcc_assert (double_int_scmp (root->offset, ref->offset) <= 0);
930   dist = double_int_sub (ref->offset, root->offset);
931   if (double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE), dist) <= 0)
932     {
933       free (ref);
934       return;
935     }
936   gcc_assert (double_int_fits_in_uhwi_p (dist));
937
938   VEC_safe_push (dref, heap, chain->refs, ref);
939
940   ref->distance = double_int_to_uhwi (dist);
941
942   if (ref->distance >= chain->length)
943     {
944       chain->length = ref->distance;
945       chain->has_max_use_after = false;
946     }
947
948   if (ref->distance == chain->length
949       && ref->pos > root->pos)
950     chain->has_max_use_after = true;
951
952   chain->all_always_accessed &= ref->always_accessed;
953 }
954
955 /* Returns the chain for invariant component COMP.  */
956
957 static chain_p
958 make_invariant_chain (struct component *comp)
959 {
960   chain_p chain = XCNEW (struct chain);
961   unsigned i;
962   dref ref;
963
964   chain->type = CT_INVARIANT;
965
966   chain->all_always_accessed = true;
967
968   FOR_EACH_VEC_ELT (dref, comp->refs, i, ref)
969     {
970       VEC_safe_push (dref, heap, chain->refs, ref);
971       chain->all_always_accessed &= ref->always_accessed;
972     }
973
974   return chain;
975 }
976
977 /* Make a new chain rooted at REF.  */
978
979 static chain_p
980 make_rooted_chain (dref ref)
981 {
982   chain_p chain = XCNEW (struct chain);
983
984   chain->type = DR_IS_READ (ref->ref) ? CT_LOAD : CT_STORE_LOAD;
985
986   VEC_safe_push (dref, heap, chain->refs, ref);
987   chain->all_always_accessed = ref->always_accessed;
988
989   ref->distance = 0;
990
991   return chain;
992 }
993
994 /* Returns true if CHAIN is not trivial.  */
995
996 static bool
997 nontrivial_chain_p (chain_p chain)
998 {
999   return chain != NULL && VEC_length (dref, chain->refs) > 1;
1000 }
1001
1002 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1003    is no such name.  */
1004
1005 static tree
1006 name_for_ref (dref ref)
1007 {
1008   tree name;
1009
1010   if (is_gimple_assign (ref->stmt))
1011     {
1012       if (!ref->ref || DR_IS_READ (ref->ref))
1013         name = gimple_assign_lhs (ref->stmt);
1014       else
1015         name = gimple_assign_rhs1 (ref->stmt);
1016     }
1017   else
1018     name = PHI_RESULT (ref->stmt);
1019
1020   return (TREE_CODE (name) == SSA_NAME ? name : NULL_TREE);
1021 }
1022
1023 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1024    iterations of the innermost enclosing loop).  */
1025
1026 static bool
1027 valid_initializer_p (struct data_reference *ref,
1028                      unsigned distance, struct data_reference *root)
1029 {
1030   aff_tree diff, base, step;
1031   double_int off;
1032
1033   /* Both REF and ROOT must be accessing the same object.  */
1034   if (!operand_equal_p (DR_BASE_ADDRESS (ref), DR_BASE_ADDRESS (root), 0))
1035     return false;
1036
1037   /* The initializer is defined outside of loop, hence its address must be
1038      invariant inside the loop.  */
1039   gcc_assert (integer_zerop (DR_STEP (ref)));
1040
1041   /* If the address of the reference is invariant, initializer must access
1042      exactly the same location.  */
1043   if (integer_zerop (DR_STEP (root)))
1044     return (operand_equal_p (DR_OFFSET (ref), DR_OFFSET (root), 0)
1045             && operand_equal_p (DR_INIT (ref), DR_INIT (root), 0));
1046
1047   /* Verify that this index of REF is equal to the root's index at
1048      -DISTANCE-th iteration.  */
1049   aff_combination_dr_offset (root, &diff);
1050   aff_combination_dr_offset (ref, &base);
1051   aff_combination_scale (&base, double_int_minus_one);
1052   aff_combination_add (&diff, &base);
1053
1054   tree_to_aff_combination_expand (DR_STEP (root), TREE_TYPE (DR_STEP (root)),
1055                                   &step, &name_expansions);
1056   if (!aff_combination_constant_multiple_p (&diff, &step, &off))
1057     return false;
1058
1059   if (!double_int_equal_p (off, uhwi_to_double_int (distance)))
1060     return false;
1061
1062   return true;
1063 }
1064
1065 /* Finds looparound phi node of LOOP that copies the value of REF, and if its
1066    initial value is correct (equal to initial value of REF shifted by one
1067    iteration), returns the phi node.  Otherwise, NULL_TREE is returned.  ROOT
1068    is the root of the current chain.  */
1069
1070 static gimple
1071 find_looparound_phi (struct loop *loop, dref ref, dref root)
1072 {
1073   tree name, init, init_ref;
1074   gimple phi = NULL, init_stmt;
1075   edge latch = loop_latch_edge (loop);
1076   struct data_reference init_dr;
1077   gimple_stmt_iterator psi;
1078
1079   if (is_gimple_assign (ref->stmt))
1080     {
1081       if (DR_IS_READ (ref->ref))
1082         name = gimple_assign_lhs (ref->stmt);
1083       else
1084         name = gimple_assign_rhs1 (ref->stmt);
1085     }
1086   else
1087     name = PHI_RESULT (ref->stmt);
1088   if (!name)
1089     return NULL;
1090
1091   for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1092     {
1093       phi = gsi_stmt (psi);
1094       if (PHI_ARG_DEF_FROM_EDGE (phi, latch) == name)
1095         break;
1096     }
1097
1098   if (gsi_end_p (psi))
1099     return NULL;
1100
1101   init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1102   if (TREE_CODE (init) != SSA_NAME)
1103     return NULL;
1104   init_stmt = SSA_NAME_DEF_STMT (init);
1105   if (gimple_code (init_stmt) != GIMPLE_ASSIGN)
1106     return NULL;
1107   gcc_assert (gimple_assign_lhs (init_stmt) == init);
1108
1109   init_ref = gimple_assign_rhs1 (init_stmt);
1110   if (!REFERENCE_CLASS_P (init_ref)
1111       && !DECL_P (init_ref))
1112     return NULL;
1113
1114   /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1115      loop enclosing PHI).  */
1116   memset (&init_dr, 0, sizeof (struct data_reference));
1117   DR_REF (&init_dr) = init_ref;
1118   DR_STMT (&init_dr) = phi;
1119   if (!dr_analyze_innermost (&init_dr, loop))
1120     return NULL;
1121
1122   if (!valid_initializer_p (&init_dr, ref->distance + 1, root->ref))
1123     return NULL;
1124
1125   return phi;
1126 }
1127
1128 /* Adds a reference for the looparound copy of REF in PHI to CHAIN.  */
1129
1130 static void
1131 insert_looparound_copy (chain_p chain, dref ref, gimple phi)
1132 {
1133   dref nw = XCNEW (struct dref_d), aref;
1134   unsigned i;
1135
1136   nw->stmt = phi;
1137   nw->distance = ref->distance + 1;
1138   nw->always_accessed = 1;
1139
1140   FOR_EACH_VEC_ELT (dref, chain->refs, i, aref)
1141     if (aref->distance >= nw->distance)
1142       break;
1143   VEC_safe_insert (dref, heap, chain->refs, i, nw);
1144
1145   if (nw->distance > chain->length)
1146     {
1147       chain->length = nw->distance;
1148       chain->has_max_use_after = false;
1149     }
1150 }
1151
1152 /* For references in CHAIN that are copied around the LOOP (created previously
1153    by PRE, or by user), add the results of such copies to the chain.  This
1154    enables us to remove the copies by unrolling, and may need less registers
1155    (also, it may allow us to combine chains together).  */
1156
1157 static void
1158 add_looparound_copies (struct loop *loop, chain_p chain)
1159 {
1160   unsigned i;
1161   dref ref, root = get_chain_root (chain);
1162   gimple phi;
1163
1164   FOR_EACH_VEC_ELT (dref, chain->refs, i, ref)
1165     {
1166       phi = find_looparound_phi (loop, ref, root);
1167       if (!phi)
1168         continue;
1169
1170       bitmap_set_bit (looparound_phis, SSA_NAME_VERSION (PHI_RESULT (phi)));
1171       insert_looparound_copy (chain, ref, phi);
1172     }
1173 }
1174
1175 /* Find roots of the values and determine distances in the component COMP.
1176    The references are redistributed into CHAINS.  LOOP is the current
1177    loop.  */
1178
1179 static void
1180 determine_roots_comp (struct loop *loop,
1181                       struct component *comp,
1182                       VEC (chain_p, heap) **chains)
1183 {
1184   unsigned i;
1185   dref a;
1186   chain_p chain = NULL;
1187   double_int last_ofs = double_int_zero;
1188
1189   /* Invariants are handled specially.  */
1190   if (comp->comp_step == RS_INVARIANT)
1191     {
1192       chain = make_invariant_chain (comp);
1193       VEC_safe_push (chain_p, heap, *chains, chain);
1194       return;
1195     }
1196
1197   VEC_qsort (dref, comp->refs, order_drefs);
1198
1199   FOR_EACH_VEC_ELT (dref, comp->refs, i, a)
1200     {
1201       if (!chain || DR_IS_WRITE (a->ref)
1202           || double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE),
1203                               double_int_sub (a->offset, last_ofs)) <= 0)
1204         {
1205           if (nontrivial_chain_p (chain))
1206             {
1207               add_looparound_copies (loop, chain);
1208               VEC_safe_push (chain_p, heap, *chains, chain);
1209             }
1210           else
1211             release_chain (chain);
1212           chain = make_rooted_chain (a);
1213           last_ofs = a->offset;
1214           continue;
1215         }
1216
1217       add_ref_to_chain (chain, a);
1218     }
1219
1220   if (nontrivial_chain_p (chain))
1221     {
1222       add_looparound_copies (loop, chain);
1223       VEC_safe_push (chain_p, heap, *chains, chain);
1224     }
1225   else
1226     release_chain (chain);
1227 }
1228
1229 /* Find roots of the values and determine distances in components COMPS, and
1230    separates the references to CHAINS.  LOOP is the current loop.  */
1231
1232 static void
1233 determine_roots (struct loop *loop,
1234                  struct component *comps, VEC (chain_p, heap) **chains)
1235 {
1236   struct component *comp;
1237
1238   for (comp = comps; comp; comp = comp->next)
1239     determine_roots_comp (loop, comp, chains);
1240 }
1241
1242 /* Replace the reference in statement STMT with temporary variable
1243    NEW_TREE.  If SET is true, NEW_TREE is instead initialized to the value of
1244    the reference in the statement.  IN_LHS is true if the reference
1245    is in the lhs of STMT, false if it is in rhs.  */
1246
1247 static void
1248 replace_ref_with (gimple stmt, tree new_tree, bool set, bool in_lhs)
1249 {
1250   tree val;
1251   gimple new_stmt;
1252   gimple_stmt_iterator bsi, psi;
1253
1254   if (gimple_code (stmt) == GIMPLE_PHI)
1255     {
1256       gcc_assert (!in_lhs && !set);
1257
1258       val = PHI_RESULT (stmt);
1259       bsi = gsi_after_labels (gimple_bb (stmt));
1260       psi = gsi_for_stmt (stmt);
1261       remove_phi_node (&psi, false);
1262
1263       /* Turn the phi node into GIMPLE_ASSIGN.  */
1264       new_stmt = gimple_build_assign (val, new_tree);
1265       gsi_insert_before (&bsi, new_stmt, GSI_NEW_STMT);
1266       return;
1267     }
1268
1269   /* Since the reference is of gimple_reg type, it should only
1270      appear as lhs or rhs of modify statement.  */
1271   gcc_assert (is_gimple_assign (stmt));
1272
1273   bsi = gsi_for_stmt (stmt);
1274
1275   /* If we do not need to initialize NEW_TREE, just replace the use of OLD.  */
1276   if (!set)
1277     {
1278       gcc_assert (!in_lhs);
1279       gimple_assign_set_rhs_from_tree (&bsi, new_tree);
1280       stmt = gsi_stmt (bsi);
1281       update_stmt (stmt);
1282       return;
1283     }
1284
1285   if (in_lhs)
1286     {
1287       /* We have statement
1288
1289          OLD = VAL
1290
1291          If OLD is a memory reference, then VAL is gimple_val, and we transform
1292          this to
1293
1294          OLD = VAL
1295          NEW = VAL
1296
1297          Otherwise, we are replacing a combination chain,
1298          VAL is the expression that performs the combination, and OLD is an
1299          SSA name.  In this case, we transform the assignment to
1300
1301          OLD = VAL
1302          NEW = OLD
1303
1304          */
1305
1306       val = gimple_assign_lhs (stmt);
1307       if (TREE_CODE (val) != SSA_NAME)
1308         {
1309           val = gimple_assign_rhs1 (stmt);
1310           gcc_assert (gimple_assign_single_p (stmt));
1311           if (TREE_CLOBBER_P (val))
1312             {
1313               val = gimple_default_def (cfun, SSA_NAME_VAR (new_tree));
1314               if (val == NULL_TREE)
1315                 {
1316                   val = make_ssa_name (SSA_NAME_VAR (new_tree),
1317                                        gimple_build_nop ());
1318                   set_default_def (SSA_NAME_VAR (new_tree), val);
1319                 }
1320             }
1321           else
1322             gcc_assert (gimple_assign_copy_p (stmt));
1323         }
1324     }
1325   else
1326     {
1327       /* VAL = OLD
1328
1329          is transformed to
1330
1331          VAL = OLD
1332          NEW = VAL  */
1333
1334       val = gimple_assign_lhs (stmt);
1335     }
1336
1337   new_stmt = gimple_build_assign (new_tree, unshare_expr (val));
1338   gsi_insert_after (&bsi, new_stmt, GSI_NEW_STMT);
1339 }
1340
1341 /* Returns the reference to the address of REF in the ITER-th iteration of
1342    LOOP, or NULL if we fail to determine it (ITER may be negative).  We
1343    try to preserve the original shape of the reference (not rewrite it
1344    as an indirect ref to the address), to make tree_could_trap_p in
1345    prepare_initializers_chain return false more often.  */
1346
1347 static tree
1348 ref_at_iteration (struct loop *loop, tree ref, int iter)
1349 {
1350   tree idx, *idx_p, type, val, op0 = NULL_TREE, ret;
1351   affine_iv iv;
1352   bool ok;
1353
1354   if (handled_component_p (ref))
1355     {
1356       op0 = ref_at_iteration (loop, TREE_OPERAND (ref, 0), iter);
1357       if (!op0)
1358         return NULL_TREE;
1359     }
1360   else if (!INDIRECT_REF_P (ref)
1361            && TREE_CODE (ref) != MEM_REF)
1362     return unshare_expr (ref);
1363
1364   if (TREE_CODE (ref) == MEM_REF)
1365     {
1366       ret = unshare_expr (ref);
1367       idx = TREE_OPERAND (ref, 0);
1368       idx_p = &TREE_OPERAND (ret, 0);
1369     }
1370   else if (TREE_CODE (ref) == COMPONENT_REF)
1371     {
1372       /* Check that the offset is loop invariant.  */
1373       if (TREE_OPERAND (ref, 2)
1374           && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2)))
1375         return NULL_TREE;
1376
1377       return build3 (COMPONENT_REF, TREE_TYPE (ref), op0,
1378                      unshare_expr (TREE_OPERAND (ref, 1)),
1379                      unshare_expr (TREE_OPERAND (ref, 2)));
1380     }
1381   else if (TREE_CODE (ref) == ARRAY_REF)
1382     {
1383       /* Check that the lower bound and the step are loop invariant.  */
1384       if (TREE_OPERAND (ref, 2)
1385           && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2)))
1386         return NULL_TREE;
1387       if (TREE_OPERAND (ref, 3)
1388           && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 3)))
1389         return NULL_TREE;
1390
1391       ret = build4 (ARRAY_REF, TREE_TYPE (ref), op0, NULL_TREE,
1392                     unshare_expr (TREE_OPERAND (ref, 2)),
1393                     unshare_expr (TREE_OPERAND (ref, 3)));
1394       idx = TREE_OPERAND (ref, 1);
1395       idx_p = &TREE_OPERAND (ret, 1);
1396     }
1397   else
1398     return NULL_TREE;
1399
1400   ok = simple_iv (loop, loop, idx, &iv, true);
1401   if (!ok)
1402     return NULL_TREE;
1403   iv.base = expand_simple_operations (iv.base);
1404   if (integer_zerop (iv.step))
1405     *idx_p = unshare_expr (iv.base);
1406   else
1407     {
1408       type = TREE_TYPE (iv.base);
1409       if (POINTER_TYPE_P (type))
1410         {
1411           val = fold_build2 (MULT_EXPR, sizetype, iv.step,
1412                              size_int (iter));
1413           val = fold_build_pointer_plus (iv.base, val);
1414         }
1415       else
1416         {
1417           val = fold_build2 (MULT_EXPR, type, iv.step,
1418                              build_int_cst_type (type, iter));
1419           val = fold_build2 (PLUS_EXPR, type, iv.base, val);
1420         }
1421       *idx_p = unshare_expr (val);
1422     }
1423
1424   return ret;
1425 }
1426
1427 /* Get the initialization expression for the INDEX-th temporary variable
1428    of CHAIN.  */
1429
1430 static tree
1431 get_init_expr (chain_p chain, unsigned index)
1432 {
1433   if (chain->type == CT_COMBINATION)
1434     {
1435       tree e1 = get_init_expr (chain->ch1, index);
1436       tree e2 = get_init_expr (chain->ch2, index);
1437
1438       return fold_build2 (chain->op, chain->rslt_type, e1, e2);
1439     }
1440   else
1441     return VEC_index (tree, chain->inits, index);
1442 }
1443
1444 /* Marks all virtual operands of statement STMT for renaming.  */
1445
1446 void
1447 mark_virtual_ops_for_renaming (gimple stmt)
1448 {
1449   tree var;
1450
1451   if (gimple_code (stmt) == GIMPLE_PHI)
1452     {
1453       var = PHI_RESULT (stmt);
1454       if (is_gimple_reg (var))
1455         return;
1456
1457       if (TREE_CODE (var) == SSA_NAME)
1458         var = SSA_NAME_VAR (var);
1459       mark_sym_for_renaming (var);
1460       return;
1461     }
1462
1463   update_stmt (stmt);
1464   if (gimple_vuse (stmt))
1465     mark_sym_for_renaming (gimple_vop (cfun));
1466 }
1467
1468 /* Returns a new temporary variable used for the I-th variable carrying
1469    value of REF.  The variable's uid is marked in TMP_VARS.  */
1470
1471 static tree
1472 predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars)
1473 {
1474   tree type = TREE_TYPE (ref);
1475   /* We never access the components of the temporary variable in predictive
1476      commoning.  */
1477   tree var = create_tmp_reg (type, get_lsm_tmp_name (ref, i));
1478
1479   add_referenced_var (var);
1480   bitmap_set_bit (tmp_vars, DECL_UID (var));
1481   return var;
1482 }
1483
1484 /* Creates the variables for CHAIN, as well as phi nodes for them and
1485    initialization on entry to LOOP.  Uids of the newly created
1486    temporary variables are marked in TMP_VARS.  */
1487
1488 static void
1489 initialize_root_vars (struct loop *loop, chain_p chain, bitmap tmp_vars)
1490 {
1491   unsigned i;
1492   unsigned n = chain->length;
1493   dref root = get_chain_root (chain);
1494   bool reuse_first = !chain->has_max_use_after;
1495   tree ref, init, var, next;
1496   gimple phi;
1497   gimple_seq stmts;
1498   edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1499
1500   /* If N == 0, then all the references are within the single iteration.  And
1501      since this is an nonempty chain, reuse_first cannot be true.  */
1502   gcc_assert (n > 0 || !reuse_first);
1503
1504   chain->vars = VEC_alloc (tree, heap, n + 1);
1505
1506   if (chain->type == CT_COMBINATION)
1507     ref = gimple_assign_lhs (root->stmt);
1508   else
1509     ref = DR_REF (root->ref);
1510
1511   for (i = 0; i < n + (reuse_first ? 0 : 1); i++)
1512     {
1513       var = predcom_tmp_var (ref, i, tmp_vars);
1514       VEC_quick_push (tree, chain->vars, var);
1515     }
1516   if (reuse_first)
1517     VEC_quick_push (tree, chain->vars, VEC_index (tree, chain->vars, 0));
1518
1519   FOR_EACH_VEC_ELT (tree, chain->vars, i, var)
1520     VEC_replace (tree, chain->vars, i, make_ssa_name (var, NULL));
1521
1522   for (i = 0; i < n; i++)
1523     {
1524       var = VEC_index (tree, chain->vars, i);
1525       next = VEC_index (tree, chain->vars, i + 1);
1526       init = get_init_expr (chain, i);
1527
1528       init = force_gimple_operand (init, &stmts, true, NULL_TREE);
1529       if (stmts)
1530         gsi_insert_seq_on_edge_immediate (entry, stmts);
1531
1532       phi = create_phi_node (var, loop->header);
1533       SSA_NAME_DEF_STMT (var) = phi;
1534       add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
1535       add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
1536     }
1537 }
1538
1539 /* Create the variables and initialization statement for root of chain
1540    CHAIN.  Uids of the newly created temporary variables are marked
1541    in TMP_VARS.  */
1542
1543 static void
1544 initialize_root (struct loop *loop, chain_p chain, bitmap tmp_vars)
1545 {
1546   dref root = get_chain_root (chain);
1547   bool in_lhs = (chain->type == CT_STORE_LOAD
1548                  || chain->type == CT_COMBINATION);
1549
1550   initialize_root_vars (loop, chain, tmp_vars);
1551   replace_ref_with (root->stmt,
1552                     VEC_index (tree, chain->vars, chain->length),
1553                     true, in_lhs);
1554 }
1555
1556 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1557    initialization on entry to LOOP if necessary.  The ssa name for the variable
1558    is stored in VARS.  If WRITTEN is true, also a phi node to copy its value
1559    around the loop is created.  Uid of the newly created temporary variable
1560    is marked in TMP_VARS.  INITS is the list containing the (single)
1561    initializer.  */
1562
1563 static void
1564 initialize_root_vars_lm (struct loop *loop, dref root, bool written,
1565                          VEC(tree, heap) **vars, VEC(tree, heap) *inits,
1566                          bitmap tmp_vars)
1567 {
1568   unsigned i;
1569   tree ref = DR_REF (root->ref), init, var, next;
1570   gimple_seq stmts;
1571   gimple phi;
1572   edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1573
1574   /* Find the initializer for the variable, and check that it cannot
1575      trap.  */
1576   init = VEC_index (tree, inits, 0);
1577
1578   *vars = VEC_alloc (tree, heap, written ? 2 : 1);
1579   var = predcom_tmp_var (ref, 0, tmp_vars);
1580   VEC_quick_push (tree, *vars, var);
1581   if (written)
1582     VEC_quick_push (tree, *vars, VEC_index (tree, *vars, 0));
1583
1584   FOR_EACH_VEC_ELT (tree, *vars, i, var)
1585     VEC_replace (tree, *vars, i, make_ssa_name (var, NULL));
1586
1587   var = VEC_index (tree, *vars, 0);
1588
1589   init = force_gimple_operand (init, &stmts, written, NULL_TREE);
1590   if (stmts)
1591     gsi_insert_seq_on_edge_immediate (entry, stmts);
1592
1593   if (written)
1594     {
1595       next = VEC_index (tree, *vars, 1);
1596       phi = create_phi_node (var, loop->header);
1597       SSA_NAME_DEF_STMT (var) = phi;
1598       add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
1599       add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
1600     }
1601   else
1602     {
1603       gimple init_stmt = gimple_build_assign (var, init);
1604       mark_virtual_ops_for_renaming (init_stmt);
1605       gsi_insert_on_edge_immediate (entry, init_stmt);
1606     }
1607 }
1608
1609
1610 /* Execute load motion for references in chain CHAIN.  Uids of the newly
1611    created temporary variables are marked in TMP_VARS.  */
1612
1613 static void
1614 execute_load_motion (struct loop *loop, chain_p chain, bitmap tmp_vars)
1615 {
1616   VEC (tree, heap) *vars;
1617   dref a;
1618   unsigned n_writes = 0, ridx, i;
1619   tree var;
1620
1621   gcc_assert (chain->type == CT_INVARIANT);
1622   gcc_assert (!chain->combined);
1623   FOR_EACH_VEC_ELT (dref, chain->refs, i, a)
1624     if (DR_IS_WRITE (a->ref))
1625       n_writes++;
1626
1627   /* If there are no reads in the loop, there is nothing to do.  */
1628   if (n_writes == VEC_length (dref, chain->refs))
1629     return;
1630
1631   initialize_root_vars_lm (loop, get_chain_root (chain), n_writes > 0,
1632                            &vars, chain->inits, tmp_vars);
1633
1634   ridx = 0;
1635   FOR_EACH_VEC_ELT (dref, chain->refs, i, a)
1636     {
1637       bool is_read = DR_IS_READ (a->ref);
1638       mark_virtual_ops_for_renaming (a->stmt);
1639
1640       if (DR_IS_WRITE (a->ref))
1641         {
1642           n_writes--;
1643           if (n_writes)
1644             {
1645               var = VEC_index (tree, vars, 0);
1646               var = make_ssa_name (SSA_NAME_VAR (var), NULL);
1647               VEC_replace (tree, vars, 0, var);
1648             }
1649           else
1650             ridx = 1;
1651         }
1652
1653       replace_ref_with (a->stmt, VEC_index (tree, vars, ridx),
1654                         !is_read, !is_read);
1655     }
1656
1657   VEC_free (tree, heap, vars);
1658 }
1659
1660 /* Returns the single statement in that NAME is used, excepting
1661    the looparound phi nodes contained in one of the chains.  If there is no
1662    such statement, or more statements, NULL is returned.  */
1663
1664 static gimple
1665 single_nonlooparound_use (tree name)
1666 {
1667   use_operand_p use;
1668   imm_use_iterator it;
1669   gimple stmt, ret = NULL;
1670
1671   FOR_EACH_IMM_USE_FAST (use, it, name)
1672     {
1673       stmt = USE_STMT (use);
1674
1675       if (gimple_code (stmt) == GIMPLE_PHI)
1676         {
1677           /* Ignore uses in looparound phi nodes.  Uses in other phi nodes
1678              could not be processed anyway, so just fail for them.  */
1679           if (bitmap_bit_p (looparound_phis,
1680                             SSA_NAME_VERSION (PHI_RESULT (stmt))))
1681             continue;
1682
1683           return NULL;
1684         }
1685       else if (is_gimple_debug (stmt))
1686         continue;
1687       else if (ret != NULL)
1688         return NULL;
1689       else
1690         ret = stmt;
1691     }
1692
1693   return ret;
1694 }
1695
1696 /* Remove statement STMT, as well as the chain of assignments in that it is
1697    used.  */
1698
1699 static void
1700 remove_stmt (gimple stmt)
1701 {
1702   tree name;
1703   gimple next;
1704   gimple_stmt_iterator psi;
1705
1706   if (gimple_code (stmt) == GIMPLE_PHI)
1707     {
1708       name = PHI_RESULT (stmt);
1709       next = single_nonlooparound_use (name);
1710       reset_debug_uses (stmt);
1711       psi = gsi_for_stmt (stmt);
1712       remove_phi_node (&psi, true);
1713
1714       if (!next
1715           || !gimple_assign_ssa_name_copy_p (next)
1716           || gimple_assign_rhs1 (next) != name)
1717         return;
1718
1719       stmt = next;
1720     }
1721
1722   while (1)
1723     {
1724       gimple_stmt_iterator bsi;
1725
1726       bsi = gsi_for_stmt (stmt);
1727
1728       name = gimple_assign_lhs (stmt);
1729       gcc_assert (TREE_CODE (name) == SSA_NAME);
1730
1731       next = single_nonlooparound_use (name);
1732       reset_debug_uses (stmt);
1733
1734       mark_virtual_ops_for_renaming (stmt);
1735       gsi_remove (&bsi, true);
1736       release_defs (stmt);
1737
1738       if (!next
1739           || !gimple_assign_ssa_name_copy_p (next)
1740           || gimple_assign_rhs1 (next) != name)
1741         return;
1742
1743       stmt = next;
1744     }
1745 }
1746
1747 /* Perform the predictive commoning optimization for a chain CHAIN.
1748    Uids of the newly created temporary variables are marked in TMP_VARS.*/
1749
1750 static void
1751 execute_pred_commoning_chain (struct loop *loop, chain_p chain,
1752                              bitmap tmp_vars)
1753 {
1754   unsigned i;
1755   dref a, root;
1756   tree var;
1757
1758   if (chain->combined)
1759     {
1760       /* For combined chains, just remove the statements that are used to
1761          compute the values of the expression (except for the root one).  */
1762       for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++)
1763         remove_stmt (a->stmt);
1764     }
1765   else
1766     {
1767       /* For non-combined chains, set up the variables that hold its value,
1768          and replace the uses of the original references by these
1769          variables.  */
1770       root = get_chain_root (chain);
1771       mark_virtual_ops_for_renaming (root->stmt);
1772
1773       initialize_root (loop, chain, tmp_vars);
1774       for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++)
1775         {
1776           mark_virtual_ops_for_renaming (a->stmt);
1777           var = VEC_index (tree, chain->vars, chain->length - a->distance);
1778           replace_ref_with (a->stmt, var, false, false);
1779         }
1780     }
1781 }
1782
1783 /* Determines the unroll factor necessary to remove as many temporary variable
1784    copies as possible.  CHAINS is the list of chains that will be
1785    optimized.  */
1786
1787 static unsigned
1788 determine_unroll_factor (VEC (chain_p, heap) *chains)
1789 {
1790   chain_p chain;
1791   unsigned factor = 1, af, nfactor, i;
1792   unsigned max = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
1793
1794   FOR_EACH_VEC_ELT (chain_p, chains, i, chain)
1795     {
1796       if (chain->type == CT_INVARIANT || chain->combined)
1797         continue;
1798
1799       /* The best unroll factor for this chain is equal to the number of
1800          temporary variables that we create for it.  */
1801       af = chain->length;
1802       if (chain->has_max_use_after)
1803         af++;
1804
1805       nfactor = factor * af / gcd (factor, af);
1806       if (nfactor <= max)
1807         factor = nfactor;
1808     }
1809
1810   return factor;
1811 }
1812
1813 /* Perform the predictive commoning optimization for CHAINS.
1814    Uids of the newly created temporary variables are marked in TMP_VARS.  */
1815
1816 static void
1817 execute_pred_commoning (struct loop *loop, VEC (chain_p, heap) *chains,
1818                         bitmap tmp_vars)
1819 {
1820   chain_p chain;
1821   unsigned i;
1822
1823   FOR_EACH_VEC_ELT (chain_p, chains, i, chain)
1824     {
1825       if (chain->type == CT_INVARIANT)
1826         execute_load_motion (loop, chain, tmp_vars);
1827       else
1828         execute_pred_commoning_chain (loop, chain, tmp_vars);
1829     }
1830
1831   update_ssa (TODO_update_ssa_only_virtuals);
1832 }
1833
1834 /* For each reference in CHAINS, if its defining statement is
1835    phi node, record the ssa name that is defined by it.  */
1836
1837 static void
1838 replace_phis_by_defined_names (VEC (chain_p, heap) *chains)
1839 {
1840   chain_p chain;
1841   dref a;
1842   unsigned i, j;
1843
1844   FOR_EACH_VEC_ELT (chain_p, chains, i, chain)
1845     FOR_EACH_VEC_ELT (dref, chain->refs, j, a)
1846       {
1847         if (gimple_code (a->stmt) == GIMPLE_PHI)
1848           {
1849             a->name_defined_by_phi = PHI_RESULT (a->stmt);
1850             a->stmt = NULL;
1851           }
1852       }
1853 }
1854
1855 /* For each reference in CHAINS, if name_defined_by_phi is not
1856    NULL, use it to set the stmt field.  */
1857
1858 static void
1859 replace_names_by_phis (VEC (chain_p, heap) *chains)
1860 {
1861   chain_p chain;
1862   dref a;
1863   unsigned i, j;
1864
1865   FOR_EACH_VEC_ELT (chain_p, chains, i, chain)
1866     FOR_EACH_VEC_ELT (dref, chain->refs, j, a)
1867       if (a->stmt == NULL)
1868         {
1869           a->stmt = SSA_NAME_DEF_STMT (a->name_defined_by_phi);
1870           gcc_assert (gimple_code (a->stmt) == GIMPLE_PHI);
1871           a->name_defined_by_phi = NULL_TREE;
1872         }
1873 }
1874
1875 /* Wrapper over execute_pred_commoning, to pass it as a callback
1876    to tree_transform_and_unroll_loop.  */
1877
1878 struct epcc_data
1879 {
1880   VEC (chain_p, heap) *chains;
1881   bitmap tmp_vars;
1882 };
1883
1884 static void
1885 execute_pred_commoning_cbck (struct loop *loop, void *data)
1886 {
1887   struct epcc_data *const dta = (struct epcc_data *) data;
1888
1889   /* Restore phi nodes that were replaced by ssa names before
1890      tree_transform_and_unroll_loop (see detailed description in
1891      tree_predictive_commoning_loop).  */
1892   replace_names_by_phis (dta->chains);
1893   execute_pred_commoning (loop, dta->chains, dta->tmp_vars);
1894 }
1895
1896 /* Base NAME and all the names in the chain of phi nodes that use it
1897    on variable VAR.  The phi nodes are recognized by being in the copies of
1898    the header of the LOOP.  */
1899
1900 static void
1901 base_names_in_chain_on (struct loop *loop, tree name, tree var)
1902 {
1903   gimple stmt, phi;
1904   imm_use_iterator iter;
1905
1906   SSA_NAME_VAR (name) = var;
1907
1908   while (1)
1909     {
1910       phi = NULL;
1911       FOR_EACH_IMM_USE_STMT (stmt, iter, name)
1912         {
1913           if (gimple_code (stmt) == GIMPLE_PHI
1914               && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1915             {
1916               phi = stmt;
1917               BREAK_FROM_IMM_USE_STMT (iter);
1918             }
1919         }
1920       if (!phi)
1921         return;
1922
1923       name = PHI_RESULT (phi);
1924       SSA_NAME_VAR (name) = var;
1925     }
1926 }
1927
1928 /* Given an unrolled LOOP after predictive commoning, remove the
1929    register copies arising from phi nodes by changing the base
1930    variables of SSA names.  TMP_VARS is the set of the temporary variables
1931    for those we want to perform this.  */
1932
1933 static void
1934 eliminate_temp_copies (struct loop *loop, bitmap tmp_vars)
1935 {
1936   edge e;
1937   gimple phi, stmt;
1938   tree name, use, var;
1939   gimple_stmt_iterator psi;
1940
1941   e = loop_latch_edge (loop);
1942   for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1943     {
1944       phi = gsi_stmt (psi);
1945       name = PHI_RESULT (phi);
1946       var = SSA_NAME_VAR (name);
1947       if (!bitmap_bit_p (tmp_vars, DECL_UID (var)))
1948         continue;
1949       use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1950       gcc_assert (TREE_CODE (use) == SSA_NAME);
1951
1952       /* Base all the ssa names in the ud and du chain of NAME on VAR.  */
1953       stmt = SSA_NAME_DEF_STMT (use);
1954       while (gimple_code (stmt) == GIMPLE_PHI
1955              /* In case we could not unroll the loop enough to eliminate
1956                 all copies, we may reach the loop header before the defining
1957                 statement (in that case, some register copies will be present
1958                 in loop latch in the final code, corresponding to the newly
1959                 created looparound phi nodes).  */
1960              && gimple_bb (stmt) != loop->header)
1961         {
1962           gcc_assert (single_pred_p (gimple_bb (stmt)));
1963           use = PHI_ARG_DEF (stmt, 0);
1964           stmt = SSA_NAME_DEF_STMT (use);
1965         }
1966
1967       base_names_in_chain_on (loop, use, var);
1968     }
1969 }
1970
1971 /* Returns true if CHAIN is suitable to be combined.  */
1972
1973 static bool
1974 chain_can_be_combined_p (chain_p chain)
1975 {
1976   return (!chain->combined
1977           && (chain->type == CT_LOAD || chain->type == CT_COMBINATION));
1978 }
1979
1980 /* Returns the modify statement that uses NAME.  Skips over assignment
1981    statements, NAME is replaced with the actual name used in the returned
1982    statement.  */
1983
1984 static gimple
1985 find_use_stmt (tree *name)
1986 {
1987   gimple stmt;
1988   tree rhs, lhs;
1989
1990   /* Skip over assignments.  */
1991   while (1)
1992     {
1993       stmt = single_nonlooparound_use (*name);
1994       if (!stmt)
1995         return NULL;
1996
1997       if (gimple_code (stmt) != GIMPLE_ASSIGN)
1998         return NULL;
1999
2000       lhs = gimple_assign_lhs (stmt);
2001       if (TREE_CODE (lhs) != SSA_NAME)
2002         return NULL;
2003
2004       if (gimple_assign_copy_p (stmt))
2005         {
2006           rhs = gimple_assign_rhs1 (stmt);
2007           if (rhs != *name)
2008             return NULL;
2009
2010           *name = lhs;
2011         }
2012       else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
2013                == GIMPLE_BINARY_RHS)
2014         return stmt;
2015       else
2016         return NULL;
2017     }
2018 }
2019
2020 /* Returns true if we may perform reassociation for operation CODE in TYPE.  */
2021
2022 static bool
2023 may_reassociate_p (tree type, enum tree_code code)
2024 {
2025   if (FLOAT_TYPE_P (type)
2026       && !flag_unsafe_math_optimizations)
2027     return false;
2028
2029   return (commutative_tree_code (code)
2030           && associative_tree_code (code));
2031 }
2032
2033 /* If the operation used in STMT is associative and commutative, go through the
2034    tree of the same operations and returns its root.  Distance to the root
2035    is stored in DISTANCE.  */
2036
2037 static gimple
2038 find_associative_operation_root (gimple stmt, unsigned *distance)
2039 {
2040   tree lhs;
2041   gimple next;
2042   enum tree_code code = gimple_assign_rhs_code (stmt);
2043   tree type = TREE_TYPE (gimple_assign_lhs (stmt));
2044   unsigned dist = 0;
2045
2046   if (!may_reassociate_p (type, code))
2047     return NULL;
2048
2049   while (1)
2050     {
2051       lhs = gimple_assign_lhs (stmt);
2052       gcc_assert (TREE_CODE (lhs) == SSA_NAME);
2053
2054       next = find_use_stmt (&lhs);
2055       if (!next
2056           || gimple_assign_rhs_code (next) != code)
2057         break;
2058
2059       stmt = next;
2060       dist++;
2061     }
2062
2063   if (distance)
2064     *distance = dist;
2065   return stmt;
2066 }
2067
2068 /* Returns the common statement in that NAME1 and NAME2 have a use.  If there
2069    is no such statement, returns NULL_TREE.  In case the operation used on
2070    NAME1 and NAME2 is associative and commutative, returns the root of the
2071    tree formed by this operation instead of the statement that uses NAME1 or
2072    NAME2.  */
2073
2074 static gimple
2075 find_common_use_stmt (tree *name1, tree *name2)
2076 {
2077   gimple stmt1, stmt2;
2078
2079   stmt1 = find_use_stmt (name1);
2080   if (!stmt1)
2081     return NULL;
2082
2083   stmt2 = find_use_stmt (name2);
2084   if (!stmt2)
2085     return NULL;
2086
2087   if (stmt1 == stmt2)
2088     return stmt1;
2089
2090   stmt1 = find_associative_operation_root (stmt1, NULL);
2091   if (!stmt1)
2092     return NULL;
2093   stmt2 = find_associative_operation_root (stmt2, NULL);
2094   if (!stmt2)
2095     return NULL;
2096
2097   return (stmt1 == stmt2 ? stmt1 : NULL);
2098 }
2099
2100 /* Checks whether R1 and R2 are combined together using CODE, with the result
2101    in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2102    if it is true.  If CODE is ERROR_MARK, set these values instead.  */
2103
2104 static bool
2105 combinable_refs_p (dref r1, dref r2,
2106                    enum tree_code *code, bool *swap, tree *rslt_type)
2107 {
2108   enum tree_code acode;
2109   bool aswap;
2110   tree atype;
2111   tree name1, name2;
2112   gimple stmt;
2113
2114   name1 = name_for_ref (r1);
2115   name2 = name_for_ref (r2);
2116   gcc_assert (name1 != NULL_TREE && name2 != NULL_TREE);
2117
2118   stmt = find_common_use_stmt (&name1, &name2);
2119
2120   if (!stmt)
2121     return false;
2122
2123   acode = gimple_assign_rhs_code (stmt);
2124   aswap = (!commutative_tree_code (acode)
2125            && gimple_assign_rhs1 (stmt) != name1);
2126   atype = TREE_TYPE (gimple_assign_lhs (stmt));
2127
2128   if (*code == ERROR_MARK)
2129     {
2130       *code = acode;
2131       *swap = aswap;
2132       *rslt_type = atype;
2133       return true;
2134     }
2135
2136   return (*code == acode
2137           && *swap == aswap
2138           && *rslt_type == atype);
2139 }
2140
2141 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2142    an assignment of the remaining operand.  */
2143
2144 static void
2145 remove_name_from_operation (gimple stmt, tree op)
2146 {
2147   tree other_op;
2148   gimple_stmt_iterator si;
2149
2150   gcc_assert (is_gimple_assign (stmt));
2151
2152   if (gimple_assign_rhs1 (stmt) == op)
2153     other_op = gimple_assign_rhs2 (stmt);
2154   else
2155     other_op = gimple_assign_rhs1 (stmt);
2156
2157   si = gsi_for_stmt (stmt);
2158   gimple_assign_set_rhs_from_tree (&si, other_op);
2159
2160   /* We should not have reallocated STMT.  */
2161   gcc_assert (gsi_stmt (si) == stmt);
2162
2163   update_stmt (stmt);
2164 }
2165
2166 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2167    are combined in a single statement, and returns this statement.  */
2168
2169 static gimple
2170 reassociate_to_the_same_stmt (tree name1, tree name2)
2171 {
2172   gimple stmt1, stmt2, root1, root2, s1, s2;
2173   gimple new_stmt, tmp_stmt;
2174   tree new_name, tmp_name, var, r1, r2;
2175   unsigned dist1, dist2;
2176   enum tree_code code;
2177   tree type = TREE_TYPE (name1);
2178   gimple_stmt_iterator bsi;
2179
2180   stmt1 = find_use_stmt (&name1);
2181   stmt2 = find_use_stmt (&name2);
2182   root1 = find_associative_operation_root (stmt1, &dist1);
2183   root2 = find_associative_operation_root (stmt2, &dist2);
2184   code = gimple_assign_rhs_code (stmt1);
2185
2186   gcc_assert (root1 && root2 && root1 == root2
2187               && code == gimple_assign_rhs_code (stmt2));
2188
2189   /* Find the root of the nearest expression in that both NAME1 and NAME2
2190      are used.  */
2191   r1 = name1;
2192   s1 = stmt1;
2193   r2 = name2;
2194   s2 = stmt2;
2195
2196   while (dist1 > dist2)
2197     {
2198       s1 = find_use_stmt (&r1);
2199       r1 = gimple_assign_lhs (s1);
2200       dist1--;
2201     }
2202   while (dist2 > dist1)
2203     {
2204       s2 = find_use_stmt (&r2);
2205       r2 = gimple_assign_lhs (s2);
2206       dist2--;
2207     }
2208
2209   while (s1 != s2)
2210     {
2211       s1 = find_use_stmt (&r1);
2212       r1 = gimple_assign_lhs (s1);
2213       s2 = find_use_stmt (&r2);
2214       r2 = gimple_assign_lhs (s2);
2215     }
2216
2217   /* Remove NAME1 and NAME2 from the statements in that they are used
2218      currently.  */
2219   remove_name_from_operation (stmt1, name1);
2220   remove_name_from_operation (stmt2, name2);
2221
2222   /* Insert the new statement combining NAME1 and NAME2 before S1, and
2223      combine it with the rhs of S1.  */
2224   var = create_tmp_reg (type, "predreastmp");
2225   add_referenced_var (var);
2226   new_name = make_ssa_name (var, NULL);
2227   new_stmt = gimple_build_assign_with_ops (code, new_name, name1, name2);
2228
2229   var = create_tmp_reg (type, "predreastmp");
2230   add_referenced_var (var);
2231   tmp_name = make_ssa_name (var, NULL);
2232
2233   /* Rhs of S1 may now be either a binary expression with operation
2234      CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2235      so that name1 or name2 was removed from it).  */
2236   tmp_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (s1),
2237                                            tmp_name,
2238                                            gimple_assign_rhs1 (s1),
2239                                            gimple_assign_rhs2 (s1));
2240
2241   bsi = gsi_for_stmt (s1);
2242   gimple_assign_set_rhs_with_ops (&bsi, code, new_name, tmp_name);
2243   s1 = gsi_stmt (bsi);
2244   update_stmt (s1);
2245
2246   gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
2247   gsi_insert_before (&bsi, tmp_stmt, GSI_SAME_STMT);
2248
2249   return new_stmt;
2250 }
2251
2252 /* Returns the statement that combines references R1 and R2.  In case R1
2253    and R2 are not used in the same statement, but they are used with an
2254    associative and commutative operation in the same expression, reassociate
2255    the expression so that they are used in the same statement.  */
2256
2257 static gimple
2258 stmt_combining_refs (dref r1, dref r2)
2259 {
2260   gimple stmt1, stmt2;
2261   tree name1 = name_for_ref (r1);
2262   tree name2 = name_for_ref (r2);
2263
2264   stmt1 = find_use_stmt (&name1);
2265   stmt2 = find_use_stmt (&name2);
2266   if (stmt1 == stmt2)
2267     return stmt1;
2268
2269   return reassociate_to_the_same_stmt (name1, name2);
2270 }
2271
2272 /* Tries to combine chains CH1 and CH2 together.  If this succeeds, the
2273    description of the new chain is returned, otherwise we return NULL.  */
2274
2275 static chain_p
2276 combine_chains (chain_p ch1, chain_p ch2)
2277 {
2278   dref r1, r2, nw;
2279   enum tree_code op = ERROR_MARK;
2280   bool swap = false;
2281   chain_p new_chain;
2282   unsigned i;
2283   gimple root_stmt;
2284   tree rslt_type = NULL_TREE;
2285
2286   if (ch1 == ch2)
2287     return NULL;
2288   if (ch1->length != ch2->length)
2289     return NULL;
2290
2291   if (VEC_length (dref, ch1->refs) != VEC_length (dref, ch2->refs))
2292     return NULL;
2293
2294   for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
2295                && VEC_iterate (dref, ch2->refs, i, r2)); i++)
2296     {
2297       if (r1->distance != r2->distance)
2298         return NULL;
2299
2300       if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type))
2301         return NULL;
2302     }
2303
2304   if (swap)
2305     {
2306       chain_p tmp = ch1;
2307       ch1 = ch2;
2308       ch2 = tmp;
2309     }
2310
2311   new_chain = XCNEW (struct chain);
2312   new_chain->type = CT_COMBINATION;
2313   new_chain->op = op;
2314   new_chain->ch1 = ch1;
2315   new_chain->ch2 = ch2;
2316   new_chain->rslt_type = rslt_type;
2317   new_chain->length = ch1->length;
2318
2319   for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
2320                && VEC_iterate (dref, ch2->refs, i, r2)); i++)
2321     {
2322       nw = XCNEW (struct dref_d);
2323       nw->stmt = stmt_combining_refs (r1, r2);
2324       nw->distance = r1->distance;
2325
2326       VEC_safe_push (dref, heap, new_chain->refs, nw);
2327     }
2328
2329   new_chain->has_max_use_after = false;
2330   root_stmt = get_chain_root (new_chain)->stmt;
2331   for (i = 1; VEC_iterate (dref, new_chain->refs, i, nw); i++)
2332     {
2333       if (nw->distance == new_chain->length
2334           && !stmt_dominates_stmt_p (nw->stmt, root_stmt))
2335         {
2336           new_chain->has_max_use_after = true;
2337           break;
2338         }
2339     }
2340
2341   ch1->combined = true;
2342   ch2->combined = true;
2343   return new_chain;
2344 }
2345
2346 /* Try to combine the CHAINS.  */
2347
2348 static void
2349 try_combine_chains (VEC (chain_p, heap) **chains)
2350 {
2351   unsigned i, j;
2352   chain_p ch1, ch2, cch;
2353   VEC (chain_p, heap) *worklist = NULL;
2354
2355   FOR_EACH_VEC_ELT (chain_p, *chains, i, ch1)
2356     if (chain_can_be_combined_p (ch1))
2357       VEC_safe_push (chain_p, heap, worklist, ch1);
2358
2359   while (!VEC_empty (chain_p, worklist))
2360     {
2361       ch1 = VEC_pop (chain_p, worklist);
2362       if (!chain_can_be_combined_p (ch1))
2363         continue;
2364
2365       FOR_EACH_VEC_ELT (chain_p, *chains, j, ch2)
2366         {
2367           if (!chain_can_be_combined_p (ch2))
2368             continue;
2369
2370           cch = combine_chains (ch1, ch2);
2371           if (cch)
2372             {
2373               VEC_safe_push (chain_p, heap, worklist, cch);
2374               VEC_safe_push (chain_p, heap, *chains, cch);
2375               break;
2376             }
2377         }
2378     }
2379 }
2380
2381 /* Prepare initializers for CHAIN in LOOP.  Returns false if this is
2382    impossible because one of these initializers may trap, true otherwise.  */
2383
2384 static bool
2385 prepare_initializers_chain (struct loop *loop, chain_p chain)
2386 {
2387   unsigned i, n = (chain->type == CT_INVARIANT) ? 1 : chain->length;
2388   struct data_reference *dr = get_chain_root (chain)->ref;
2389   tree init;
2390   gimple_seq stmts;
2391   dref laref;
2392   edge entry = loop_preheader_edge (loop);
2393
2394   /* Find the initializers for the variables, and check that they cannot
2395      trap.  */
2396   chain->inits = VEC_alloc (tree, heap, n);
2397   for (i = 0; i < n; i++)
2398     VEC_quick_push (tree, chain->inits, NULL_TREE);
2399
2400   /* If we have replaced some looparound phi nodes, use their initializers
2401      instead of creating our own.  */
2402   FOR_EACH_VEC_ELT (dref, chain->refs, i, laref)
2403     {
2404       if (gimple_code (laref->stmt) != GIMPLE_PHI)
2405         continue;
2406
2407       gcc_assert (laref->distance > 0);
2408       VEC_replace (tree, chain->inits, n - laref->distance,
2409                    PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry));
2410     }
2411
2412   for (i = 0; i < n; i++)
2413     {
2414       if (VEC_index (tree, chain->inits, i) != NULL_TREE)
2415         continue;
2416
2417       init = ref_at_iteration (loop, DR_REF (dr), (int) i - n);
2418       if (!init)
2419         return false;
2420
2421       if (!chain->all_always_accessed && tree_could_trap_p (init))
2422         return false;
2423
2424       init = force_gimple_operand (init, &stmts, false, NULL_TREE);
2425       if (stmts)
2426         gsi_insert_seq_on_edge_immediate (entry, stmts);
2427
2428       VEC_replace (tree, chain->inits, i, init);
2429     }
2430
2431   return true;
2432 }
2433
2434 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2435    be used because the initializers might trap.  */
2436
2437 static void
2438 prepare_initializers (struct loop *loop, VEC (chain_p, heap) *chains)
2439 {
2440   chain_p chain;
2441   unsigned i;
2442
2443   for (i = 0; i < VEC_length (chain_p, chains); )
2444     {
2445       chain = VEC_index (chain_p, chains, i);
2446       if (prepare_initializers_chain (loop, chain))
2447         i++;
2448       else
2449         {
2450           release_chain (chain);
2451           VEC_unordered_remove (chain_p, chains, i);
2452         }
2453     }
2454 }
2455
2456 /* Performs predictive commoning for LOOP.  Returns true if LOOP was
2457    unrolled.  */
2458
2459 static bool
2460 tree_predictive_commoning_loop (struct loop *loop)
2461 {
2462   VEC (loop_p, heap) *loop_nest;
2463   VEC (data_reference_p, heap) *datarefs;
2464   VEC (ddr_p, heap) *dependences;
2465   struct component *components;
2466   VEC (chain_p, heap) *chains = NULL;
2467   unsigned unroll_factor;
2468   struct tree_niter_desc desc;
2469   bool unroll = false;
2470   edge exit;
2471   bitmap tmp_vars;
2472
2473   if (dump_file && (dump_flags & TDF_DETAILS))
2474     fprintf (dump_file, "Processing loop %d\n",  loop->num);
2475
2476   /* Find the data references and split them into components according to their
2477      dependence relations.  */
2478   datarefs = VEC_alloc (data_reference_p, heap, 10);
2479   dependences = VEC_alloc (ddr_p, heap, 10);
2480   loop_nest = VEC_alloc (loop_p, heap, 3);
2481   if (! compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs,
2482                                            &dependences))
2483     {
2484       if (dump_file && (dump_flags & TDF_DETAILS))
2485         fprintf (dump_file, "Cannot analyze data dependencies\n");
2486       VEC_free (loop_p, heap, loop_nest);
2487       free_data_refs (datarefs);
2488       free_dependence_relations (dependences);
2489       return false;
2490     }
2491
2492   if (dump_file && (dump_flags & TDF_DETAILS))
2493     dump_data_dependence_relations (dump_file, dependences);
2494
2495   components = split_data_refs_to_components (loop, datarefs, dependences);
2496   VEC_free (loop_p, heap, loop_nest);
2497   free_dependence_relations (dependences);
2498   if (!components)
2499     {
2500       free_data_refs (datarefs);
2501       return false;
2502     }
2503
2504   if (dump_file && (dump_flags & TDF_DETAILS))
2505     {
2506       fprintf (dump_file, "Initial state:\n\n");
2507       dump_components (dump_file, components);
2508     }
2509
2510   /* Find the suitable components and split them into chains.  */
2511   components = filter_suitable_components (loop, components);
2512
2513   tmp_vars = BITMAP_ALLOC (NULL);
2514   looparound_phis = BITMAP_ALLOC (NULL);
2515   determine_roots (loop, components, &chains);
2516   release_components (components);
2517
2518   if (!chains)
2519     {
2520       if (dump_file && (dump_flags & TDF_DETAILS))
2521         fprintf (dump_file,
2522                  "Predictive commoning failed: no suitable chains\n");
2523       goto end;
2524     }
2525   prepare_initializers (loop, chains);
2526
2527   /* Try to combine the chains that are always worked with together.  */
2528   try_combine_chains (&chains);
2529
2530   if (dump_file && (dump_flags & TDF_DETAILS))
2531     {
2532       fprintf (dump_file, "Before commoning:\n\n");
2533       dump_chains (dump_file, chains);
2534     }
2535
2536   /* Determine the unroll factor, and if the loop should be unrolled, ensure
2537      that its number of iterations is divisible by the factor.  */
2538   unroll_factor = determine_unroll_factor (chains);
2539   scev_reset ();
2540   unroll = (unroll_factor > 1
2541             && can_unroll_loop_p (loop, unroll_factor, &desc));
2542   exit = single_dom_exit (loop);
2543
2544   /* Execute the predictive commoning transformations, and possibly unroll the
2545      loop.  */
2546   if (unroll)
2547     {
2548       struct epcc_data dta;
2549
2550       if (dump_file && (dump_flags & TDF_DETAILS))
2551         fprintf (dump_file, "Unrolling %u times.\n", unroll_factor);
2552
2553       dta.chains = chains;
2554       dta.tmp_vars = tmp_vars;
2555
2556       update_ssa (TODO_update_ssa_only_virtuals);
2557
2558       /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2559          execute_pred_commoning_cbck is called may cause phi nodes to be
2560          reallocated, which is a problem since CHAINS may point to these
2561          statements.  To fix this, we store the ssa names defined by the
2562          phi nodes here instead of the phi nodes themselves, and restore
2563          the phi nodes in execute_pred_commoning_cbck.  A bit hacky.  */
2564       replace_phis_by_defined_names (chains);
2565
2566       tree_transform_and_unroll_loop (loop, unroll_factor, exit, &desc,
2567                                       execute_pred_commoning_cbck, &dta);
2568       eliminate_temp_copies (loop, tmp_vars);
2569     }
2570   else
2571     {
2572       if (dump_file && (dump_flags & TDF_DETAILS))
2573         fprintf (dump_file,
2574                  "Executing predictive commoning without unrolling.\n");
2575       execute_pred_commoning (loop, chains, tmp_vars);
2576     }
2577
2578 end: ;
2579   release_chains (chains);
2580   free_data_refs (datarefs);
2581   BITMAP_FREE (tmp_vars);
2582   BITMAP_FREE (looparound_phis);
2583
2584   free_affine_expand_cache (&name_expansions);
2585
2586   return unroll;
2587 }
2588
2589 /* Runs predictive commoning.  */
2590
2591 unsigned
2592 tree_predictive_commoning (void)
2593 {
2594   bool unrolled = false;
2595   struct loop *loop;
2596   loop_iterator li;
2597   unsigned ret = 0;
2598
2599   initialize_original_copy_tables ();
2600   FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
2601     if (optimize_loop_for_speed_p (loop))
2602       {
2603         unrolled |= tree_predictive_commoning_loop (loop);
2604       }
2605
2606   if (unrolled)
2607     {
2608       scev_reset ();
2609       ret = TODO_cleanup_cfg;
2610     }
2611   free_original_copy_tables ();
2612
2613   return ret;
2614 }