Merge branch 'vendor/GCC47'
[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       /* A simple post-dominance check - make sure the combination
2122          is executed under the same condition as the references.  */
2123       || (gimple_bb (stmt) != gimple_bb (r1->stmt)
2124           && gimple_bb (stmt) != gimple_bb (r2->stmt)))
2125     return false;
2126
2127   acode = gimple_assign_rhs_code (stmt);
2128   aswap = (!commutative_tree_code (acode)
2129            && gimple_assign_rhs1 (stmt) != name1);
2130   atype = TREE_TYPE (gimple_assign_lhs (stmt));
2131
2132   if (*code == ERROR_MARK)
2133     {
2134       *code = acode;
2135       *swap = aswap;
2136       *rslt_type = atype;
2137       return true;
2138     }
2139
2140   return (*code == acode
2141           && *swap == aswap
2142           && *rslt_type == atype);
2143 }
2144
2145 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2146    an assignment of the remaining operand.  */
2147
2148 static void
2149 remove_name_from_operation (gimple stmt, tree op)
2150 {
2151   tree other_op;
2152   gimple_stmt_iterator si;
2153
2154   gcc_assert (is_gimple_assign (stmt));
2155
2156   if (gimple_assign_rhs1 (stmt) == op)
2157     other_op = gimple_assign_rhs2 (stmt);
2158   else
2159     other_op = gimple_assign_rhs1 (stmt);
2160
2161   si = gsi_for_stmt (stmt);
2162   gimple_assign_set_rhs_from_tree (&si, other_op);
2163
2164   /* We should not have reallocated STMT.  */
2165   gcc_assert (gsi_stmt (si) == stmt);
2166
2167   update_stmt (stmt);
2168 }
2169
2170 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2171    are combined in a single statement, and returns this statement.  */
2172
2173 static gimple
2174 reassociate_to_the_same_stmt (tree name1, tree name2)
2175 {
2176   gimple stmt1, stmt2, root1, root2, s1, s2;
2177   gimple new_stmt, tmp_stmt;
2178   tree new_name, tmp_name, var, r1, r2;
2179   unsigned dist1, dist2;
2180   enum tree_code code;
2181   tree type = TREE_TYPE (name1);
2182   gimple_stmt_iterator bsi;
2183
2184   stmt1 = find_use_stmt (&name1);
2185   stmt2 = find_use_stmt (&name2);
2186   root1 = find_associative_operation_root (stmt1, &dist1);
2187   root2 = find_associative_operation_root (stmt2, &dist2);
2188   code = gimple_assign_rhs_code (stmt1);
2189
2190   gcc_assert (root1 && root2 && root1 == root2
2191               && code == gimple_assign_rhs_code (stmt2));
2192
2193   /* Find the root of the nearest expression in that both NAME1 and NAME2
2194      are used.  */
2195   r1 = name1;
2196   s1 = stmt1;
2197   r2 = name2;
2198   s2 = stmt2;
2199
2200   while (dist1 > dist2)
2201     {
2202       s1 = find_use_stmt (&r1);
2203       r1 = gimple_assign_lhs (s1);
2204       dist1--;
2205     }
2206   while (dist2 > dist1)
2207     {
2208       s2 = find_use_stmt (&r2);
2209       r2 = gimple_assign_lhs (s2);
2210       dist2--;
2211     }
2212
2213   while (s1 != s2)
2214     {
2215       s1 = find_use_stmt (&r1);
2216       r1 = gimple_assign_lhs (s1);
2217       s2 = find_use_stmt (&r2);
2218       r2 = gimple_assign_lhs (s2);
2219     }
2220
2221   /* Remove NAME1 and NAME2 from the statements in that they are used
2222      currently.  */
2223   remove_name_from_operation (stmt1, name1);
2224   remove_name_from_operation (stmt2, name2);
2225
2226   /* Insert the new statement combining NAME1 and NAME2 before S1, and
2227      combine it with the rhs of S1.  */
2228   var = create_tmp_reg (type, "predreastmp");
2229   add_referenced_var (var);
2230   new_name = make_ssa_name (var, NULL);
2231   new_stmt = gimple_build_assign_with_ops (code, new_name, name1, name2);
2232
2233   var = create_tmp_reg (type, "predreastmp");
2234   add_referenced_var (var);
2235   tmp_name = make_ssa_name (var, NULL);
2236
2237   /* Rhs of S1 may now be either a binary expression with operation
2238      CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2239      so that name1 or name2 was removed from it).  */
2240   tmp_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (s1),
2241                                            tmp_name,
2242                                            gimple_assign_rhs1 (s1),
2243                                            gimple_assign_rhs2 (s1));
2244
2245   bsi = gsi_for_stmt (s1);
2246   gimple_assign_set_rhs_with_ops (&bsi, code, new_name, tmp_name);
2247   s1 = gsi_stmt (bsi);
2248   update_stmt (s1);
2249
2250   gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
2251   gsi_insert_before (&bsi, tmp_stmt, GSI_SAME_STMT);
2252
2253   return new_stmt;
2254 }
2255
2256 /* Returns the statement that combines references R1 and R2.  In case R1
2257    and R2 are not used in the same statement, but they are used with an
2258    associative and commutative operation in the same expression, reassociate
2259    the expression so that they are used in the same statement.  */
2260
2261 static gimple
2262 stmt_combining_refs (dref r1, dref r2)
2263 {
2264   gimple stmt1, stmt2;
2265   tree name1 = name_for_ref (r1);
2266   tree name2 = name_for_ref (r2);
2267
2268   stmt1 = find_use_stmt (&name1);
2269   stmt2 = find_use_stmt (&name2);
2270   if (stmt1 == stmt2)
2271     return stmt1;
2272
2273   return reassociate_to_the_same_stmt (name1, name2);
2274 }
2275
2276 /* Tries to combine chains CH1 and CH2 together.  If this succeeds, the
2277    description of the new chain is returned, otherwise we return NULL.  */
2278
2279 static chain_p
2280 combine_chains (chain_p ch1, chain_p ch2)
2281 {
2282   dref r1, r2, nw;
2283   enum tree_code op = ERROR_MARK;
2284   bool swap = false;
2285   chain_p new_chain;
2286   unsigned i;
2287   gimple root_stmt;
2288   tree rslt_type = NULL_TREE;
2289
2290   if (ch1 == ch2)
2291     return NULL;
2292   if (ch1->length != ch2->length)
2293     return NULL;
2294
2295   if (VEC_length (dref, ch1->refs) != VEC_length (dref, ch2->refs))
2296     return NULL;
2297
2298   for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
2299                && VEC_iterate (dref, ch2->refs, i, r2)); i++)
2300     {
2301       if (r1->distance != r2->distance)
2302         return NULL;
2303
2304       if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type))
2305         return NULL;
2306     }
2307
2308   if (swap)
2309     {
2310       chain_p tmp = ch1;
2311       ch1 = ch2;
2312       ch2 = tmp;
2313     }
2314
2315   new_chain = XCNEW (struct chain);
2316   new_chain->type = CT_COMBINATION;
2317   new_chain->op = op;
2318   new_chain->ch1 = ch1;
2319   new_chain->ch2 = ch2;
2320   new_chain->rslt_type = rslt_type;
2321   new_chain->length = ch1->length;
2322
2323   for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
2324                && VEC_iterate (dref, ch2->refs, i, r2)); i++)
2325     {
2326       nw = XCNEW (struct dref_d);
2327       nw->stmt = stmt_combining_refs (r1, r2);
2328       nw->distance = r1->distance;
2329
2330       VEC_safe_push (dref, heap, new_chain->refs, nw);
2331     }
2332
2333   new_chain->has_max_use_after = false;
2334   root_stmt = get_chain_root (new_chain)->stmt;
2335   for (i = 1; VEC_iterate (dref, new_chain->refs, i, nw); i++)
2336     {
2337       if (nw->distance == new_chain->length
2338           && !stmt_dominates_stmt_p (nw->stmt, root_stmt))
2339         {
2340           new_chain->has_max_use_after = true;
2341           break;
2342         }
2343     }
2344
2345   ch1->combined = true;
2346   ch2->combined = true;
2347   return new_chain;
2348 }
2349
2350 /* Try to combine the CHAINS.  */
2351
2352 static void
2353 try_combine_chains (VEC (chain_p, heap) **chains)
2354 {
2355   unsigned i, j;
2356   chain_p ch1, ch2, cch;
2357   VEC (chain_p, heap) *worklist = NULL;
2358
2359   FOR_EACH_VEC_ELT (chain_p, *chains, i, ch1)
2360     if (chain_can_be_combined_p (ch1))
2361       VEC_safe_push (chain_p, heap, worklist, ch1);
2362
2363   while (!VEC_empty (chain_p, worklist))
2364     {
2365       ch1 = VEC_pop (chain_p, worklist);
2366       if (!chain_can_be_combined_p (ch1))
2367         continue;
2368
2369       FOR_EACH_VEC_ELT (chain_p, *chains, j, ch2)
2370         {
2371           if (!chain_can_be_combined_p (ch2))
2372             continue;
2373
2374           cch = combine_chains (ch1, ch2);
2375           if (cch)
2376             {
2377               VEC_safe_push (chain_p, heap, worklist, cch);
2378               VEC_safe_push (chain_p, heap, *chains, cch);
2379               break;
2380             }
2381         }
2382     }
2383 }
2384
2385 /* Prepare initializers for CHAIN in LOOP.  Returns false if this is
2386    impossible because one of these initializers may trap, true otherwise.  */
2387
2388 static bool
2389 prepare_initializers_chain (struct loop *loop, chain_p chain)
2390 {
2391   unsigned i, n = (chain->type == CT_INVARIANT) ? 1 : chain->length;
2392   struct data_reference *dr = get_chain_root (chain)->ref;
2393   tree init;
2394   gimple_seq stmts;
2395   dref laref;
2396   edge entry = loop_preheader_edge (loop);
2397
2398   /* Find the initializers for the variables, and check that they cannot
2399      trap.  */
2400   chain->inits = VEC_alloc (tree, heap, n);
2401   for (i = 0; i < n; i++)
2402     VEC_quick_push (tree, chain->inits, NULL_TREE);
2403
2404   /* If we have replaced some looparound phi nodes, use their initializers
2405      instead of creating our own.  */
2406   FOR_EACH_VEC_ELT (dref, chain->refs, i, laref)
2407     {
2408       if (gimple_code (laref->stmt) != GIMPLE_PHI)
2409         continue;
2410
2411       gcc_assert (laref->distance > 0);
2412       VEC_replace (tree, chain->inits, n - laref->distance,
2413                    PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry));
2414     }
2415
2416   for (i = 0; i < n; i++)
2417     {
2418       if (VEC_index (tree, chain->inits, i) != NULL_TREE)
2419         continue;
2420
2421       init = ref_at_iteration (loop, DR_REF (dr), (int) i - n);
2422       if (!init)
2423         return false;
2424
2425       if (!chain->all_always_accessed && tree_could_trap_p (init))
2426         return false;
2427
2428       init = force_gimple_operand (init, &stmts, false, NULL_TREE);
2429       if (stmts)
2430         gsi_insert_seq_on_edge_immediate (entry, stmts);
2431
2432       VEC_replace (tree, chain->inits, i, init);
2433     }
2434
2435   return true;
2436 }
2437
2438 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2439    be used because the initializers might trap.  */
2440
2441 static void
2442 prepare_initializers (struct loop *loop, VEC (chain_p, heap) *chains)
2443 {
2444   chain_p chain;
2445   unsigned i;
2446
2447   for (i = 0; i < VEC_length (chain_p, chains); )
2448     {
2449       chain = VEC_index (chain_p, chains, i);
2450       if (prepare_initializers_chain (loop, chain))
2451         i++;
2452       else
2453         {
2454           release_chain (chain);
2455           VEC_unordered_remove (chain_p, chains, i);
2456         }
2457     }
2458 }
2459
2460 /* Performs predictive commoning for LOOP.  Returns true if LOOP was
2461    unrolled.  */
2462
2463 static bool
2464 tree_predictive_commoning_loop (struct loop *loop)
2465 {
2466   VEC (loop_p, heap) *loop_nest;
2467   VEC (data_reference_p, heap) *datarefs;
2468   VEC (ddr_p, heap) *dependences;
2469   struct component *components;
2470   VEC (chain_p, heap) *chains = NULL;
2471   unsigned unroll_factor;
2472   struct tree_niter_desc desc;
2473   bool unroll = false;
2474   edge exit;
2475   bitmap tmp_vars;
2476
2477   if (dump_file && (dump_flags & TDF_DETAILS))
2478     fprintf (dump_file, "Processing loop %d\n",  loop->num);
2479
2480   /* Find the data references and split them into components according to their
2481      dependence relations.  */
2482   datarefs = VEC_alloc (data_reference_p, heap, 10);
2483   dependences = VEC_alloc (ddr_p, heap, 10);
2484   loop_nest = VEC_alloc (loop_p, heap, 3);
2485   if (! compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs,
2486                                            &dependences))
2487     {
2488       if (dump_file && (dump_flags & TDF_DETAILS))
2489         fprintf (dump_file, "Cannot analyze data dependencies\n");
2490       VEC_free (loop_p, heap, loop_nest);
2491       free_data_refs (datarefs);
2492       free_dependence_relations (dependences);
2493       return false;
2494     }
2495
2496   if (dump_file && (dump_flags & TDF_DETAILS))
2497     dump_data_dependence_relations (dump_file, dependences);
2498
2499   components = split_data_refs_to_components (loop, datarefs, dependences);
2500   VEC_free (loop_p, heap, loop_nest);
2501   free_dependence_relations (dependences);
2502   if (!components)
2503     {
2504       free_data_refs (datarefs);
2505       return false;
2506     }
2507
2508   if (dump_file && (dump_flags & TDF_DETAILS))
2509     {
2510       fprintf (dump_file, "Initial state:\n\n");
2511       dump_components (dump_file, components);
2512     }
2513
2514   /* Find the suitable components and split them into chains.  */
2515   components = filter_suitable_components (loop, components);
2516
2517   tmp_vars = BITMAP_ALLOC (NULL);
2518   looparound_phis = BITMAP_ALLOC (NULL);
2519   determine_roots (loop, components, &chains);
2520   release_components (components);
2521
2522   if (!chains)
2523     {
2524       if (dump_file && (dump_flags & TDF_DETAILS))
2525         fprintf (dump_file,
2526                  "Predictive commoning failed: no suitable chains\n");
2527       goto end;
2528     }
2529   prepare_initializers (loop, chains);
2530
2531   /* Try to combine the chains that are always worked with together.  */
2532   try_combine_chains (&chains);
2533
2534   if (dump_file && (dump_flags & TDF_DETAILS))
2535     {
2536       fprintf (dump_file, "Before commoning:\n\n");
2537       dump_chains (dump_file, chains);
2538     }
2539
2540   /* Determine the unroll factor, and if the loop should be unrolled, ensure
2541      that its number of iterations is divisible by the factor.  */
2542   unroll_factor = determine_unroll_factor (chains);
2543   scev_reset ();
2544   unroll = (unroll_factor > 1
2545             && can_unroll_loop_p (loop, unroll_factor, &desc));
2546   exit = single_dom_exit (loop);
2547
2548   /* Execute the predictive commoning transformations, and possibly unroll the
2549      loop.  */
2550   if (unroll)
2551     {
2552       struct epcc_data dta;
2553
2554       if (dump_file && (dump_flags & TDF_DETAILS))
2555         fprintf (dump_file, "Unrolling %u times.\n", unroll_factor);
2556
2557       dta.chains = chains;
2558       dta.tmp_vars = tmp_vars;
2559
2560       update_ssa (TODO_update_ssa_only_virtuals);
2561
2562       /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2563          execute_pred_commoning_cbck is called may cause phi nodes to be
2564          reallocated, which is a problem since CHAINS may point to these
2565          statements.  To fix this, we store the ssa names defined by the
2566          phi nodes here instead of the phi nodes themselves, and restore
2567          the phi nodes in execute_pred_commoning_cbck.  A bit hacky.  */
2568       replace_phis_by_defined_names (chains);
2569
2570       tree_transform_and_unroll_loop (loop, unroll_factor, exit, &desc,
2571                                       execute_pred_commoning_cbck, &dta);
2572       eliminate_temp_copies (loop, tmp_vars);
2573     }
2574   else
2575     {
2576       if (dump_file && (dump_flags & TDF_DETAILS))
2577         fprintf (dump_file,
2578                  "Executing predictive commoning without unrolling.\n");
2579       execute_pred_commoning (loop, chains, tmp_vars);
2580     }
2581
2582 end: ;
2583   release_chains (chains);
2584   free_data_refs (datarefs);
2585   BITMAP_FREE (tmp_vars);
2586   BITMAP_FREE (looparound_phis);
2587
2588   free_affine_expand_cache (&name_expansions);
2589
2590   return unroll;
2591 }
2592
2593 /* Runs predictive commoning.  */
2594
2595 unsigned
2596 tree_predictive_commoning (void)
2597 {
2598   bool unrolled = false;
2599   struct loop *loop;
2600   loop_iterator li;
2601   unsigned ret = 0;
2602
2603   initialize_original_copy_tables ();
2604   FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
2605     if (optimize_loop_for_speed_p (loop))
2606       {
2607         unrolled |= tree_predictive_commoning_loop (loop);
2608       }
2609
2610   if (unrolled)
2611     {
2612       scev_reset ();
2613       ret = TODO_cleanup_cfg;
2614     }
2615   free_original_copy_tables ();
2616
2617   return ret;
2618 }