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