Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-predcom.c @ 0:a06113de4d67

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