Daily bump.
[official-gcc.git] / gcc / tree-ssa-loop-prefetch.c
blob705848216be93753ed3b98341059318136baf650
1 /* Array prefetching.
2 Copyright (C) 2005, 2007 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
9 later version.
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.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "tree.h"
25 #include "rtl.h"
26 #include "tm_p.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
29 #include "output.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
33 #include "timevar.h"
34 #include "cfgloop.h"
35 #include "varray.h"
36 #include "expr.h"
37 #include "tree-pass.h"
38 #include "ggc.h"
39 #include "insn-config.h"
40 #include "recog.h"
41 #include "hashtab.h"
42 #include "tree-chrec.h"
43 #include "tree-scalar-evolution.h"
44 #include "toplev.h"
45 #include "params.h"
46 #include "langhooks.h"
47 #include "tree-inline.h"
48 #include "tree-data-ref.h"
49 #include "optabs.h"
51 /* This pass inserts prefetch instructions to optimize cache usage during
52 accesses to arrays in loops. It processes loops sequentially and:
54 1) Gathers all memory references in the single loop.
55 2) For each of the references it decides when it is profitable to prefetch
56 it. To do it, we evaluate the reuse among the accesses, and determines
57 two values: PREFETCH_BEFORE (meaning that it only makes sense to do
58 prefetching in the first PREFETCH_BEFORE iterations of the loop) and
59 PREFETCH_MOD (meaning that it only makes sense to prefetch in the
60 iterations of the loop that are zero modulo PREFETCH_MOD). For example
61 (assuming cache line size is 64 bytes, char has size 1 byte and there
62 is no hardware sequential prefetch):
64 char *a;
65 for (i = 0; i < max; i++)
67 a[255] = ...; (0)
68 a[i] = ...; (1)
69 a[i + 64] = ...; (2)
70 a[16*i] = ...; (3)
71 a[187*i] = ...; (4)
72 a[187*i + 50] = ...; (5)
75 (0) obviously has PREFETCH_BEFORE 1
76 (1) has PREFETCH_BEFORE 64, since (2) accesses the same memory
77 location 64 iterations before it, and PREFETCH_MOD 64 (since
78 it hits the same cache line otherwise).
79 (2) has PREFETCH_MOD 64
80 (3) has PREFETCH_MOD 4
81 (4) has PREFETCH_MOD 1. We do not set PREFETCH_BEFORE here, since
82 the cache line accessed by (4) is the same with probability only
83 7/32.
84 (5) has PREFETCH_MOD 1 as well.
86 Additionally, we use data dependence analysis to determine for each
87 reference the distance till the first reuse; this information is used
88 to determine the temporality of the issued prefetch instruction.
90 3) We determine how much ahead we need to prefetch. The number of
91 iterations needed is time to fetch / time spent in one iteration of
92 the loop. The problem is that we do not know either of these values,
93 so we just make a heuristic guess based on a magic (possibly)
94 target-specific constant and size of the loop.
96 4) Determine which of the references we prefetch. We take into account
97 that there is a maximum number of simultaneous prefetches (provided
98 by machine description). We prefetch as many prefetches as possible
99 while still within this bound (starting with those with lowest
100 prefetch_mod, since they are responsible for most of the cache
101 misses).
103 5) We unroll and peel loops so that we are able to satisfy PREFETCH_MOD
104 and PREFETCH_BEFORE requirements (within some bounds), and to avoid
105 prefetching nonaccessed memory.
106 TODO -- actually implement peeling.
108 6) We actually emit the prefetch instructions. ??? Perhaps emit the
109 prefetch instructions with guards in cases where 5) was not sufficient
110 to satisfy the constraints?
112 Some other TODO:
113 -- write and use more general reuse analysis (that could be also used
114 in other cache aimed loop optimizations)
115 -- make it behave sanely together with the prefetches given by user
116 (now we just ignore them; at the very least we should avoid
117 optimizing loops in that user put his own prefetches)
118 -- we assume cache line size alignment of arrays; this could be
119 improved. */
121 /* Magic constants follow. These should be replaced by machine specific
122 numbers. */
124 /* True if write can be prefetched by a read prefetch. */
126 #ifndef WRITE_CAN_USE_READ_PREFETCH
127 #define WRITE_CAN_USE_READ_PREFETCH 1
128 #endif
130 /* True if read can be prefetched by a write prefetch. */
132 #ifndef READ_CAN_USE_WRITE_PREFETCH
133 #define READ_CAN_USE_WRITE_PREFETCH 0
134 #endif
136 /* The size of the block loaded by a single prefetch. Usually, this is
137 the same as cache line size (at the moment, we only consider one level
138 of cache hierarchy). */
140 #ifndef PREFETCH_BLOCK
141 #define PREFETCH_BLOCK L1_CACHE_LINE_SIZE
142 #endif
144 /* Do we have a forward hardware sequential prefetching? */
146 #ifndef HAVE_FORWARD_PREFETCH
147 #define HAVE_FORWARD_PREFETCH 0
148 #endif
150 /* Do we have a backward hardware sequential prefetching? */
152 #ifndef HAVE_BACKWARD_PREFETCH
153 #define HAVE_BACKWARD_PREFETCH 0
154 #endif
156 /* In some cases we are only able to determine that there is a certain
157 probability that the two accesses hit the same cache line. In this
158 case, we issue the prefetches for both of them if this probability
159 is less then (1000 - ACCEPTABLE_MISS_RATE) promile. */
161 #ifndef ACCEPTABLE_MISS_RATE
162 #define ACCEPTABLE_MISS_RATE 50
163 #endif
165 #ifndef HAVE_prefetch
166 #define HAVE_prefetch 0
167 #endif
169 #define L1_CACHE_SIZE_BYTES ((unsigned) (L1_CACHE_SIZE * 1024))
170 #define L2_CACHE_SIZE_BYTES ((unsigned) (L2_CACHE_SIZE * 1024))
172 /* We consider a memory access nontemporal if it is not reused sooner than
173 after L2_CACHE_SIZE_BYTES of memory are accessed. However, we ignore
174 accesses closer than L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
175 so that we use nontemporal prefetches e.g. if single memory location
176 is accessed several times in a single iteration of the loop. */
177 #define NONTEMPORAL_FRACTION 16
179 /* In case we have to emit a memory fence instruction after the loop that
180 uses nontemporal stores, this defines the builtin to use. */
182 #ifndef FENCE_FOLLOWING_MOVNT
183 #define FENCE_FOLLOWING_MOVNT NULL_TREE
184 #endif
186 /* The group of references between that reuse may occur. */
188 struct mem_ref_group
190 tree base; /* Base of the reference. */
191 HOST_WIDE_INT step; /* Step of the reference. */
192 struct mem_ref *refs; /* References in the group. */
193 struct mem_ref_group *next; /* Next group of references. */
196 /* Assigned to PREFETCH_BEFORE when all iterations are to be prefetched. */
198 #define PREFETCH_ALL (~(unsigned HOST_WIDE_INT) 0)
200 /* The memory reference. */
202 struct mem_ref
204 tree stmt; /* Statement in that the reference appears. */
205 tree mem; /* The reference. */
206 HOST_WIDE_INT delta; /* Constant offset of the reference. */
207 struct mem_ref_group *group; /* The group of references it belongs to. */
208 unsigned HOST_WIDE_INT prefetch_mod;
209 /* Prefetch only each PREFETCH_MOD-th
210 iteration. */
211 unsigned HOST_WIDE_INT prefetch_before;
212 /* Prefetch only first PREFETCH_BEFORE
213 iterations. */
214 unsigned reuse_distance; /* The amount of data accessed before the first
215 reuse of this value. */
216 struct mem_ref *next; /* The next reference in the group. */
217 unsigned write_p : 1; /* Is it a write? */
218 unsigned independent_p : 1; /* True if the reference is independent on
219 all other references inside the loop. */
220 unsigned issue_prefetch_p : 1; /* Should we really issue the prefetch? */
221 unsigned storent_p : 1; /* True if we changed the store to a
222 nontemporal one. */
225 /* Dumps information about reference REF to FILE. */
227 static void
228 dump_mem_ref (FILE *file, struct mem_ref *ref)
230 fprintf (file, "Reference %p:\n", (void *) ref);
232 fprintf (file, " group %p (base ", (void *) ref->group);
233 print_generic_expr (file, ref->group->base, TDF_SLIM);
234 fprintf (file, ", step ");
235 fprintf (file, HOST_WIDE_INT_PRINT_DEC, ref->group->step);
236 fprintf (file, ")\n");
238 fprintf (file, " delta ");
239 fprintf (file, HOST_WIDE_INT_PRINT_DEC, ref->delta);
240 fprintf (file, "\n");
242 fprintf (file, " %s\n", ref->write_p ? "write" : "read");
244 fprintf (file, "\n");
247 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
248 exist. */
250 static struct mem_ref_group *
251 find_or_create_group (struct mem_ref_group **groups, tree base,
252 HOST_WIDE_INT step)
254 struct mem_ref_group *group;
256 for (; *groups; groups = &(*groups)->next)
258 if ((*groups)->step == step
259 && operand_equal_p ((*groups)->base, base, 0))
260 return *groups;
262 /* Keep the list of groups sorted by decreasing step. */
263 if ((*groups)->step < step)
264 break;
267 group = XNEW (struct mem_ref_group);
268 group->base = base;
269 group->step = step;
270 group->refs = NULL;
271 group->next = *groups;
272 *groups = group;
274 return group;
277 /* Records a memory reference MEM in GROUP with offset DELTA and write status
278 WRITE_P. The reference occurs in statement STMT. */
280 static void
281 record_ref (struct mem_ref_group *group, tree stmt, tree mem,
282 HOST_WIDE_INT delta, bool write_p)
284 struct mem_ref **aref;
286 /* Do not record the same address twice. */
287 for (aref = &group->refs; *aref; aref = &(*aref)->next)
289 /* It does not have to be possible for write reference to reuse the read
290 prefetch, or vice versa. */
291 if (!WRITE_CAN_USE_READ_PREFETCH
292 && write_p
293 && !(*aref)->write_p)
294 continue;
295 if (!READ_CAN_USE_WRITE_PREFETCH
296 && !write_p
297 && (*aref)->write_p)
298 continue;
300 if ((*aref)->delta == delta)
301 return;
304 (*aref) = XNEW (struct mem_ref);
305 (*aref)->stmt = stmt;
306 (*aref)->mem = mem;
307 (*aref)->delta = delta;
308 (*aref)->write_p = write_p;
309 (*aref)->prefetch_before = PREFETCH_ALL;
310 (*aref)->prefetch_mod = 1;
311 (*aref)->reuse_distance = 0;
312 (*aref)->issue_prefetch_p = false;
313 (*aref)->group = group;
314 (*aref)->next = NULL;
315 (*aref)->independent_p = false;
316 (*aref)->storent_p = false;
318 if (dump_file && (dump_flags & TDF_DETAILS))
319 dump_mem_ref (dump_file, *aref);
322 /* Release memory references in GROUPS. */
324 static void
325 release_mem_refs (struct mem_ref_group *groups)
327 struct mem_ref_group *next_g;
328 struct mem_ref *ref, *next_r;
330 for (; groups; groups = next_g)
332 next_g = groups->next;
333 for (ref = groups->refs; ref; ref = next_r)
335 next_r = ref->next;
336 free (ref);
338 free (groups);
342 /* A structure used to pass arguments to idx_analyze_ref. */
344 struct ar_data
346 struct loop *loop; /* Loop of the reference. */
347 tree stmt; /* Statement of the reference. */
348 HOST_WIDE_INT *step; /* Step of the memory reference. */
349 HOST_WIDE_INT *delta; /* Offset of the memory reference. */
352 /* Analyzes a single INDEX of a memory reference to obtain information
353 described at analyze_ref. Callback for for_each_index. */
355 static bool
356 idx_analyze_ref (tree base, tree *index, void *data)
358 struct ar_data *ar_data = (struct ar_data *) data;
359 tree ibase, step, stepsize;
360 HOST_WIDE_INT istep, idelta = 0, imult = 1;
361 affine_iv iv;
363 if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
364 || TREE_CODE (base) == ALIGN_INDIRECT_REF)
365 return false;
367 if (!simple_iv (ar_data->loop, ar_data->stmt, *index, &iv, false))
368 return false;
369 ibase = iv.base;
370 step = iv.step;
372 if (!cst_and_fits_in_hwi (step))
373 return false;
374 istep = int_cst_value (step);
376 if (TREE_CODE (ibase) == POINTER_PLUS_EXPR
377 && cst_and_fits_in_hwi (TREE_OPERAND (ibase, 1)))
379 idelta = int_cst_value (TREE_OPERAND (ibase, 1));
380 ibase = TREE_OPERAND (ibase, 0);
382 if (cst_and_fits_in_hwi (ibase))
384 idelta += int_cst_value (ibase);
385 ibase = build_int_cst (TREE_TYPE (ibase), 0);
388 if (TREE_CODE (base) == ARRAY_REF)
390 stepsize = array_ref_element_size (base);
391 if (!cst_and_fits_in_hwi (stepsize))
392 return false;
393 imult = int_cst_value (stepsize);
395 istep *= imult;
396 idelta *= imult;
399 *ar_data->step += istep;
400 *ar_data->delta += idelta;
401 *index = ibase;
403 return true;
406 /* Tries to express REF_P in shape &BASE + STEP * iter + DELTA, where DELTA and
407 STEP are integer constants and iter is number of iterations of LOOP. The
408 reference occurs in statement STMT. Strips nonaddressable component
409 references from REF_P. */
411 static bool
412 analyze_ref (struct loop *loop, tree *ref_p, tree *base,
413 HOST_WIDE_INT *step, HOST_WIDE_INT *delta,
414 tree stmt)
416 struct ar_data ar_data;
417 tree off;
418 HOST_WIDE_INT bit_offset;
419 tree ref = *ref_p;
421 *step = 0;
422 *delta = 0;
424 /* First strip off the component references. Ignore bitfields. */
425 if (TREE_CODE (ref) == COMPONENT_REF
426 && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref, 1)))
427 ref = TREE_OPERAND (ref, 0);
429 *ref_p = ref;
431 for (; TREE_CODE (ref) == COMPONENT_REF; ref = TREE_OPERAND (ref, 0))
433 off = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1));
434 bit_offset = TREE_INT_CST_LOW (off);
435 gcc_assert (bit_offset % BITS_PER_UNIT == 0);
437 *delta += bit_offset / BITS_PER_UNIT;
440 *base = unshare_expr (ref);
441 ar_data.loop = loop;
442 ar_data.stmt = stmt;
443 ar_data.step = step;
444 ar_data.delta = delta;
445 return for_each_index (base, idx_analyze_ref, &ar_data);
448 /* Record a memory reference REF to the list REFS. The reference occurs in
449 LOOP in statement STMT and it is write if WRITE_P. Returns true if the
450 reference was recorded, false otherwise. */
452 static bool
453 gather_memory_references_ref (struct loop *loop, struct mem_ref_group **refs,
454 tree ref, bool write_p, tree stmt)
456 tree base;
457 HOST_WIDE_INT step, delta;
458 struct mem_ref_group *agrp;
460 if (!analyze_ref (loop, &ref, &base, &step, &delta, stmt))
461 return false;
463 /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
464 are integer constants. */
465 agrp = find_or_create_group (refs, base, step);
466 record_ref (agrp, stmt, ref, delta, write_p);
468 return true;
471 /* Record the suitable memory references in LOOP. NO_OTHER_REFS is set to
472 true if there are no other memory references inside the loop. */
474 static struct mem_ref_group *
475 gather_memory_references (struct loop *loop, bool *no_other_refs)
477 basic_block *body = get_loop_body_in_dom_order (loop);
478 basic_block bb;
479 unsigned i;
480 block_stmt_iterator bsi;
481 tree stmt, lhs, rhs, call;
482 struct mem_ref_group *refs = NULL;
484 *no_other_refs = true;
486 /* Scan the loop body in order, so that the former references precede the
487 later ones. */
488 for (i = 0; i < loop->num_nodes; i++)
490 bb = body[i];
491 if (bb->loop_father != loop)
492 continue;
494 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
496 stmt = bsi_stmt (bsi);
497 call = get_call_expr_in (stmt);
498 if (call && !(call_expr_flags (call) & ECF_CONST))
499 *no_other_refs = false;
501 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
503 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
504 *no_other_refs = false;
505 continue;
508 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
509 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
511 if (REFERENCE_CLASS_P (rhs))
512 *no_other_refs &= gather_memory_references_ref (loop, &refs,
513 rhs, false, stmt);
514 if (REFERENCE_CLASS_P (lhs))
515 *no_other_refs &= gather_memory_references_ref (loop, &refs,
516 lhs, true, stmt);
519 free (body);
521 return refs;
524 /* Prune the prefetch candidate REF using the self-reuse. */
526 static void
527 prune_ref_by_self_reuse (struct mem_ref *ref)
529 HOST_WIDE_INT step = ref->group->step;
530 bool backward = step < 0;
532 if (step == 0)
534 /* Prefetch references to invariant address just once. */
535 ref->prefetch_before = 1;
536 return;
539 if (backward)
540 step = -step;
542 if (step > PREFETCH_BLOCK)
543 return;
545 if ((backward && HAVE_BACKWARD_PREFETCH)
546 || (!backward && HAVE_FORWARD_PREFETCH))
548 ref->prefetch_before = 1;
549 return;
552 ref->prefetch_mod = PREFETCH_BLOCK / step;
555 /* Divides X by BY, rounding down. */
557 static HOST_WIDE_INT
558 ddown (HOST_WIDE_INT x, unsigned HOST_WIDE_INT by)
560 gcc_assert (by > 0);
562 if (x >= 0)
563 return x / by;
564 else
565 return (x + by - 1) / by;
568 /* Prune the prefetch candidate REF using the reuse with BY.
569 If BY_IS_BEFORE is true, BY is before REF in the loop. */
571 static void
572 prune_ref_by_group_reuse (struct mem_ref *ref, struct mem_ref *by,
573 bool by_is_before)
575 HOST_WIDE_INT step = ref->group->step;
576 bool backward = step < 0;
577 HOST_WIDE_INT delta_r = ref->delta, delta_b = by->delta;
578 HOST_WIDE_INT delta = delta_b - delta_r;
579 HOST_WIDE_INT hit_from;
580 unsigned HOST_WIDE_INT prefetch_before, prefetch_block;
582 if (delta == 0)
584 /* If the references has the same address, only prefetch the
585 former. */
586 if (by_is_before)
587 ref->prefetch_before = 0;
589 return;
592 if (!step)
594 /* If the reference addresses are invariant and fall into the
595 same cache line, prefetch just the first one. */
596 if (!by_is_before)
597 return;
599 if (ddown (ref->delta, PREFETCH_BLOCK)
600 != ddown (by->delta, PREFETCH_BLOCK))
601 return;
603 ref->prefetch_before = 0;
604 return;
607 /* Only prune the reference that is behind in the array. */
608 if (backward)
610 if (delta > 0)
611 return;
613 /* Transform the data so that we may assume that the accesses
614 are forward. */
615 delta = - delta;
616 step = -step;
617 delta_r = PREFETCH_BLOCK - 1 - delta_r;
618 delta_b = PREFETCH_BLOCK - 1 - delta_b;
620 else
622 if (delta < 0)
623 return;
626 /* Check whether the two references are likely to hit the same cache
627 line, and how distant the iterations in that it occurs are from
628 each other. */
630 if (step <= PREFETCH_BLOCK)
632 /* The accesses are sure to meet. Let us check when. */
633 hit_from = ddown (delta_b, PREFETCH_BLOCK) * PREFETCH_BLOCK;
634 prefetch_before = (hit_from - delta_r + step - 1) / step;
636 if (prefetch_before < ref->prefetch_before)
637 ref->prefetch_before = prefetch_before;
639 return;
642 /* A more complicated case. First let us ensure that size of cache line
643 and step are coprime (here we assume that PREFETCH_BLOCK is a power
644 of two. */
645 prefetch_block = PREFETCH_BLOCK;
646 while ((step & 1) == 0
647 && prefetch_block > 1)
649 step >>= 1;
650 prefetch_block >>= 1;
651 delta >>= 1;
654 /* Now step > prefetch_block, and step and prefetch_block are coprime.
655 Determine the probability that the accesses hit the same cache line. */
657 prefetch_before = delta / step;
658 delta %= step;
659 if ((unsigned HOST_WIDE_INT) delta
660 <= (prefetch_block * ACCEPTABLE_MISS_RATE / 1000))
662 if (prefetch_before < ref->prefetch_before)
663 ref->prefetch_before = prefetch_before;
665 return;
668 /* Try also the following iteration. */
669 prefetch_before++;
670 delta = step - delta;
671 if ((unsigned HOST_WIDE_INT) delta
672 <= (prefetch_block * ACCEPTABLE_MISS_RATE / 1000))
674 if (prefetch_before < ref->prefetch_before)
675 ref->prefetch_before = prefetch_before;
677 return;
680 /* The ref probably does not reuse by. */
681 return;
684 /* Prune the prefetch candidate REF using the reuses with other references
685 in REFS. */
687 static void
688 prune_ref_by_reuse (struct mem_ref *ref, struct mem_ref *refs)
690 struct mem_ref *prune_by;
691 bool before = true;
693 prune_ref_by_self_reuse (ref);
695 for (prune_by = refs; prune_by; prune_by = prune_by->next)
697 if (prune_by == ref)
699 before = false;
700 continue;
703 if (!WRITE_CAN_USE_READ_PREFETCH
704 && ref->write_p
705 && !prune_by->write_p)
706 continue;
707 if (!READ_CAN_USE_WRITE_PREFETCH
708 && !ref->write_p
709 && prune_by->write_p)
710 continue;
712 prune_ref_by_group_reuse (ref, prune_by, before);
716 /* Prune the prefetch candidates in GROUP using the reuse analysis. */
718 static void
719 prune_group_by_reuse (struct mem_ref_group *group)
721 struct mem_ref *ref_pruned;
723 for (ref_pruned = group->refs; ref_pruned; ref_pruned = ref_pruned->next)
725 prune_ref_by_reuse (ref_pruned, group->refs);
727 if (dump_file && (dump_flags & TDF_DETAILS))
729 fprintf (dump_file, "Reference %p:", (void *) ref_pruned);
731 if (ref_pruned->prefetch_before == PREFETCH_ALL
732 && ref_pruned->prefetch_mod == 1)
733 fprintf (dump_file, " no restrictions");
734 else if (ref_pruned->prefetch_before == 0)
735 fprintf (dump_file, " do not prefetch");
736 else if (ref_pruned->prefetch_before <= ref_pruned->prefetch_mod)
737 fprintf (dump_file, " prefetch once");
738 else
740 if (ref_pruned->prefetch_before != PREFETCH_ALL)
742 fprintf (dump_file, " prefetch before ");
743 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC,
744 ref_pruned->prefetch_before);
746 if (ref_pruned->prefetch_mod != 1)
748 fprintf (dump_file, " prefetch mod ");
749 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC,
750 ref_pruned->prefetch_mod);
753 fprintf (dump_file, "\n");
758 /* Prune the list of prefetch candidates GROUPS using the reuse analysis. */
760 static void
761 prune_by_reuse (struct mem_ref_group *groups)
763 for (; groups; groups = groups->next)
764 prune_group_by_reuse (groups);
767 /* Returns true if we should issue prefetch for REF. */
769 static bool
770 should_issue_prefetch_p (struct mem_ref *ref)
772 /* For now do not issue prefetches for only first few of the
773 iterations. */
774 if (ref->prefetch_before != PREFETCH_ALL)
775 return false;
777 /* Do not prefetch nontemporal stores. */
778 if (ref->storent_p)
779 return false;
781 return true;
784 /* Decide which of the prefetch candidates in GROUPS to prefetch.
785 AHEAD is the number of iterations to prefetch ahead (which corresponds
786 to the number of simultaneous instances of one prefetch running at a
787 time). UNROLL_FACTOR is the factor by that the loop is going to be
788 unrolled. Returns true if there is anything to prefetch. */
790 static bool
791 schedule_prefetches (struct mem_ref_group *groups, unsigned unroll_factor,
792 unsigned ahead)
794 unsigned remaining_prefetch_slots, n_prefetches, prefetch_slots;
795 unsigned slots_per_prefetch;
796 struct mem_ref *ref;
797 bool any = false;
799 /* At most SIMULTANEOUS_PREFETCHES should be running at the same time. */
800 remaining_prefetch_slots = SIMULTANEOUS_PREFETCHES;
802 /* The prefetch will run for AHEAD iterations of the original loop, i.e.,
803 AHEAD / UNROLL_FACTOR iterations of the unrolled loop. In each iteration,
804 it will need a prefetch slot. */
805 slots_per_prefetch = (ahead + unroll_factor / 2) / unroll_factor;
806 if (dump_file && (dump_flags & TDF_DETAILS))
807 fprintf (dump_file, "Each prefetch instruction takes %u prefetch slots.\n",
808 slots_per_prefetch);
810 /* For now we just take memory references one by one and issue
811 prefetches for as many as possible. The groups are sorted
812 starting with the largest step, since the references with
813 large step are more likely to cause many cache misses. */
815 for (; groups; groups = groups->next)
816 for (ref = groups->refs; ref; ref = ref->next)
818 if (!should_issue_prefetch_p (ref))
819 continue;
821 /* If we need to prefetch the reference each PREFETCH_MOD iterations,
822 and we unroll the loop UNROLL_FACTOR times, we need to insert
823 ceil (UNROLL_FACTOR / PREFETCH_MOD) instructions in each
824 iteration. */
825 n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
826 / ref->prefetch_mod);
827 prefetch_slots = n_prefetches * slots_per_prefetch;
829 /* If more than half of the prefetches would be lost anyway, do not
830 issue the prefetch. */
831 if (2 * remaining_prefetch_slots < prefetch_slots)
832 continue;
834 ref->issue_prefetch_p = true;
836 if (remaining_prefetch_slots <= prefetch_slots)
837 return true;
838 remaining_prefetch_slots -= prefetch_slots;
839 any = true;
842 return any;
845 /* Determine whether there is any reference suitable for prefetching
846 in GROUPS. */
848 static bool
849 anything_to_prefetch_p (struct mem_ref_group *groups)
851 struct mem_ref *ref;
853 for (; groups; groups = groups->next)
854 for (ref = groups->refs; ref; ref = ref->next)
855 if (should_issue_prefetch_p (ref))
856 return true;
858 return false;
861 /* Issue prefetches for the reference REF into loop as decided before.
862 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR
863 is the factor by which LOOP was unrolled. */
865 static void
866 issue_prefetch_ref (struct mem_ref *ref, unsigned unroll_factor, unsigned ahead)
868 HOST_WIDE_INT delta;
869 tree addr, addr_base, prefetch, write_p, local;
870 block_stmt_iterator bsi;
871 unsigned n_prefetches, ap;
872 bool nontemporal = ref->reuse_distance >= L2_CACHE_SIZE_BYTES;
874 if (dump_file && (dump_flags & TDF_DETAILS))
875 fprintf (dump_file, "Issued%s prefetch for %p.\n",
876 nontemporal ? " nontemporal" : "",
877 (void *) ref);
879 bsi = bsi_for_stmt (ref->stmt);
881 n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
882 / ref->prefetch_mod);
883 addr_base = build_fold_addr_expr_with_type (ref->mem, ptr_type_node);
884 addr_base = force_gimple_operand_bsi (&bsi, unshare_expr (addr_base),
885 true, NULL, true, BSI_SAME_STMT);
886 write_p = ref->write_p ? integer_one_node : integer_zero_node;
887 local = build_int_cst (integer_type_node, nontemporal ? 0 : 3);
889 for (ap = 0; ap < n_prefetches; ap++)
891 /* Determine the address to prefetch. */
892 delta = (ahead + ap * ref->prefetch_mod) * ref->group->step;
893 addr = fold_build2 (POINTER_PLUS_EXPR, ptr_type_node,
894 addr_base, size_int (delta));
895 addr = force_gimple_operand_bsi (&bsi, unshare_expr (addr), true, NULL,
896 true, BSI_SAME_STMT);
898 /* Create the prefetch instruction. */
899 prefetch = build_call_expr (built_in_decls[BUILT_IN_PREFETCH],
900 3, addr, write_p, local);
901 bsi_insert_before (&bsi, prefetch, BSI_SAME_STMT);
905 /* Issue prefetches for the references in GROUPS into loop as decided before.
906 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR is the
907 factor by that LOOP was unrolled. */
909 static void
910 issue_prefetches (struct mem_ref_group *groups,
911 unsigned unroll_factor, unsigned ahead)
913 struct mem_ref *ref;
915 for (; groups; groups = groups->next)
916 for (ref = groups->refs; ref; ref = ref->next)
917 if (ref->issue_prefetch_p)
918 issue_prefetch_ref (ref, unroll_factor, ahead);
921 /* Returns true if REF is a memory write for that a nontemporal store insn
922 can be used. */
924 static bool
925 nontemporal_store_p (struct mem_ref *ref)
927 enum machine_mode mode;
928 enum insn_code code;
930 /* REF must be a write that is not reused. We require it to be independent
931 on all other memory references in the loop, as the nontemporal stores may
932 be reordered with respect to other memory references. */
933 if (!ref->write_p
934 || !ref->independent_p
935 || ref->reuse_distance < L2_CACHE_SIZE_BYTES)
936 return false;
938 /* Check that we have the storent instruction for the mode. */
939 mode = TYPE_MODE (TREE_TYPE (ref->mem));
940 if (mode == BLKmode)
941 return false;
943 code = optab_handler (storent_optab, mode)->insn_code;
944 return code != CODE_FOR_nothing;
947 /* If REF is a nontemporal store, we mark the corresponding modify statement
948 and return true. Otherwise, we return false. */
950 static bool
951 mark_nontemporal_store (struct mem_ref *ref)
953 if (!nontemporal_store_p (ref))
954 return false;
956 if (dump_file && (dump_flags & TDF_DETAILS))
957 fprintf (dump_file, "Marked reference %p as a nontemporal store.\n",
958 (void *) ref);
960 MOVE_NONTEMPORAL (ref->stmt) = true;
961 ref->storent_p = true;
963 return true;
966 /* Issue a memory fence instruction after LOOP. */
968 static void
969 emit_mfence_after_loop (struct loop *loop)
971 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
972 edge exit;
973 tree call;
974 block_stmt_iterator bsi;
975 unsigned i;
977 for (i = 0; VEC_iterate (edge, exits, i, exit); i++)
979 call = build_function_call_expr (FENCE_FOLLOWING_MOVNT, NULL_TREE);
981 if (!single_pred_p (exit->dest)
982 /* If possible, we prefer not to insert the fence on other paths
983 in cfg. */
984 && !(exit->flags & EDGE_ABNORMAL))
985 split_loop_exit_edge (exit);
986 bsi = bsi_after_labels (exit->dest);
988 bsi_insert_before (&bsi, call, BSI_NEW_STMT);
989 mark_virtual_ops_for_renaming (call);
992 VEC_free (edge, heap, exits);
993 update_ssa (TODO_update_ssa_only_virtuals);
996 /* Returns true if we can use storent in loop, false otherwise. */
998 static bool
999 may_use_storent_in_loop_p (struct loop *loop)
1001 bool ret = true;
1003 if (loop->inner != NULL)
1004 return false;
1006 /* If we must issue a mfence insn after using storent, check that there
1007 is a suitable place for it at each of the loop exits. */
1008 if (FENCE_FOLLOWING_MOVNT != NULL_TREE)
1010 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1011 unsigned i;
1012 edge exit;
1014 for (i = 0; VEC_iterate (edge, exits, i, exit); i++)
1015 if ((exit->flags & EDGE_ABNORMAL)
1016 && exit->dest == EXIT_BLOCK_PTR)
1017 ret = false;
1019 VEC_free (edge, heap, exits);
1022 return ret;
1025 /* Marks nontemporal stores in LOOP. GROUPS contains the description of memory
1026 references in the loop. */
1028 static void
1029 mark_nontemporal_stores (struct loop *loop, struct mem_ref_group *groups)
1031 struct mem_ref *ref;
1032 bool any = false;
1034 if (!may_use_storent_in_loop_p (loop))
1035 return;
1037 for (; groups; groups = groups->next)
1038 for (ref = groups->refs; ref; ref = ref->next)
1039 any |= mark_nontemporal_store (ref);
1041 if (any && FENCE_FOLLOWING_MOVNT != NULL_TREE)
1042 emit_mfence_after_loop (loop);
1045 /* Determines whether we can profitably unroll LOOP FACTOR times, and if
1046 this is the case, fill in DESC by the description of number of
1047 iterations. */
1049 static bool
1050 should_unroll_loop_p (struct loop *loop, struct tree_niter_desc *desc,
1051 unsigned factor)
1053 if (!can_unroll_loop_p (loop, factor, desc))
1054 return false;
1056 /* We only consider loops without control flow for unrolling. This is not
1057 a hard restriction -- tree_unroll_loop works with arbitrary loops
1058 as well; but the unrolling/prefetching is usually more profitable for
1059 loops consisting of a single basic block, and we want to limit the
1060 code growth. */
1061 if (loop->num_nodes > 2)
1062 return false;
1064 return true;
1067 /* Determine the coefficient by that unroll LOOP, from the information
1068 contained in the list of memory references REFS. Description of
1069 umber of iterations of LOOP is stored to DESC. NINSNS is the number of
1070 insns of the LOOP. EST_NITER is the estimated number of iterations of
1071 the loop, or -1 if no estimate is available. */
1073 static unsigned
1074 determine_unroll_factor (struct loop *loop, struct mem_ref_group *refs,
1075 unsigned ninsns, struct tree_niter_desc *desc,
1076 HOST_WIDE_INT est_niter)
1078 unsigned upper_bound;
1079 unsigned nfactor, factor, mod_constraint;
1080 struct mem_ref_group *agp;
1081 struct mem_ref *ref;
1083 /* First check whether the loop is not too large to unroll. We ignore
1084 PARAM_MAX_UNROLL_TIMES, because for small loops, it prevented us
1085 from unrolling them enough to make exactly one cache line covered by each
1086 iteration. Also, the goal of PARAM_MAX_UNROLL_TIMES is to prevent
1087 us from unrolling the loops too many times in cases where we only expect
1088 gains from better scheduling and decreasing loop overhead, which is not
1089 the case here. */
1090 upper_bound = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / ninsns;
1092 /* If we unrolled the loop more times than it iterates, the unrolled version
1093 of the loop would be never entered. */
1094 if (est_niter >= 0 && est_niter < (HOST_WIDE_INT) upper_bound)
1095 upper_bound = est_niter;
1097 if (upper_bound <= 1)
1098 return 1;
1100 /* Choose the factor so that we may prefetch each cache just once,
1101 but bound the unrolling by UPPER_BOUND. */
1102 factor = 1;
1103 for (agp = refs; agp; agp = agp->next)
1104 for (ref = agp->refs; ref; ref = ref->next)
1105 if (should_issue_prefetch_p (ref))
1107 mod_constraint = ref->prefetch_mod;
1108 nfactor = least_common_multiple (mod_constraint, factor);
1109 if (nfactor <= upper_bound)
1110 factor = nfactor;
1113 if (!should_unroll_loop_p (loop, desc, factor))
1114 return 1;
1116 return factor;
1119 /* Returns the total volume of the memory references REFS, taking into account
1120 reuses in the innermost loop and cache line size. TODO -- we should also
1121 take into account reuses across the iterations of the loops in the loop
1122 nest. */
1124 static unsigned
1125 volume_of_references (struct mem_ref_group *refs)
1127 unsigned volume = 0;
1128 struct mem_ref_group *gr;
1129 struct mem_ref *ref;
1131 for (gr = refs; gr; gr = gr->next)
1132 for (ref = gr->refs; ref; ref = ref->next)
1134 /* Almost always reuses another value? */
1135 if (ref->prefetch_before != PREFETCH_ALL)
1136 continue;
1138 /* If several iterations access the same cache line, use the size of
1139 the line divided by this number. Otherwise, a cache line is
1140 accessed in each iteration. TODO -- in the latter case, we should
1141 take the size of the reference into account, rounding it up on cache
1142 line size multiple. */
1143 volume += L1_CACHE_LINE_SIZE / ref->prefetch_mod;
1145 return volume;
1148 /* Returns the volume of memory references accessed across VEC iterations of
1149 loops, whose sizes are described in the LOOP_SIZES array. N is the number
1150 of the loops in the nest (length of VEC and LOOP_SIZES vectors). */
1152 static unsigned
1153 volume_of_dist_vector (lambda_vector vec, unsigned *loop_sizes, unsigned n)
1155 unsigned i;
1157 for (i = 0; i < n; i++)
1158 if (vec[i] != 0)
1159 break;
1161 if (i == n)
1162 return 0;
1164 gcc_assert (vec[i] > 0);
1166 /* We ignore the parts of the distance vector in subloops, since usually
1167 the numbers of iterations are much smaller. */
1168 return loop_sizes[i] * vec[i];
1171 /* Add the steps of ACCESS_FN multiplied by STRIDE to the array STRIDE
1172 at the position corresponding to the loop of the step. N is the depth
1173 of the considered loop nest, and, LOOP is its innermost loop. */
1175 static void
1176 add_subscript_strides (tree access_fn, unsigned stride,
1177 HOST_WIDE_INT *strides, unsigned n, struct loop *loop)
1179 struct loop *aloop;
1180 tree step;
1181 HOST_WIDE_INT astep;
1182 unsigned min_depth = loop_depth (loop) - n;
1184 while (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
1186 aloop = get_chrec_loop (access_fn);
1187 step = CHREC_RIGHT (access_fn);
1188 access_fn = CHREC_LEFT (access_fn);
1190 if ((unsigned) loop_depth (aloop) <= min_depth)
1191 continue;
1193 if (host_integerp (step, 0))
1194 astep = tree_low_cst (step, 0);
1195 else
1196 astep = L1_CACHE_LINE_SIZE;
1198 strides[n - 1 - loop_depth (loop) + loop_depth (aloop)] += astep * stride;
1203 /* Returns the volume of memory references accessed between two consecutive
1204 self-reuses of the reference DR. We consider the subscripts of DR in N
1205 loops, and LOOP_SIZES contains the volumes of accesses in each of the
1206 loops. LOOP is the innermost loop of the current loop nest. */
1208 static unsigned
1209 self_reuse_distance (data_reference_p dr, unsigned *loop_sizes, unsigned n,
1210 struct loop *loop)
1212 tree stride, access_fn;
1213 HOST_WIDE_INT *strides, astride;
1214 VEC (tree, heap) *access_fns;
1215 tree ref = DR_REF (dr);
1216 unsigned i, ret = ~0u;
1218 /* In the following example:
1220 for (i = 0; i < N; i++)
1221 for (j = 0; j < N; j++)
1222 use (a[j][i]);
1223 the same cache line is accessed each N steps (except if the change from
1224 i to i + 1 crosses the boundary of the cache line). Thus, for self-reuse,
1225 we cannot rely purely on the results of the data dependence analysis.
1227 Instead, we compute the stride of the reference in each loop, and consider
1228 the innermost loop in that the stride is less than cache size. */
1230 strides = XCNEWVEC (HOST_WIDE_INT, n);
1231 access_fns = DR_ACCESS_FNS (dr);
1233 for (i = 0; VEC_iterate (tree, access_fns, i, access_fn); i++)
1235 /* Keep track of the reference corresponding to the subscript, so that we
1236 know its stride. */
1237 while (handled_component_p (ref) && TREE_CODE (ref) != ARRAY_REF)
1238 ref = TREE_OPERAND (ref, 0);
1240 if (TREE_CODE (ref) == ARRAY_REF)
1242 stride = TYPE_SIZE_UNIT (TREE_TYPE (ref));
1243 if (host_integerp (stride, 1))
1244 astride = tree_low_cst (stride, 1);
1245 else
1246 astride = L1_CACHE_LINE_SIZE;
1248 ref = TREE_OPERAND (ref, 0);
1250 else
1251 astride = 1;
1253 add_subscript_strides (access_fn, astride, strides, n, loop);
1256 for (i = n; i-- > 0; )
1258 unsigned HOST_WIDE_INT s;
1260 s = strides[i] < 0 ? -strides[i] : strides[i];
1262 if (s < (unsigned) L1_CACHE_LINE_SIZE
1263 && (loop_sizes[i]
1264 > (unsigned) (L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION)))
1266 ret = loop_sizes[i];
1267 break;
1271 free (strides);
1272 return ret;
1275 /* Determines the distance till the first reuse of each reference in REFS
1276 in the loop nest of LOOP. NO_OTHER_REFS is true if there are no other
1277 memory references in the loop. */
1279 static void
1280 determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
1281 bool no_other_refs)
1283 struct loop *nest, *aloop;
1284 VEC (data_reference_p, heap) *datarefs = NULL;
1285 VEC (ddr_p, heap) *dependences = NULL;
1286 struct mem_ref_group *gr;
1287 struct mem_ref *ref, *refb;
1288 VEC (loop_p, heap) *vloops = NULL;
1289 unsigned *loop_data_size;
1290 unsigned i, j, n;
1291 unsigned volume, dist, adist;
1292 HOST_WIDE_INT vol;
1293 data_reference_p dr;
1294 ddr_p dep;
1296 if (loop->inner)
1297 return;
1299 /* Find the outermost loop of the loop nest of loop (we require that
1300 there are no sibling loops inside the nest). */
1301 nest = loop;
1302 while (1)
1304 aloop = loop_outer (nest);
1306 if (aloop == current_loops->tree_root
1307 || aloop->inner->next)
1308 break;
1310 nest = aloop;
1313 /* For each loop, determine the amount of data accessed in each iteration.
1314 We use this to estimate whether the reference is evicted from the
1315 cache before its reuse. */
1316 find_loop_nest (nest, &vloops);
1317 n = VEC_length (loop_p, vloops);
1318 loop_data_size = XNEWVEC (unsigned, n);
1319 volume = volume_of_references (refs);
1320 i = n;
1321 while (i-- != 0)
1323 loop_data_size[i] = volume;
1324 /* Bound the volume by the L2 cache size, since above this bound,
1325 all dependence distances are equivalent. */
1326 if (volume > L2_CACHE_SIZE_BYTES)
1327 continue;
1329 aloop = VEC_index (loop_p, vloops, i);
1330 vol = estimated_loop_iterations_int (aloop, false);
1331 if (vol < 0)
1332 vol = expected_loop_iterations (aloop);
1333 volume *= vol;
1336 /* Prepare the references in the form suitable for data dependence
1337 analysis. We ignore unanalyzable data references (the results
1338 are used just as a heuristics to estimate temporality of the
1339 references, hence we do not need to worry about correctness). */
1340 for (gr = refs; gr; gr = gr->next)
1341 for (ref = gr->refs; ref; ref = ref->next)
1343 dr = create_data_ref (nest, ref->mem, ref->stmt, !ref->write_p);
1345 if (dr)
1347 ref->reuse_distance = volume;
1348 dr->aux = ref;
1349 VEC_safe_push (data_reference_p, heap, datarefs, dr);
1351 else
1352 no_other_refs = false;
1355 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1357 dist = self_reuse_distance (dr, loop_data_size, n, loop);
1358 ref = dr->aux;
1359 if (ref->reuse_distance > dist)
1360 ref->reuse_distance = dist;
1362 if (no_other_refs)
1363 ref->independent_p = true;
1366 compute_all_dependences (datarefs, &dependences, vloops, true);
1368 for (i = 0; VEC_iterate (ddr_p, dependences, i, dep); i++)
1370 if (DDR_ARE_DEPENDENT (dep) == chrec_known)
1371 continue;
1373 ref = DDR_A (dep)->aux;
1374 refb = DDR_B (dep)->aux;
1376 if (DDR_ARE_DEPENDENT (dep) == chrec_dont_know
1377 || DDR_NUM_DIST_VECTS (dep) == 0)
1379 /* If the dependence cannot be analyzed, assume that there might be
1380 a reuse. */
1381 dist = 0;
1383 ref->independent_p = false;
1384 refb->independent_p = false;
1386 else
1388 /* The distance vectors are normalized to be always lexicographically
1389 positive, hence we cannot tell just from them whether DDR_A comes
1390 before DDR_B or vice versa. However, it is not important,
1391 anyway -- if DDR_A is close to DDR_B, then it is either reused in
1392 DDR_B (and it is not nontemporal), or it reuses the value of DDR_B
1393 in cache (and marking it as nontemporal would not affect
1394 anything). */
1396 dist = volume;
1397 for (j = 0; j < DDR_NUM_DIST_VECTS (dep); j++)
1399 adist = volume_of_dist_vector (DDR_DIST_VECT (dep, j),
1400 loop_data_size, n);
1402 /* If this is a dependence in the innermost loop (i.e., the
1403 distances in all superloops are zero) and it is not
1404 the trivial self-dependence with distance zero, record that
1405 the references are not completely independent. */
1406 if (lambda_vector_zerop (DDR_DIST_VECT (dep, j), n - 1)
1407 && (ref != refb
1408 || DDR_DIST_VECT (dep, j)[n-1] != 0))
1410 ref->independent_p = false;
1411 refb->independent_p = false;
1414 /* Ignore accesses closer than
1415 L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
1416 so that we use nontemporal prefetches e.g. if single memory
1417 location is accessed several times in a single iteration of
1418 the loop. */
1419 if (adist < L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION)
1420 continue;
1422 if (adist < dist)
1423 dist = adist;
1427 if (ref->reuse_distance > dist)
1428 ref->reuse_distance = dist;
1429 if (refb->reuse_distance > dist)
1430 refb->reuse_distance = dist;
1433 free_dependence_relations (dependences);
1434 free_data_refs (datarefs);
1435 free (loop_data_size);
1437 if (dump_file && (dump_flags & TDF_DETAILS))
1439 fprintf (dump_file, "Reuse distances:\n");
1440 for (gr = refs; gr; gr = gr->next)
1441 for (ref = gr->refs; ref; ref = ref->next)
1442 fprintf (dump_file, " ref %p distance %u\n",
1443 (void *) ref, ref->reuse_distance);
1447 /* Issue prefetch instructions for array references in LOOP. Returns
1448 true if the LOOP was unrolled. */
1450 static bool
1451 loop_prefetch_arrays (struct loop *loop)
1453 struct mem_ref_group *refs;
1454 unsigned ahead, ninsns, time, unroll_factor;
1455 HOST_WIDE_INT est_niter;
1456 struct tree_niter_desc desc;
1457 bool unrolled = false, no_other_refs;
1459 if (!maybe_hot_bb_p (loop->header))
1461 if (dump_file && (dump_flags & TDF_DETAILS))
1462 fprintf (dump_file, " ignored (cold area)\n");
1463 return false;
1466 /* Step 1: gather the memory references. */
1467 refs = gather_memory_references (loop, &no_other_refs);
1469 /* Step 2: estimate the reuse effects. */
1470 prune_by_reuse (refs);
1472 if (!anything_to_prefetch_p (refs))
1473 goto fail;
1475 determine_loop_nest_reuse (loop, refs, no_other_refs);
1477 /* Step 3: determine the ahead and unroll factor. */
1479 /* FIXME: the time should be weighted by the probabilities of the blocks in
1480 the loop body. */
1481 time = tree_num_loop_insns (loop, &eni_time_weights);
1482 ahead = (PREFETCH_LATENCY + time - 1) / time;
1483 est_niter = estimated_loop_iterations_int (loop, false);
1485 /* The prefetches will run for AHEAD iterations of the original loop. Unless
1486 the loop rolls at least AHEAD times, prefetching the references does not
1487 make sense. */
1488 if (est_niter >= 0 && est_niter <= (HOST_WIDE_INT) ahead)
1490 if (dump_file && (dump_flags & TDF_DETAILS))
1491 fprintf (dump_file,
1492 "Not prefetching -- loop estimated to roll only %d times\n",
1493 (int) est_niter);
1494 goto fail;
1497 mark_nontemporal_stores (loop, refs);
1499 ninsns = tree_num_loop_insns (loop, &eni_size_weights);
1500 unroll_factor = determine_unroll_factor (loop, refs, ninsns, &desc,
1501 est_niter);
1502 if (dump_file && (dump_flags & TDF_DETAILS))
1503 fprintf (dump_file, "Ahead %d, unroll factor %d\n", ahead, unroll_factor);
1505 /* Step 4: what to prefetch? */
1506 if (!schedule_prefetches (refs, unroll_factor, ahead))
1507 goto fail;
1509 /* Step 5: unroll the loop. TODO -- peeling of first and last few
1510 iterations so that we do not issue superfluous prefetches. */
1511 if (unroll_factor != 1)
1513 tree_unroll_loop (loop, unroll_factor,
1514 single_dom_exit (loop), &desc);
1515 unrolled = true;
1518 /* Step 6: issue the prefetches. */
1519 issue_prefetches (refs, unroll_factor, ahead);
1521 fail:
1522 release_mem_refs (refs);
1523 return unrolled;
1526 /* Issue prefetch instructions for array references in loops. */
1528 unsigned int
1529 tree_ssa_prefetch_arrays (void)
1531 loop_iterator li;
1532 struct loop *loop;
1533 bool unrolled = false;
1534 int todo_flags = 0;
1536 if (!HAVE_prefetch
1537 /* It is possible to ask compiler for say -mtune=i486 -march=pentium4.
1538 -mtune=i486 causes us having PREFETCH_BLOCK 0, since this is part
1539 of processor costs and i486 does not have prefetch, but
1540 -march=pentium4 causes HAVE_prefetch to be true. Ugh. */
1541 || PREFETCH_BLOCK == 0)
1542 return 0;
1544 if (dump_file && (dump_flags & TDF_DETAILS))
1546 fprintf (dump_file, "Prefetching parameters:\n");
1547 fprintf (dump_file, " simultaneous prefetches: %d\n",
1548 SIMULTANEOUS_PREFETCHES);
1549 fprintf (dump_file, " prefetch latency: %d\n", PREFETCH_LATENCY);
1550 fprintf (dump_file, " prefetch block size: %d\n", PREFETCH_BLOCK);
1551 fprintf (dump_file, " L1 cache size: %d lines, %d kB\n",
1552 L1_CACHE_SIZE_BYTES / L1_CACHE_LINE_SIZE, L1_CACHE_SIZE);
1553 fprintf (dump_file, " L1 cache line size: %d\n", L1_CACHE_LINE_SIZE);
1554 fprintf (dump_file, " L2 cache size: %d kB\n", L2_CACHE_SIZE);
1555 fprintf (dump_file, "\n");
1558 initialize_original_copy_tables ();
1560 if (!built_in_decls[BUILT_IN_PREFETCH])
1562 tree type = build_function_type (void_type_node,
1563 tree_cons (NULL_TREE,
1564 const_ptr_type_node,
1565 NULL_TREE));
1566 tree decl = add_builtin_function ("__builtin_prefetch", type,
1567 BUILT_IN_PREFETCH, BUILT_IN_NORMAL,
1568 NULL, NULL_TREE);
1569 DECL_IS_NOVOPS (decl) = true;
1570 built_in_decls[BUILT_IN_PREFETCH] = decl;
1573 /* We assume that size of cache line is a power of two, so verify this
1574 here. */
1575 gcc_assert ((PREFETCH_BLOCK & (PREFETCH_BLOCK - 1)) == 0);
1577 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1579 if (dump_file && (dump_flags & TDF_DETAILS))
1580 fprintf (dump_file, "Processing loop %d:\n", loop->num);
1582 unrolled |= loop_prefetch_arrays (loop);
1584 if (dump_file && (dump_flags & TDF_DETAILS))
1585 fprintf (dump_file, "\n\n");
1588 if (unrolled)
1590 scev_reset ();
1591 todo_flags |= TODO_cleanup_cfg;
1594 free_original_copy_tables ();
1595 return todo_flags;