* var-tracking.c (insn_stack_adjust_offset_pre_post): If insn has a
[official-gcc.git] / gcc / tree-ssa-loop-prefetch.c
blob6da4bf232aaa9b52b8d3a1059ac8824e3dc1e4fe
1 /* Array prefetching.
2 Copyright (C) 2005, 2007, 2008 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) per thousand. */
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 gimple 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, gimple 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 gimple 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 gimple 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, gimple stmt)
456 tree base;
457 HOST_WIDE_INT step, delta;
458 struct mem_ref_group *agrp;
460 if (get_base_address (ref) == NULL)
461 return false;
463 if (!analyze_ref (loop, &ref, &base, &step, &delta, stmt))
464 return false;
466 /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
467 are integer constants. */
468 agrp = find_or_create_group (refs, base, step);
469 record_ref (agrp, stmt, ref, delta, write_p);
471 return true;
474 /* Record the suitable memory references in LOOP. NO_OTHER_REFS is set to
475 true if there are no other memory references inside the loop. */
477 static struct mem_ref_group *
478 gather_memory_references (struct loop *loop, bool *no_other_refs)
480 basic_block *body = get_loop_body_in_dom_order (loop);
481 basic_block bb;
482 unsigned i;
483 gimple_stmt_iterator bsi;
484 gimple stmt;
485 tree lhs, rhs;
486 struct mem_ref_group *refs = NULL;
488 *no_other_refs = true;
490 /* Scan the loop body in order, so that the former references precede the
491 later ones. */
492 for (i = 0; i < loop->num_nodes; i++)
494 bb = body[i];
495 if (bb->loop_father != loop)
496 continue;
498 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
500 stmt = gsi_stmt (bsi);
502 if (gimple_code (stmt) != GIMPLE_ASSIGN)
504 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)
505 || (is_gimple_call (stmt)
506 && !(gimple_call_flags (stmt) & ECF_CONST)))
507 *no_other_refs = false;
508 continue;
511 lhs = gimple_assign_lhs (stmt);
512 rhs = gimple_assign_rhs1 (stmt);
514 if (REFERENCE_CLASS_P (rhs))
515 *no_other_refs &= gather_memory_references_ref (loop, &refs,
516 rhs, false, stmt);
517 if (REFERENCE_CLASS_P (lhs))
518 *no_other_refs &= gather_memory_references_ref (loop, &refs,
519 lhs, true, stmt);
522 free (body);
524 return refs;
527 /* Prune the prefetch candidate REF using the self-reuse. */
529 static void
530 prune_ref_by_self_reuse (struct mem_ref *ref)
532 HOST_WIDE_INT step = ref->group->step;
533 bool backward = step < 0;
535 if (step == 0)
537 /* Prefetch references to invariant address just once. */
538 ref->prefetch_before = 1;
539 return;
542 if (backward)
543 step = -step;
545 if (step > PREFETCH_BLOCK)
546 return;
548 if ((backward && HAVE_BACKWARD_PREFETCH)
549 || (!backward && HAVE_FORWARD_PREFETCH))
551 ref->prefetch_before = 1;
552 return;
555 ref->prefetch_mod = PREFETCH_BLOCK / step;
558 /* Divides X by BY, rounding down. */
560 static HOST_WIDE_INT
561 ddown (HOST_WIDE_INT x, unsigned HOST_WIDE_INT by)
563 gcc_assert (by > 0);
565 if (x >= 0)
566 return x / by;
567 else
568 return (x + by - 1) / by;
571 /* Prune the prefetch candidate REF using the reuse with BY.
572 If BY_IS_BEFORE is true, BY is before REF in the loop. */
574 static void
575 prune_ref_by_group_reuse (struct mem_ref *ref, struct mem_ref *by,
576 bool by_is_before)
578 HOST_WIDE_INT step = ref->group->step;
579 bool backward = step < 0;
580 HOST_WIDE_INT delta_r = ref->delta, delta_b = by->delta;
581 HOST_WIDE_INT delta = delta_b - delta_r;
582 HOST_WIDE_INT hit_from;
583 unsigned HOST_WIDE_INT prefetch_before, prefetch_block;
585 if (delta == 0)
587 /* If the references has the same address, only prefetch the
588 former. */
589 if (by_is_before)
590 ref->prefetch_before = 0;
592 return;
595 if (!step)
597 /* If the reference addresses are invariant and fall into the
598 same cache line, prefetch just the first one. */
599 if (!by_is_before)
600 return;
602 if (ddown (ref->delta, PREFETCH_BLOCK)
603 != ddown (by->delta, PREFETCH_BLOCK))
604 return;
606 ref->prefetch_before = 0;
607 return;
610 /* Only prune the reference that is behind in the array. */
611 if (backward)
613 if (delta > 0)
614 return;
616 /* Transform the data so that we may assume that the accesses
617 are forward. */
618 delta = - delta;
619 step = -step;
620 delta_r = PREFETCH_BLOCK - 1 - delta_r;
621 delta_b = PREFETCH_BLOCK - 1 - delta_b;
623 else
625 if (delta < 0)
626 return;
629 /* Check whether the two references are likely to hit the same cache
630 line, and how distant the iterations in that it occurs are from
631 each other. */
633 if (step <= PREFETCH_BLOCK)
635 /* The accesses are sure to meet. Let us check when. */
636 hit_from = ddown (delta_b, PREFETCH_BLOCK) * PREFETCH_BLOCK;
637 prefetch_before = (hit_from - delta_r + step - 1) / step;
639 if (prefetch_before < ref->prefetch_before)
640 ref->prefetch_before = prefetch_before;
642 return;
645 /* A more complicated case. First let us ensure that size of cache line
646 and step are coprime (here we assume that PREFETCH_BLOCK is a power
647 of two. */
648 prefetch_block = PREFETCH_BLOCK;
649 while ((step & 1) == 0
650 && prefetch_block > 1)
652 step >>= 1;
653 prefetch_block >>= 1;
654 delta >>= 1;
657 /* Now step > prefetch_block, and step and prefetch_block are coprime.
658 Determine the probability that the accesses hit the same cache line. */
660 prefetch_before = delta / step;
661 delta %= step;
662 if ((unsigned HOST_WIDE_INT) delta
663 <= (prefetch_block * ACCEPTABLE_MISS_RATE / 1000))
665 if (prefetch_before < ref->prefetch_before)
666 ref->prefetch_before = prefetch_before;
668 return;
671 /* Try also the following iteration. */
672 prefetch_before++;
673 delta = step - delta;
674 if ((unsigned HOST_WIDE_INT) delta
675 <= (prefetch_block * ACCEPTABLE_MISS_RATE / 1000))
677 if (prefetch_before < ref->prefetch_before)
678 ref->prefetch_before = prefetch_before;
680 return;
683 /* The ref probably does not reuse by. */
684 return;
687 /* Prune the prefetch candidate REF using the reuses with other references
688 in REFS. */
690 static void
691 prune_ref_by_reuse (struct mem_ref *ref, struct mem_ref *refs)
693 struct mem_ref *prune_by;
694 bool before = true;
696 prune_ref_by_self_reuse (ref);
698 for (prune_by = refs; prune_by; prune_by = prune_by->next)
700 if (prune_by == ref)
702 before = false;
703 continue;
706 if (!WRITE_CAN_USE_READ_PREFETCH
707 && ref->write_p
708 && !prune_by->write_p)
709 continue;
710 if (!READ_CAN_USE_WRITE_PREFETCH
711 && !ref->write_p
712 && prune_by->write_p)
713 continue;
715 prune_ref_by_group_reuse (ref, prune_by, before);
719 /* Prune the prefetch candidates in GROUP using the reuse analysis. */
721 static void
722 prune_group_by_reuse (struct mem_ref_group *group)
724 struct mem_ref *ref_pruned;
726 for (ref_pruned = group->refs; ref_pruned; ref_pruned = ref_pruned->next)
728 prune_ref_by_reuse (ref_pruned, group->refs);
730 if (dump_file && (dump_flags & TDF_DETAILS))
732 fprintf (dump_file, "Reference %p:", (void *) ref_pruned);
734 if (ref_pruned->prefetch_before == PREFETCH_ALL
735 && ref_pruned->prefetch_mod == 1)
736 fprintf (dump_file, " no restrictions");
737 else if (ref_pruned->prefetch_before == 0)
738 fprintf (dump_file, " do not prefetch");
739 else if (ref_pruned->prefetch_before <= ref_pruned->prefetch_mod)
740 fprintf (dump_file, " prefetch once");
741 else
743 if (ref_pruned->prefetch_before != PREFETCH_ALL)
745 fprintf (dump_file, " prefetch before ");
746 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC,
747 ref_pruned->prefetch_before);
749 if (ref_pruned->prefetch_mod != 1)
751 fprintf (dump_file, " prefetch mod ");
752 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC,
753 ref_pruned->prefetch_mod);
756 fprintf (dump_file, "\n");
761 /* Prune the list of prefetch candidates GROUPS using the reuse analysis. */
763 static void
764 prune_by_reuse (struct mem_ref_group *groups)
766 for (; groups; groups = groups->next)
767 prune_group_by_reuse (groups);
770 /* Returns true if we should issue prefetch for REF. */
772 static bool
773 should_issue_prefetch_p (struct mem_ref *ref)
775 /* For now do not issue prefetches for only first few of the
776 iterations. */
777 if (ref->prefetch_before != PREFETCH_ALL)
778 return false;
780 /* Do not prefetch nontemporal stores. */
781 if (ref->storent_p)
782 return false;
784 return true;
787 /* Decide which of the prefetch candidates in GROUPS to prefetch.
788 AHEAD is the number of iterations to prefetch ahead (which corresponds
789 to the number of simultaneous instances of one prefetch running at a
790 time). UNROLL_FACTOR is the factor by that the loop is going to be
791 unrolled. Returns true if there is anything to prefetch. */
793 static bool
794 schedule_prefetches (struct mem_ref_group *groups, unsigned unroll_factor,
795 unsigned ahead)
797 unsigned remaining_prefetch_slots, n_prefetches, prefetch_slots;
798 unsigned slots_per_prefetch;
799 struct mem_ref *ref;
800 bool any = false;
802 /* At most SIMULTANEOUS_PREFETCHES should be running at the same time. */
803 remaining_prefetch_slots = SIMULTANEOUS_PREFETCHES;
805 /* The prefetch will run for AHEAD iterations of the original loop, i.e.,
806 AHEAD / UNROLL_FACTOR iterations of the unrolled loop. In each iteration,
807 it will need a prefetch slot. */
808 slots_per_prefetch = (ahead + unroll_factor / 2) / unroll_factor;
809 if (dump_file && (dump_flags & TDF_DETAILS))
810 fprintf (dump_file, "Each prefetch instruction takes %u prefetch slots.\n",
811 slots_per_prefetch);
813 /* For now we just take memory references one by one and issue
814 prefetches for as many as possible. The groups are sorted
815 starting with the largest step, since the references with
816 large step are more likely to cause many cache misses. */
818 for (; groups; groups = groups->next)
819 for (ref = groups->refs; ref; ref = ref->next)
821 if (!should_issue_prefetch_p (ref))
822 continue;
824 /* If we need to prefetch the reference each PREFETCH_MOD iterations,
825 and we unroll the loop UNROLL_FACTOR times, we need to insert
826 ceil (UNROLL_FACTOR / PREFETCH_MOD) instructions in each
827 iteration. */
828 n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
829 / ref->prefetch_mod);
830 prefetch_slots = n_prefetches * slots_per_prefetch;
832 /* If more than half of the prefetches would be lost anyway, do not
833 issue the prefetch. */
834 if (2 * remaining_prefetch_slots < prefetch_slots)
835 continue;
837 ref->issue_prefetch_p = true;
839 if (remaining_prefetch_slots <= prefetch_slots)
840 return true;
841 remaining_prefetch_slots -= prefetch_slots;
842 any = true;
845 return any;
848 /* Determine whether there is any reference suitable for prefetching
849 in GROUPS. */
851 static bool
852 anything_to_prefetch_p (struct mem_ref_group *groups)
854 struct mem_ref *ref;
856 for (; groups; groups = groups->next)
857 for (ref = groups->refs; ref; ref = ref->next)
858 if (should_issue_prefetch_p (ref))
859 return true;
861 return false;
864 /* Issue prefetches for the reference REF into loop as decided before.
865 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR
866 is the factor by which LOOP was unrolled. */
868 static void
869 issue_prefetch_ref (struct mem_ref *ref, unsigned unroll_factor, unsigned ahead)
871 HOST_WIDE_INT delta;
872 tree addr, addr_base, write_p, local;
873 gimple prefetch;
874 gimple_stmt_iterator bsi;
875 unsigned n_prefetches, ap;
876 bool nontemporal = ref->reuse_distance >= L2_CACHE_SIZE_BYTES;
878 if (dump_file && (dump_flags & TDF_DETAILS))
879 fprintf (dump_file, "Issued%s prefetch for %p.\n",
880 nontemporal ? " nontemporal" : "",
881 (void *) ref);
883 bsi = gsi_for_stmt (ref->stmt);
885 n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
886 / ref->prefetch_mod);
887 addr_base = build_fold_addr_expr_with_type (ref->mem, ptr_type_node);
888 addr_base = force_gimple_operand_gsi (&bsi, unshare_expr (addr_base),
889 true, NULL, true, GSI_SAME_STMT);
890 write_p = ref->write_p ? integer_one_node : integer_zero_node;
891 local = build_int_cst (integer_type_node, nontemporal ? 0 : 3);
893 for (ap = 0; ap < n_prefetches; ap++)
895 /* Determine the address to prefetch. */
896 delta = (ahead + ap * ref->prefetch_mod) * ref->group->step;
897 addr = fold_build2 (POINTER_PLUS_EXPR, ptr_type_node,
898 addr_base, size_int (delta));
899 addr = force_gimple_operand_gsi (&bsi, unshare_expr (addr), true, NULL,
900 true, GSI_SAME_STMT);
902 /* Create the prefetch instruction. */
903 prefetch = gimple_build_call (built_in_decls[BUILT_IN_PREFETCH],
904 3, addr, write_p, local);
905 gsi_insert_before (&bsi, prefetch, GSI_SAME_STMT);
909 /* Issue prefetches for the references in GROUPS into loop as decided before.
910 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR is the
911 factor by that LOOP was unrolled. */
913 static void
914 issue_prefetches (struct mem_ref_group *groups,
915 unsigned unroll_factor, unsigned ahead)
917 struct mem_ref *ref;
919 for (; groups; groups = groups->next)
920 for (ref = groups->refs; ref; ref = ref->next)
921 if (ref->issue_prefetch_p)
922 issue_prefetch_ref (ref, unroll_factor, ahead);
925 /* Returns true if REF is a memory write for that a nontemporal store insn
926 can be used. */
928 static bool
929 nontemporal_store_p (struct mem_ref *ref)
931 enum machine_mode mode;
932 enum insn_code code;
934 /* REF must be a write that is not reused. We require it to be independent
935 on all other memory references in the loop, as the nontemporal stores may
936 be reordered with respect to other memory references. */
937 if (!ref->write_p
938 || !ref->independent_p
939 || ref->reuse_distance < L2_CACHE_SIZE_BYTES)
940 return false;
942 /* Check that we have the storent instruction for the mode. */
943 mode = TYPE_MODE (TREE_TYPE (ref->mem));
944 if (mode == BLKmode)
945 return false;
947 code = optab_handler (storent_optab, mode)->insn_code;
948 return code != CODE_FOR_nothing;
951 /* If REF is a nontemporal store, we mark the corresponding modify statement
952 and return true. Otherwise, we return false. */
954 static bool
955 mark_nontemporal_store (struct mem_ref *ref)
957 if (!nontemporal_store_p (ref))
958 return false;
960 if (dump_file && (dump_flags & TDF_DETAILS))
961 fprintf (dump_file, "Marked reference %p as a nontemporal store.\n",
962 (void *) ref);
964 gimple_assign_set_nontemporal_move (ref->stmt, true);
965 ref->storent_p = true;
967 return true;
970 /* Issue a memory fence instruction after LOOP. */
972 static void
973 emit_mfence_after_loop (struct loop *loop)
975 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
976 edge exit;
977 gimple call;
978 gimple_stmt_iterator bsi;
979 unsigned i;
981 for (i = 0; VEC_iterate (edge, exits, i, exit); i++)
983 call = gimple_build_call (FENCE_FOLLOWING_MOVNT, 0);
985 if (!single_pred_p (exit->dest)
986 /* If possible, we prefer not to insert the fence on other paths
987 in cfg. */
988 && !(exit->flags & EDGE_ABNORMAL))
989 split_loop_exit_edge (exit);
990 bsi = gsi_after_labels (exit->dest);
992 gsi_insert_before (&bsi, call, GSI_NEW_STMT);
993 mark_virtual_ops_for_renaming (call);
996 VEC_free (edge, heap, exits);
997 update_ssa (TODO_update_ssa_only_virtuals);
1000 /* Returns true if we can use storent in loop, false otherwise. */
1002 static bool
1003 may_use_storent_in_loop_p (struct loop *loop)
1005 bool ret = true;
1007 if (loop->inner != NULL)
1008 return false;
1010 /* If we must issue a mfence insn after using storent, check that there
1011 is a suitable place for it at each of the loop exits. */
1012 if (FENCE_FOLLOWING_MOVNT != NULL_TREE)
1014 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1015 unsigned i;
1016 edge exit;
1018 for (i = 0; VEC_iterate (edge, exits, i, exit); i++)
1019 if ((exit->flags & EDGE_ABNORMAL)
1020 && exit->dest == EXIT_BLOCK_PTR)
1021 ret = false;
1023 VEC_free (edge, heap, exits);
1026 return ret;
1029 /* Marks nontemporal stores in LOOP. GROUPS contains the description of memory
1030 references in the loop. */
1032 static void
1033 mark_nontemporal_stores (struct loop *loop, struct mem_ref_group *groups)
1035 struct mem_ref *ref;
1036 bool any = false;
1038 if (!may_use_storent_in_loop_p (loop))
1039 return;
1041 for (; groups; groups = groups->next)
1042 for (ref = groups->refs; ref; ref = ref->next)
1043 any |= mark_nontemporal_store (ref);
1045 if (any && FENCE_FOLLOWING_MOVNT != NULL_TREE)
1046 emit_mfence_after_loop (loop);
1049 /* Determines whether we can profitably unroll LOOP FACTOR times, and if
1050 this is the case, fill in DESC by the description of number of
1051 iterations. */
1053 static bool
1054 should_unroll_loop_p (struct loop *loop, struct tree_niter_desc *desc,
1055 unsigned factor)
1057 if (!can_unroll_loop_p (loop, factor, desc))
1058 return false;
1060 /* We only consider loops without control flow for unrolling. This is not
1061 a hard restriction -- tree_unroll_loop works with arbitrary loops
1062 as well; but the unrolling/prefetching is usually more profitable for
1063 loops consisting of a single basic block, and we want to limit the
1064 code growth. */
1065 if (loop->num_nodes > 2)
1066 return false;
1068 return true;
1071 /* Determine the coefficient by that unroll LOOP, from the information
1072 contained in the list of memory references REFS. Description of
1073 umber of iterations of LOOP is stored to DESC. NINSNS is the number of
1074 insns of the LOOP. EST_NITER is the estimated number of iterations of
1075 the loop, or -1 if no estimate is available. */
1077 static unsigned
1078 determine_unroll_factor (struct loop *loop, struct mem_ref_group *refs,
1079 unsigned ninsns, struct tree_niter_desc *desc,
1080 HOST_WIDE_INT est_niter)
1082 unsigned upper_bound;
1083 unsigned nfactor, factor, mod_constraint;
1084 struct mem_ref_group *agp;
1085 struct mem_ref *ref;
1087 /* First check whether the loop is not too large to unroll. We ignore
1088 PARAM_MAX_UNROLL_TIMES, because for small loops, it prevented us
1089 from unrolling them enough to make exactly one cache line covered by each
1090 iteration. Also, the goal of PARAM_MAX_UNROLL_TIMES is to prevent
1091 us from unrolling the loops too many times in cases where we only expect
1092 gains from better scheduling and decreasing loop overhead, which is not
1093 the case here. */
1094 upper_bound = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / ninsns;
1096 /* If we unrolled the loop more times than it iterates, the unrolled version
1097 of the loop would be never entered. */
1098 if (est_niter >= 0 && est_niter < (HOST_WIDE_INT) upper_bound)
1099 upper_bound = est_niter;
1101 if (upper_bound <= 1)
1102 return 1;
1104 /* Choose the factor so that we may prefetch each cache just once,
1105 but bound the unrolling by UPPER_BOUND. */
1106 factor = 1;
1107 for (agp = refs; agp; agp = agp->next)
1108 for (ref = agp->refs; ref; ref = ref->next)
1109 if (should_issue_prefetch_p (ref))
1111 mod_constraint = ref->prefetch_mod;
1112 nfactor = least_common_multiple (mod_constraint, factor);
1113 if (nfactor <= upper_bound)
1114 factor = nfactor;
1117 if (!should_unroll_loop_p (loop, desc, factor))
1118 return 1;
1120 return factor;
1123 /* Returns the total volume of the memory references REFS, taking into account
1124 reuses in the innermost loop and cache line size. TODO -- we should also
1125 take into account reuses across the iterations of the loops in the loop
1126 nest. */
1128 static unsigned
1129 volume_of_references (struct mem_ref_group *refs)
1131 unsigned volume = 0;
1132 struct mem_ref_group *gr;
1133 struct mem_ref *ref;
1135 for (gr = refs; gr; gr = gr->next)
1136 for (ref = gr->refs; ref; ref = ref->next)
1138 /* Almost always reuses another value? */
1139 if (ref->prefetch_before != PREFETCH_ALL)
1140 continue;
1142 /* If several iterations access the same cache line, use the size of
1143 the line divided by this number. Otherwise, a cache line is
1144 accessed in each iteration. TODO -- in the latter case, we should
1145 take the size of the reference into account, rounding it up on cache
1146 line size multiple. */
1147 volume += L1_CACHE_LINE_SIZE / ref->prefetch_mod;
1149 return volume;
1152 /* Returns the volume of memory references accessed across VEC iterations of
1153 loops, whose sizes are described in the LOOP_SIZES array. N is the number
1154 of the loops in the nest (length of VEC and LOOP_SIZES vectors). */
1156 static unsigned
1157 volume_of_dist_vector (lambda_vector vec, unsigned *loop_sizes, unsigned n)
1159 unsigned i;
1161 for (i = 0; i < n; i++)
1162 if (vec[i] != 0)
1163 break;
1165 if (i == n)
1166 return 0;
1168 gcc_assert (vec[i] > 0);
1170 /* We ignore the parts of the distance vector in subloops, since usually
1171 the numbers of iterations are much smaller. */
1172 return loop_sizes[i] * vec[i];
1175 /* Add the steps of ACCESS_FN multiplied by STRIDE to the array STRIDE
1176 at the position corresponding to the loop of the step. N is the depth
1177 of the considered loop nest, and, LOOP is its innermost loop. */
1179 static void
1180 add_subscript_strides (tree access_fn, unsigned stride,
1181 HOST_WIDE_INT *strides, unsigned n, struct loop *loop)
1183 struct loop *aloop;
1184 tree step;
1185 HOST_WIDE_INT astep;
1186 unsigned min_depth = loop_depth (loop) - n;
1188 while (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
1190 aloop = get_chrec_loop (access_fn);
1191 step = CHREC_RIGHT (access_fn);
1192 access_fn = CHREC_LEFT (access_fn);
1194 if ((unsigned) loop_depth (aloop) <= min_depth)
1195 continue;
1197 if (host_integerp (step, 0))
1198 astep = tree_low_cst (step, 0);
1199 else
1200 astep = L1_CACHE_LINE_SIZE;
1202 strides[n - 1 - loop_depth (loop) + loop_depth (aloop)] += astep * stride;
1207 /* Returns the volume of memory references accessed between two consecutive
1208 self-reuses of the reference DR. We consider the subscripts of DR in N
1209 loops, and LOOP_SIZES contains the volumes of accesses in each of the
1210 loops. LOOP is the innermost loop of the current loop nest. */
1212 static unsigned
1213 self_reuse_distance (data_reference_p dr, unsigned *loop_sizes, unsigned n,
1214 struct loop *loop)
1216 tree stride, access_fn;
1217 HOST_WIDE_INT *strides, astride;
1218 VEC (tree, heap) *access_fns;
1219 tree ref = DR_REF (dr);
1220 unsigned i, ret = ~0u;
1222 /* In the following example:
1224 for (i = 0; i < N; i++)
1225 for (j = 0; j < N; j++)
1226 use (a[j][i]);
1227 the same cache line is accessed each N steps (except if the change from
1228 i to i + 1 crosses the boundary of the cache line). Thus, for self-reuse,
1229 we cannot rely purely on the results of the data dependence analysis.
1231 Instead, we compute the stride of the reference in each loop, and consider
1232 the innermost loop in that the stride is less than cache size. */
1234 strides = XCNEWVEC (HOST_WIDE_INT, n);
1235 access_fns = DR_ACCESS_FNS (dr);
1237 for (i = 0; VEC_iterate (tree, access_fns, i, access_fn); i++)
1239 /* Keep track of the reference corresponding to the subscript, so that we
1240 know its stride. */
1241 while (handled_component_p (ref) && TREE_CODE (ref) != ARRAY_REF)
1242 ref = TREE_OPERAND (ref, 0);
1244 if (TREE_CODE (ref) == ARRAY_REF)
1246 stride = TYPE_SIZE_UNIT (TREE_TYPE (ref));
1247 if (host_integerp (stride, 1))
1248 astride = tree_low_cst (stride, 1);
1249 else
1250 astride = L1_CACHE_LINE_SIZE;
1252 ref = TREE_OPERAND (ref, 0);
1254 else
1255 astride = 1;
1257 add_subscript_strides (access_fn, astride, strides, n, loop);
1260 for (i = n; i-- > 0; )
1262 unsigned HOST_WIDE_INT s;
1264 s = strides[i] < 0 ? -strides[i] : strides[i];
1266 if (s < (unsigned) L1_CACHE_LINE_SIZE
1267 && (loop_sizes[i]
1268 > (unsigned) (L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION)))
1270 ret = loop_sizes[i];
1271 break;
1275 free (strides);
1276 return ret;
1279 /* Determines the distance till the first reuse of each reference in REFS
1280 in the loop nest of LOOP. NO_OTHER_REFS is true if there are no other
1281 memory references in the loop. */
1283 static void
1284 determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
1285 bool no_other_refs)
1287 struct loop *nest, *aloop;
1288 VEC (data_reference_p, heap) *datarefs = NULL;
1289 VEC (ddr_p, heap) *dependences = NULL;
1290 struct mem_ref_group *gr;
1291 struct mem_ref *ref, *refb;
1292 VEC (loop_p, heap) *vloops = NULL;
1293 unsigned *loop_data_size;
1294 unsigned i, j, n;
1295 unsigned volume, dist, adist;
1296 HOST_WIDE_INT vol;
1297 data_reference_p dr;
1298 ddr_p dep;
1300 if (loop->inner)
1301 return;
1303 /* Find the outermost loop of the loop nest of loop (we require that
1304 there are no sibling loops inside the nest). */
1305 nest = loop;
1306 while (1)
1308 aloop = loop_outer (nest);
1310 if (aloop == current_loops->tree_root
1311 || aloop->inner->next)
1312 break;
1314 nest = aloop;
1317 /* For each loop, determine the amount of data accessed in each iteration.
1318 We use this to estimate whether the reference is evicted from the
1319 cache before its reuse. */
1320 find_loop_nest (nest, &vloops);
1321 n = VEC_length (loop_p, vloops);
1322 loop_data_size = XNEWVEC (unsigned, n);
1323 volume = volume_of_references (refs);
1324 i = n;
1325 while (i-- != 0)
1327 loop_data_size[i] = volume;
1328 /* Bound the volume by the L2 cache size, since above this bound,
1329 all dependence distances are equivalent. */
1330 if (volume > L2_CACHE_SIZE_BYTES)
1331 continue;
1333 aloop = VEC_index (loop_p, vloops, i);
1334 vol = estimated_loop_iterations_int (aloop, false);
1335 if (vol < 0)
1336 vol = expected_loop_iterations (aloop);
1337 volume *= vol;
1340 /* Prepare the references in the form suitable for data dependence
1341 analysis. We ignore unanalyzable data references (the results
1342 are used just as a heuristics to estimate temporality of the
1343 references, hence we do not need to worry about correctness). */
1344 for (gr = refs; gr; gr = gr->next)
1345 for (ref = gr->refs; ref; ref = ref->next)
1347 dr = create_data_ref (nest, ref->mem, ref->stmt, !ref->write_p);
1349 if (dr)
1351 ref->reuse_distance = volume;
1352 dr->aux = ref;
1353 VEC_safe_push (data_reference_p, heap, datarefs, dr);
1355 else
1356 no_other_refs = false;
1359 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1361 dist = self_reuse_distance (dr, loop_data_size, n, loop);
1362 ref = (struct mem_ref *) dr->aux;
1363 if (ref->reuse_distance > dist)
1364 ref->reuse_distance = dist;
1366 if (no_other_refs)
1367 ref->independent_p = true;
1370 compute_all_dependences (datarefs, &dependences, vloops, true);
1372 for (i = 0; VEC_iterate (ddr_p, dependences, i, dep); i++)
1374 if (DDR_ARE_DEPENDENT (dep) == chrec_known)
1375 continue;
1377 ref = (struct mem_ref *) DDR_A (dep)->aux;
1378 refb = (struct mem_ref *) DDR_B (dep)->aux;
1380 if (DDR_ARE_DEPENDENT (dep) == chrec_dont_know
1381 || DDR_NUM_DIST_VECTS (dep) == 0)
1383 /* If the dependence cannot be analyzed, assume that there might be
1384 a reuse. */
1385 dist = 0;
1387 ref->independent_p = false;
1388 refb->independent_p = false;
1390 else
1392 /* The distance vectors are normalized to be always lexicographically
1393 positive, hence we cannot tell just from them whether DDR_A comes
1394 before DDR_B or vice versa. However, it is not important,
1395 anyway -- if DDR_A is close to DDR_B, then it is either reused in
1396 DDR_B (and it is not nontemporal), or it reuses the value of DDR_B
1397 in cache (and marking it as nontemporal would not affect
1398 anything). */
1400 dist = volume;
1401 for (j = 0; j < DDR_NUM_DIST_VECTS (dep); j++)
1403 adist = volume_of_dist_vector (DDR_DIST_VECT (dep, j),
1404 loop_data_size, n);
1406 /* If this is a dependence in the innermost loop (i.e., the
1407 distances in all superloops are zero) and it is not
1408 the trivial self-dependence with distance zero, record that
1409 the references are not completely independent. */
1410 if (lambda_vector_zerop (DDR_DIST_VECT (dep, j), n - 1)
1411 && (ref != refb
1412 || DDR_DIST_VECT (dep, j)[n-1] != 0))
1414 ref->independent_p = false;
1415 refb->independent_p = false;
1418 /* Ignore accesses closer than
1419 L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
1420 so that we use nontemporal prefetches e.g. if single memory
1421 location is accessed several times in a single iteration of
1422 the loop. */
1423 if (adist < L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION)
1424 continue;
1426 if (adist < dist)
1427 dist = adist;
1431 if (ref->reuse_distance > dist)
1432 ref->reuse_distance = dist;
1433 if (refb->reuse_distance > dist)
1434 refb->reuse_distance = dist;
1437 free_dependence_relations (dependences);
1438 free_data_refs (datarefs);
1439 free (loop_data_size);
1441 if (dump_file && (dump_flags & TDF_DETAILS))
1443 fprintf (dump_file, "Reuse distances:\n");
1444 for (gr = refs; gr; gr = gr->next)
1445 for (ref = gr->refs; ref; ref = ref->next)
1446 fprintf (dump_file, " ref %p distance %u\n",
1447 (void *) ref, ref->reuse_distance);
1451 /* Issue prefetch instructions for array references in LOOP. Returns
1452 true if the LOOP was unrolled. */
1454 static bool
1455 loop_prefetch_arrays (struct loop *loop)
1457 struct mem_ref_group *refs;
1458 unsigned ahead, ninsns, time, unroll_factor;
1459 HOST_WIDE_INT est_niter;
1460 struct tree_niter_desc desc;
1461 bool unrolled = false, no_other_refs;
1463 if (optimize_loop_nest_for_size_p (loop))
1465 if (dump_file && (dump_flags & TDF_DETAILS))
1466 fprintf (dump_file, " ignored (cold area)\n");
1467 return false;
1470 /* Step 1: gather the memory references. */
1471 refs = gather_memory_references (loop, &no_other_refs);
1473 /* Step 2: estimate the reuse effects. */
1474 prune_by_reuse (refs);
1476 if (!anything_to_prefetch_p (refs))
1477 goto fail;
1479 determine_loop_nest_reuse (loop, refs, no_other_refs);
1481 /* Step 3: determine the ahead and unroll factor. */
1483 /* FIXME: the time should be weighted by the probabilities of the blocks in
1484 the loop body. */
1485 time = tree_num_loop_insns (loop, &eni_time_weights);
1486 ahead = (PREFETCH_LATENCY + time - 1) / time;
1487 est_niter = estimated_loop_iterations_int (loop, false);
1489 /* The prefetches will run for AHEAD iterations of the original loop. Unless
1490 the loop rolls at least AHEAD times, prefetching the references does not
1491 make sense. */
1492 if (est_niter >= 0 && est_niter <= (HOST_WIDE_INT) ahead)
1494 if (dump_file && (dump_flags & TDF_DETAILS))
1495 fprintf (dump_file,
1496 "Not prefetching -- loop estimated to roll only %d times\n",
1497 (int) est_niter);
1498 goto fail;
1501 mark_nontemporal_stores (loop, refs);
1503 ninsns = tree_num_loop_insns (loop, &eni_size_weights);
1504 unroll_factor = determine_unroll_factor (loop, refs, ninsns, &desc,
1505 est_niter);
1506 if (dump_file && (dump_flags & TDF_DETAILS))
1507 fprintf (dump_file, "Ahead %d, unroll factor %d\n", ahead, unroll_factor);
1509 /* Step 4: what to prefetch? */
1510 if (!schedule_prefetches (refs, unroll_factor, ahead))
1511 goto fail;
1513 /* Step 5: unroll the loop. TODO -- peeling of first and last few
1514 iterations so that we do not issue superfluous prefetches. */
1515 if (unroll_factor != 1)
1517 tree_unroll_loop (loop, unroll_factor,
1518 single_dom_exit (loop), &desc);
1519 unrolled = true;
1522 /* Step 6: issue the prefetches. */
1523 issue_prefetches (refs, unroll_factor, ahead);
1525 fail:
1526 release_mem_refs (refs);
1527 return unrolled;
1530 /* Issue prefetch instructions for array references in loops. */
1532 unsigned int
1533 tree_ssa_prefetch_arrays (void)
1535 loop_iterator li;
1536 struct loop *loop;
1537 bool unrolled = false;
1538 int todo_flags = 0;
1540 if (!HAVE_prefetch
1541 /* It is possible to ask compiler for say -mtune=i486 -march=pentium4.
1542 -mtune=i486 causes us having PREFETCH_BLOCK 0, since this is part
1543 of processor costs and i486 does not have prefetch, but
1544 -march=pentium4 causes HAVE_prefetch to be true. Ugh. */
1545 || PREFETCH_BLOCK == 0)
1546 return 0;
1548 if (dump_file && (dump_flags & TDF_DETAILS))
1550 fprintf (dump_file, "Prefetching parameters:\n");
1551 fprintf (dump_file, " simultaneous prefetches: %d\n",
1552 SIMULTANEOUS_PREFETCHES);
1553 fprintf (dump_file, " prefetch latency: %d\n", PREFETCH_LATENCY);
1554 fprintf (dump_file, " prefetch block size: %d\n", PREFETCH_BLOCK);
1555 fprintf (dump_file, " L1 cache size: %d lines, %d kB\n",
1556 L1_CACHE_SIZE_BYTES / L1_CACHE_LINE_SIZE, L1_CACHE_SIZE);
1557 fprintf (dump_file, " L1 cache line size: %d\n", L1_CACHE_LINE_SIZE);
1558 fprintf (dump_file, " L2 cache size: %d kB\n", L2_CACHE_SIZE);
1559 fprintf (dump_file, "\n");
1562 initialize_original_copy_tables ();
1564 if (!built_in_decls[BUILT_IN_PREFETCH])
1566 tree type = build_function_type (void_type_node,
1567 tree_cons (NULL_TREE,
1568 const_ptr_type_node,
1569 NULL_TREE));
1570 tree decl = add_builtin_function ("__builtin_prefetch", type,
1571 BUILT_IN_PREFETCH, BUILT_IN_NORMAL,
1572 NULL, NULL_TREE);
1573 DECL_IS_NOVOPS (decl) = true;
1574 built_in_decls[BUILT_IN_PREFETCH] = decl;
1577 /* We assume that size of cache line is a power of two, so verify this
1578 here. */
1579 gcc_assert ((PREFETCH_BLOCK & (PREFETCH_BLOCK - 1)) == 0);
1581 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1583 if (dump_file && (dump_flags & TDF_DETAILS))
1584 fprintf (dump_file, "Processing loop %d:\n", loop->num);
1586 unrolled |= loop_prefetch_arrays (loop);
1588 if (dump_file && (dump_flags & TDF_DETAILS))
1589 fprintf (dump_file, "\n\n");
1592 if (unrolled)
1594 scev_reset ();
1595 todo_flags |= TODO_cleanup_cfg;
1598 free_original_copy_tables ();
1599 return todo_flags;