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
dump_dref(FILE * file,dref ref)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
dump_chain(FILE * file,chain_p chain)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
dump_chains(FILE * file,VEC (chain_p,heap)* chains)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
dump_component(FILE * file,struct component * comp)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
dump_components(FILE * file,struct component * comps)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
release_chain(chain_p chain)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
release_chains(VEC (chain_p,heap)* chains)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
release_component(struct component * comp)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
release_components(struct component * comps)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
component_of(unsigned fathers[],unsigned a)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
merge_comps(unsigned fathers[],unsigned sizes[],unsigned a,unsigned b)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
suitable_reference_p(struct data_reference * a,enum ref_step_type * ref_step)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
aff_combination_dr_offset(struct data_reference * dr,aff_tree * offset)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
determine_offset(struct data_reference * a,struct data_reference * b,double_int * off)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
last_always_executed_block(struct loop * loop)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 *
split_data_refs_to_components(struct loop * loop,VEC (data_reference_p,heap)* datarefs,VEC (ddr_p,heap)* depends)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
suitable_component_p(struct loop * loop,struct component * comp)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 *
filter_suitable_components(struct loop * loop,struct component * comps)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
order_drefs(const void * a,const void * b)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
get_chain_root(chain_p chain)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
add_ref_to_chain(chain_p chain,dref ref)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
make_invariant_chain(struct component * comp)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
make_rooted_chain(dref ref)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
nontrivial_chain_p(chain_p chain)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
name_for_ref(dref ref)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
valid_initializer_p(struct data_reference * ref,unsigned distance,struct data_reference * root)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
find_looparound_phi(struct loop * loop,dref ref,dref root)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
insert_looparound_copy(chain_p chain,dref ref,gimple phi)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
add_looparound_copies(struct loop * loop,chain_p chain)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
determine_roots_comp(struct loop * loop,struct component * comp,VEC (chain_p,heap)** chains)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
determine_roots(struct loop * loop,struct component * comps,VEC (chain_p,heap)** chains)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
replace_ref_with(gimple stmt,tree new_tree,bool set,bool in_lhs)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
ref_at_iteration(struct loop * loop,tree ref,int iter)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
get_init_expr(chain_p chain,unsigned index)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
mark_virtual_ops_for_renaming(gimple stmt)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
predcom_tmp_var(tree ref,unsigned i,bitmap tmp_vars)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
initialize_root_vars(struct loop * loop,chain_p chain,bitmap tmp_vars)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
initialize_root(struct loop * loop,chain_p chain,bitmap tmp_vars)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
initialize_root_vars_lm(struct loop * loop,dref root,bool written,VEC (tree,heap)** vars,VEC (tree,heap)* inits,bitmap tmp_vars)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
execute_load_motion(struct loop * loop,chain_p chain,bitmap tmp_vars)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
single_nonlooparound_use(tree name)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
remove_stmt(gimple stmt)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
execute_pred_commoning_chain(struct loop * loop,chain_p chain,bitmap tmp_vars)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
determine_unroll_factor(VEC (chain_p,heap)* chains)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
execute_pred_commoning(struct loop * loop,VEC (chain_p,heap)* chains,bitmap tmp_vars)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
replace_phis_by_defined_names(VEC (chain_p,heap)* chains)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
replace_names_by_phis(VEC (chain_p,heap)* chains)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
execute_pred_commoning_cbck(struct loop * loop,void * data)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
base_names_in_chain_on(struct loop * loop,tree name,tree var)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
eliminate_temp_copies(struct loop * loop,bitmap tmp_vars)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
chain_can_be_combined_p(chain_p chain)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
find_use_stmt(tree * name)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
may_reassociate_p(tree type,enum tree_code code)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
find_associative_operation_root(gimple stmt,unsigned * distance)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
find_common_use_stmt(tree * name1,tree * name2)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
combinable_refs_p(dref r1,dref r2,enum tree_code * code,bool * swap,tree * rslt_type)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
remove_name_from_operation(gimple stmt,tree op)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
reassociate_to_the_same_stmt(tree name1,tree name2)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
stmt_combining_refs(dref r1,dref r2)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
combine_chains(chain_p ch1,chain_p ch2)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
try_combine_chains(VEC (chain_p,heap)** chains)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
prepare_initializers_chain(struct loop * loop,chain_p chain)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
prepare_initializers(struct loop * loop,VEC (chain_p,heap)* chains)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
tree_predictive_commoning_loop(struct loop * loop)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
tree_predictive_commoning(void)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 }
2619