gcc/
[official-gcc.git] / gcc / tree-ssa-loop-prefetch.c
blob441e4a9d1f0c65f1749c78d8b0d496e11c4762c9
1 /* Array prefetching.
2 Copyright (C) 2005-2015 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 "alias.h"
25 #include "symtab.h"
26 #include "tree.h"
27 #include "fold-const.h"
28 #include "stor-layout.h"
29 #include "tm_p.h"
30 #include "predict.h"
31 #include "hard-reg-set.h"
32 #include "function.h"
33 #include "dominance.h"
34 #include "cfg.h"
35 #include "basic-block.h"
36 #include "tree-pretty-print.h"
37 #include "tree-ssa-alias.h"
38 #include "internal-fn.h"
39 #include "gimple-expr.h"
40 #include "gimple.h"
41 #include "gimplify.h"
42 #include "gimple-iterator.h"
43 #include "gimplify-me.h"
44 #include "gimple-ssa.h"
45 #include "tree-ssa-loop-ivopts.h"
46 #include "tree-ssa-loop-manip.h"
47 #include "tree-ssa-loop-niter.h"
48 #include "tree-ssa-loop.h"
49 #include "tree-into-ssa.h"
50 #include "cfgloop.h"
51 #include "tree-pass.h"
52 #include "insn-config.h"
53 #include "tree-chrec.h"
54 #include "tree-scalar-evolution.h"
55 #include "diagnostic-core.h"
56 #include "params.h"
57 #include "langhooks.h"
58 #include "tree-inline.h"
59 #include "tree-data-ref.h"
60 #include "target.h"
63 /* FIXME: Needed for optabs, but this should all be moved to a TBD interface
64 between the GIMPLE and RTL worlds. */
65 #include "rtl.h"
66 #include "flags.h"
67 #include "expmed.h"
68 #include "dojump.h"
69 #include "explow.h"
70 #include "calls.h"
71 #include "emit-rtl.h"
72 #include "varasm.h"
73 #include "stmt.h"
74 #include "expr.h"
75 #include "insn-codes.h"
76 #include "optabs.h"
77 #include "recog.h"
79 /* This pass inserts prefetch instructions to optimize cache usage during
80 accesses to arrays in loops. It processes loops sequentially and:
82 1) Gathers all memory references in the single loop.
83 2) For each of the references it decides when it is profitable to prefetch
84 it. To do it, we evaluate the reuse among the accesses, and determines
85 two values: PREFETCH_BEFORE (meaning that it only makes sense to do
86 prefetching in the first PREFETCH_BEFORE iterations of the loop) and
87 PREFETCH_MOD (meaning that it only makes sense to prefetch in the
88 iterations of the loop that are zero modulo PREFETCH_MOD). For example
89 (assuming cache line size is 64 bytes, char has size 1 byte and there
90 is no hardware sequential prefetch):
92 char *a;
93 for (i = 0; i < max; i++)
95 a[255] = ...; (0)
96 a[i] = ...; (1)
97 a[i + 64] = ...; (2)
98 a[16*i] = ...; (3)
99 a[187*i] = ...; (4)
100 a[187*i + 50] = ...; (5)
103 (0) obviously has PREFETCH_BEFORE 1
104 (1) has PREFETCH_BEFORE 64, since (2) accesses the same memory
105 location 64 iterations before it, and PREFETCH_MOD 64 (since
106 it hits the same cache line otherwise).
107 (2) has PREFETCH_MOD 64
108 (3) has PREFETCH_MOD 4
109 (4) has PREFETCH_MOD 1. We do not set PREFETCH_BEFORE here, since
110 the cache line accessed by (5) is the same with probability only
111 7/32.
112 (5) has PREFETCH_MOD 1 as well.
114 Additionally, we use data dependence analysis to determine for each
115 reference the distance till the first reuse; this information is used
116 to determine the temporality of the issued prefetch instruction.
118 3) We determine how much ahead we need to prefetch. The number of
119 iterations needed is time to fetch / time spent in one iteration of
120 the loop. The problem is that we do not know either of these values,
121 so we just make a heuristic guess based on a magic (possibly)
122 target-specific constant and size of the loop.
124 4) Determine which of the references we prefetch. We take into account
125 that there is a maximum number of simultaneous prefetches (provided
126 by machine description). We prefetch as many prefetches as possible
127 while still within this bound (starting with those with lowest
128 prefetch_mod, since they are responsible for most of the cache
129 misses).
131 5) We unroll and peel loops so that we are able to satisfy PREFETCH_MOD
132 and PREFETCH_BEFORE requirements (within some bounds), and to avoid
133 prefetching nonaccessed memory.
134 TODO -- actually implement peeling.
136 6) We actually emit the prefetch instructions. ??? Perhaps emit the
137 prefetch instructions with guards in cases where 5) was not sufficient
138 to satisfy the constraints?
140 A cost model is implemented to determine whether or not prefetching is
141 profitable for a given loop. The cost model has three heuristics:
143 1. Function trip_count_to_ahead_ratio_too_small_p implements a
144 heuristic that determines whether or not the loop has too few
145 iterations (compared to ahead). Prefetching is not likely to be
146 beneficial if the trip count to ahead ratio is below a certain
147 minimum.
149 2. Function mem_ref_count_reasonable_p implements a heuristic that
150 determines whether the given loop has enough CPU ops that can be
151 overlapped with cache missing memory ops. If not, the loop
152 won't benefit from prefetching. In the implementation,
153 prefetching is not considered beneficial if the ratio between
154 the instruction count and the mem ref count is below a certain
155 minimum.
157 3. Function insn_to_prefetch_ratio_too_small_p implements a
158 heuristic that disables prefetching in a loop if the prefetching
159 cost is above a certain limit. The relative prefetching cost is
160 estimated by taking the ratio between the prefetch count and the
161 total intruction count (this models the I-cache cost).
163 The limits used in these heuristics are defined as parameters with
164 reasonable default values. Machine-specific default values will be
165 added later.
167 Some other TODO:
168 -- write and use more general reuse analysis (that could be also used
169 in other cache aimed loop optimizations)
170 -- make it behave sanely together with the prefetches given by user
171 (now we just ignore them; at the very least we should avoid
172 optimizing loops in that user put his own prefetches)
173 -- we assume cache line size alignment of arrays; this could be
174 improved. */
176 /* Magic constants follow. These should be replaced by machine specific
177 numbers. */
179 /* True if write can be prefetched by a read prefetch. */
181 #ifndef WRITE_CAN_USE_READ_PREFETCH
182 #define WRITE_CAN_USE_READ_PREFETCH 1
183 #endif
185 /* True if read can be prefetched by a write prefetch. */
187 #ifndef READ_CAN_USE_WRITE_PREFETCH
188 #define READ_CAN_USE_WRITE_PREFETCH 0
189 #endif
191 /* The size of the block loaded by a single prefetch. Usually, this is
192 the same as cache line size (at the moment, we only consider one level
193 of cache hierarchy). */
195 #ifndef PREFETCH_BLOCK
196 #define PREFETCH_BLOCK L1_CACHE_LINE_SIZE
197 #endif
199 /* Do we have a forward hardware sequential prefetching? */
201 #ifndef HAVE_FORWARD_PREFETCH
202 #define HAVE_FORWARD_PREFETCH 0
203 #endif
205 /* Do we have a backward hardware sequential prefetching? */
207 #ifndef HAVE_BACKWARD_PREFETCH
208 #define HAVE_BACKWARD_PREFETCH 0
209 #endif
211 /* In some cases we are only able to determine that there is a certain
212 probability that the two accesses hit the same cache line. In this
213 case, we issue the prefetches for both of them if this probability
214 is less then (1000 - ACCEPTABLE_MISS_RATE) per thousand. */
216 #ifndef ACCEPTABLE_MISS_RATE
217 #define ACCEPTABLE_MISS_RATE 50
218 #endif
220 #define L1_CACHE_SIZE_BYTES ((unsigned) (L1_CACHE_SIZE * 1024))
221 #define L2_CACHE_SIZE_BYTES ((unsigned) (L2_CACHE_SIZE * 1024))
223 /* We consider a memory access nontemporal if it is not reused sooner than
224 after L2_CACHE_SIZE_BYTES of memory are accessed. However, we ignore
225 accesses closer than L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
226 so that we use nontemporal prefetches e.g. if single memory location
227 is accessed several times in a single iteration of the loop. */
228 #define NONTEMPORAL_FRACTION 16
230 /* In case we have to emit a memory fence instruction after the loop that
231 uses nontemporal stores, this defines the builtin to use. */
233 #ifndef FENCE_FOLLOWING_MOVNT
234 #define FENCE_FOLLOWING_MOVNT NULL_TREE
235 #endif
237 /* It is not profitable to prefetch when the trip count is not at
238 least TRIP_COUNT_TO_AHEAD_RATIO times the prefetch ahead distance.
239 For example, in a loop with a prefetch ahead distance of 10,
240 supposing that TRIP_COUNT_TO_AHEAD_RATIO is equal to 4, it is
241 profitable to prefetch when the trip count is greater or equal to
242 40. In that case, 30 out of the 40 iterations will benefit from
243 prefetching. */
245 #ifndef TRIP_COUNT_TO_AHEAD_RATIO
246 #define TRIP_COUNT_TO_AHEAD_RATIO 4
247 #endif
249 /* The group of references between that reuse may occur. */
251 struct mem_ref_group
253 tree base; /* Base of the reference. */
254 tree step; /* Step of the reference. */
255 struct mem_ref *refs; /* References in the group. */
256 struct mem_ref_group *next; /* Next group of references. */
259 /* Assigned to PREFETCH_BEFORE when all iterations are to be prefetched. */
261 #define PREFETCH_ALL (~(unsigned HOST_WIDE_INT) 0)
263 /* Do not generate a prefetch if the unroll factor is significantly less
264 than what is required by the prefetch. This is to avoid redundant
265 prefetches. For example, when prefetch_mod is 16 and unroll_factor is
266 2, prefetching requires unrolling the loop 16 times, but
267 the loop is actually unrolled twice. In this case (ratio = 8),
268 prefetching is not likely to be beneficial. */
270 #ifndef PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
271 #define PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO 4
272 #endif
274 /* Some of the prefetch computations have quadratic complexity. We want to
275 avoid huge compile times and, therefore, want to limit the amount of
276 memory references per loop where we consider prefetching. */
278 #ifndef PREFETCH_MAX_MEM_REFS_PER_LOOP
279 #define PREFETCH_MAX_MEM_REFS_PER_LOOP 200
280 #endif
282 /* The memory reference. */
284 struct mem_ref
286 gimple stmt; /* Statement in that the reference appears. */
287 tree mem; /* The reference. */
288 HOST_WIDE_INT delta; /* Constant offset of the reference. */
289 struct mem_ref_group *group; /* The group of references it belongs to. */
290 unsigned HOST_WIDE_INT prefetch_mod;
291 /* Prefetch only each PREFETCH_MOD-th
292 iteration. */
293 unsigned HOST_WIDE_INT prefetch_before;
294 /* Prefetch only first PREFETCH_BEFORE
295 iterations. */
296 unsigned reuse_distance; /* The amount of data accessed before the first
297 reuse of this value. */
298 struct mem_ref *next; /* The next reference in the group. */
299 unsigned write_p : 1; /* Is it a write? */
300 unsigned independent_p : 1; /* True if the reference is independent on
301 all other references inside the loop. */
302 unsigned issue_prefetch_p : 1; /* Should we really issue the prefetch? */
303 unsigned storent_p : 1; /* True if we changed the store to a
304 nontemporal one. */
307 /* Dumps information about memory reference */
308 static void
309 dump_mem_details (FILE *file, tree base, tree step,
310 HOST_WIDE_INT delta, bool write_p)
312 fprintf (file, "(base ");
313 print_generic_expr (file, base, TDF_SLIM);
314 fprintf (file, ", step ");
315 if (cst_and_fits_in_hwi (step))
316 fprintf (file, HOST_WIDE_INT_PRINT_DEC, int_cst_value (step));
317 else
318 print_generic_expr (file, step, TDF_TREE);
319 fprintf (file, ")\n");
320 fprintf (file, " delta ");
321 fprintf (file, HOST_WIDE_INT_PRINT_DEC, delta);
322 fprintf (file, "\n");
323 fprintf (file, " %s\n", write_p ? "write" : "read");
324 fprintf (file, "\n");
327 /* Dumps information about reference REF to FILE. */
329 static void
330 dump_mem_ref (FILE *file, struct mem_ref *ref)
332 fprintf (file, "Reference %p:\n", (void *) ref);
334 fprintf (file, " group %p ", (void *) ref->group);
336 dump_mem_details (file, ref->group->base, ref->group->step, ref->delta,
337 ref->write_p);
340 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
341 exist. */
343 static struct mem_ref_group *
344 find_or_create_group (struct mem_ref_group **groups, tree base, tree step)
346 struct mem_ref_group *group;
348 for (; *groups; groups = &(*groups)->next)
350 if (operand_equal_p ((*groups)->step, step, 0)
351 && operand_equal_p ((*groups)->base, base, 0))
352 return *groups;
354 /* If step is an integer constant, keep the list of groups sorted
355 by decreasing step. */
356 if (cst_and_fits_in_hwi ((*groups)->step) && cst_and_fits_in_hwi (step)
357 && int_cst_value ((*groups)->step) < int_cst_value (step))
358 break;
361 group = XNEW (struct mem_ref_group);
362 group->base = base;
363 group->step = step;
364 group->refs = NULL;
365 group->next = *groups;
366 *groups = group;
368 return group;
371 /* Records a memory reference MEM in GROUP with offset DELTA and write status
372 WRITE_P. The reference occurs in statement STMT. */
374 static void
375 record_ref (struct mem_ref_group *group, gimple stmt, tree mem,
376 HOST_WIDE_INT delta, bool write_p)
378 struct mem_ref **aref;
380 /* Do not record the same address twice. */
381 for (aref = &group->refs; *aref; aref = &(*aref)->next)
383 /* It does not have to be possible for write reference to reuse the read
384 prefetch, or vice versa. */
385 if (!WRITE_CAN_USE_READ_PREFETCH
386 && write_p
387 && !(*aref)->write_p)
388 continue;
389 if (!READ_CAN_USE_WRITE_PREFETCH
390 && !write_p
391 && (*aref)->write_p)
392 continue;
394 if ((*aref)->delta == delta)
395 return;
398 (*aref) = XNEW (struct mem_ref);
399 (*aref)->stmt = stmt;
400 (*aref)->mem = mem;
401 (*aref)->delta = delta;
402 (*aref)->write_p = write_p;
403 (*aref)->prefetch_before = PREFETCH_ALL;
404 (*aref)->prefetch_mod = 1;
405 (*aref)->reuse_distance = 0;
406 (*aref)->issue_prefetch_p = false;
407 (*aref)->group = group;
408 (*aref)->next = NULL;
409 (*aref)->independent_p = false;
410 (*aref)->storent_p = false;
412 if (dump_file && (dump_flags & TDF_DETAILS))
413 dump_mem_ref (dump_file, *aref);
416 /* Release memory references in GROUPS. */
418 static void
419 release_mem_refs (struct mem_ref_group *groups)
421 struct mem_ref_group *next_g;
422 struct mem_ref *ref, *next_r;
424 for (; groups; groups = next_g)
426 next_g = groups->next;
427 for (ref = groups->refs; ref; ref = next_r)
429 next_r = ref->next;
430 free (ref);
432 free (groups);
436 /* A structure used to pass arguments to idx_analyze_ref. */
438 struct ar_data
440 struct loop *loop; /* Loop of the reference. */
441 gimple stmt; /* Statement of the reference. */
442 tree *step; /* Step of the memory reference. */
443 HOST_WIDE_INT *delta; /* Offset of the memory reference. */
446 /* Analyzes a single INDEX of a memory reference to obtain information
447 described at analyze_ref. Callback for for_each_index. */
449 static bool
450 idx_analyze_ref (tree base, tree *index, void *data)
452 struct ar_data *ar_data = (struct ar_data *) data;
453 tree ibase, step, stepsize;
454 HOST_WIDE_INT idelta = 0, imult = 1;
455 affine_iv iv;
457 if (!simple_iv (ar_data->loop, loop_containing_stmt (ar_data->stmt),
458 *index, &iv, true))
459 return false;
460 ibase = iv.base;
461 step = iv.step;
463 if (TREE_CODE (ibase) == POINTER_PLUS_EXPR
464 && cst_and_fits_in_hwi (TREE_OPERAND (ibase, 1)))
466 idelta = int_cst_value (TREE_OPERAND (ibase, 1));
467 ibase = TREE_OPERAND (ibase, 0);
469 if (cst_and_fits_in_hwi (ibase))
471 idelta += int_cst_value (ibase);
472 ibase = build_int_cst (TREE_TYPE (ibase), 0);
475 if (TREE_CODE (base) == ARRAY_REF)
477 stepsize = array_ref_element_size (base);
478 if (!cst_and_fits_in_hwi (stepsize))
479 return false;
480 imult = int_cst_value (stepsize);
481 step = fold_build2 (MULT_EXPR, sizetype,
482 fold_convert (sizetype, step),
483 fold_convert (sizetype, stepsize));
484 idelta *= imult;
487 if (*ar_data->step == NULL_TREE)
488 *ar_data->step = step;
489 else
490 *ar_data->step = fold_build2 (PLUS_EXPR, sizetype,
491 fold_convert (sizetype, *ar_data->step),
492 fold_convert (sizetype, step));
493 *ar_data->delta += idelta;
494 *index = ibase;
496 return true;
499 /* Tries to express REF_P in shape &BASE + STEP * iter + DELTA, where DELTA and
500 STEP are integer constants and iter is number of iterations of LOOP. The
501 reference occurs in statement STMT. Strips nonaddressable component
502 references from REF_P. */
504 static bool
505 analyze_ref (struct loop *loop, tree *ref_p, tree *base,
506 tree *step, HOST_WIDE_INT *delta,
507 gimple stmt)
509 struct ar_data ar_data;
510 tree off;
511 HOST_WIDE_INT bit_offset;
512 tree ref = *ref_p;
514 *step = NULL_TREE;
515 *delta = 0;
517 /* First strip off the component references. Ignore bitfields.
518 Also strip off the real and imagine parts of a complex, so that
519 they can have the same base. */
520 if (TREE_CODE (ref) == REALPART_EXPR
521 || TREE_CODE (ref) == IMAGPART_EXPR
522 || (TREE_CODE (ref) == COMPONENT_REF
523 && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref, 1))))
525 if (TREE_CODE (ref) == IMAGPART_EXPR)
526 *delta += int_size_in_bytes (TREE_TYPE (ref));
527 ref = TREE_OPERAND (ref, 0);
530 *ref_p = ref;
532 for (; TREE_CODE (ref) == COMPONENT_REF; ref = TREE_OPERAND (ref, 0))
534 off = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1));
535 bit_offset = TREE_INT_CST_LOW (off);
536 gcc_assert (bit_offset % BITS_PER_UNIT == 0);
538 *delta += bit_offset / BITS_PER_UNIT;
541 *base = unshare_expr (ref);
542 ar_data.loop = loop;
543 ar_data.stmt = stmt;
544 ar_data.step = step;
545 ar_data.delta = delta;
546 return for_each_index (base, idx_analyze_ref, &ar_data);
549 /* Record a memory reference REF to the list REFS. The reference occurs in
550 LOOP in statement STMT and it is write if WRITE_P. Returns true if the
551 reference was recorded, false otherwise. */
553 static bool
554 gather_memory_references_ref (struct loop *loop, struct mem_ref_group **refs,
555 tree ref, bool write_p, gimple stmt)
557 tree base, step;
558 HOST_WIDE_INT delta;
559 struct mem_ref_group *agrp;
561 if (get_base_address (ref) == NULL)
562 return false;
564 if (!analyze_ref (loop, &ref, &base, &step, &delta, stmt))
565 return false;
566 /* If analyze_ref fails the default is a NULL_TREE. We can stop here. */
567 if (step == NULL_TREE)
568 return false;
570 /* Stop if the address of BASE could not be taken. */
571 if (may_be_nonaddressable_p (base))
572 return false;
574 /* Limit non-constant step prefetching only to the innermost loops and
575 only when the step is loop invariant in the entire loop nest. */
576 if (!cst_and_fits_in_hwi (step))
578 if (loop->inner != NULL)
580 if (dump_file && (dump_flags & TDF_DETAILS))
582 fprintf (dump_file, "Memory expression %p\n",(void *) ref );
583 print_generic_expr (dump_file, ref, TDF_TREE);
584 fprintf (dump_file,":");
585 dump_mem_details (dump_file, base, step, delta, write_p);
586 fprintf (dump_file,
587 "Ignoring %p, non-constant step prefetching is "
588 "limited to inner most loops \n",
589 (void *) ref);
591 return false;
593 else
595 if (!expr_invariant_in_loop_p (loop_outermost (loop), step))
597 if (dump_file && (dump_flags & TDF_DETAILS))
599 fprintf (dump_file, "Memory expression %p\n",(void *) ref );
600 print_generic_expr (dump_file, ref, TDF_TREE);
601 fprintf (dump_file,":");
602 dump_mem_details (dump_file, base, step, delta, write_p);
603 fprintf (dump_file,
604 "Not prefetching, ignoring %p due to "
605 "loop variant step\n",
606 (void *) ref);
608 return false;
613 /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
614 are integer constants. */
615 agrp = find_or_create_group (refs, base, step);
616 record_ref (agrp, stmt, ref, delta, write_p);
618 return true;
621 /* Record the suitable memory references in LOOP. NO_OTHER_REFS is set to
622 true if there are no other memory references inside the loop. */
624 static struct mem_ref_group *
625 gather_memory_references (struct loop *loop, bool *no_other_refs, unsigned *ref_count)
627 basic_block *body = get_loop_body_in_dom_order (loop);
628 basic_block bb;
629 unsigned i;
630 gimple_stmt_iterator bsi;
631 gimple stmt;
632 tree lhs, rhs;
633 struct mem_ref_group *refs = NULL;
635 *no_other_refs = true;
636 *ref_count = 0;
638 /* Scan the loop body in order, so that the former references precede the
639 later ones. */
640 for (i = 0; i < loop->num_nodes; i++)
642 bb = body[i];
643 if (bb->loop_father != loop)
644 continue;
646 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
648 stmt = gsi_stmt (bsi);
650 if (gimple_code (stmt) != GIMPLE_ASSIGN)
652 if (gimple_vuse (stmt)
653 || (is_gimple_call (stmt)
654 && !(gimple_call_flags (stmt) & ECF_CONST)))
655 *no_other_refs = false;
656 continue;
659 lhs = gimple_assign_lhs (stmt);
660 rhs = gimple_assign_rhs1 (stmt);
662 if (REFERENCE_CLASS_P (rhs))
664 *no_other_refs &= gather_memory_references_ref (loop, &refs,
665 rhs, false, stmt);
666 *ref_count += 1;
668 if (REFERENCE_CLASS_P (lhs))
670 *no_other_refs &= gather_memory_references_ref (loop, &refs,
671 lhs, true, stmt);
672 *ref_count += 1;
676 free (body);
678 return refs;
681 /* Prune the prefetch candidate REF using the self-reuse. */
683 static void
684 prune_ref_by_self_reuse (struct mem_ref *ref)
686 HOST_WIDE_INT step;
687 bool backward;
689 /* If the step size is non constant, we cannot calculate prefetch_mod. */
690 if (!cst_and_fits_in_hwi (ref->group->step))
691 return;
693 step = int_cst_value (ref->group->step);
695 backward = step < 0;
697 if (step == 0)
699 /* Prefetch references to invariant address just once. */
700 ref->prefetch_before = 1;
701 return;
704 if (backward)
705 step = -step;
707 if (step > PREFETCH_BLOCK)
708 return;
710 if ((backward && HAVE_BACKWARD_PREFETCH)
711 || (!backward && HAVE_FORWARD_PREFETCH))
713 ref->prefetch_before = 1;
714 return;
717 ref->prefetch_mod = PREFETCH_BLOCK / step;
720 /* Divides X by BY, rounding down. */
722 static HOST_WIDE_INT
723 ddown (HOST_WIDE_INT x, unsigned HOST_WIDE_INT by)
725 gcc_assert (by > 0);
727 if (x >= 0)
728 return x / by;
729 else
730 return (x + by - 1) / by;
733 /* Given a CACHE_LINE_SIZE and two inductive memory references
734 with a common STEP greater than CACHE_LINE_SIZE and an address
735 difference DELTA, compute the probability that they will fall
736 in different cache lines. Return true if the computed miss rate
737 is not greater than the ACCEPTABLE_MISS_RATE. DISTINCT_ITERS is the
738 number of distinct iterations after which the pattern repeats itself.
739 ALIGN_UNIT is the unit of alignment in bytes. */
741 static bool
742 is_miss_rate_acceptable (unsigned HOST_WIDE_INT cache_line_size,
743 HOST_WIDE_INT step, HOST_WIDE_INT delta,
744 unsigned HOST_WIDE_INT distinct_iters,
745 int align_unit)
747 unsigned align, iter;
748 int total_positions, miss_positions, max_allowed_miss_positions;
749 int address1, address2, cache_line1, cache_line2;
751 /* It always misses if delta is greater than or equal to the cache
752 line size. */
753 if (delta >= (HOST_WIDE_INT) cache_line_size)
754 return false;
756 miss_positions = 0;
757 total_positions = (cache_line_size / align_unit) * distinct_iters;
758 max_allowed_miss_positions = (ACCEPTABLE_MISS_RATE * total_positions) / 1000;
760 /* Iterate through all possible alignments of the first
761 memory reference within its cache line. */
762 for (align = 0; align < cache_line_size; align += align_unit)
764 /* Iterate through all distinct iterations. */
765 for (iter = 0; iter < distinct_iters; iter++)
767 address1 = align + step * iter;
768 address2 = address1 + delta;
769 cache_line1 = address1 / cache_line_size;
770 cache_line2 = address2 / cache_line_size;
771 if (cache_line1 != cache_line2)
773 miss_positions += 1;
774 if (miss_positions > max_allowed_miss_positions)
775 return false;
778 return true;
781 /* Prune the prefetch candidate REF using the reuse with BY.
782 If BY_IS_BEFORE is true, BY is before REF in the loop. */
784 static void
785 prune_ref_by_group_reuse (struct mem_ref *ref, struct mem_ref *by,
786 bool by_is_before)
788 HOST_WIDE_INT step;
789 bool backward;
790 HOST_WIDE_INT delta_r = ref->delta, delta_b = by->delta;
791 HOST_WIDE_INT delta = delta_b - delta_r;
792 HOST_WIDE_INT hit_from;
793 unsigned HOST_WIDE_INT prefetch_before, prefetch_block;
794 HOST_WIDE_INT reduced_step;
795 unsigned HOST_WIDE_INT reduced_prefetch_block;
796 tree ref_type;
797 int align_unit;
799 /* If the step is non constant we cannot calculate prefetch_before. */
800 if (!cst_and_fits_in_hwi (ref->group->step)) {
801 return;
804 step = int_cst_value (ref->group->step);
806 backward = step < 0;
809 if (delta == 0)
811 /* If the references has the same address, only prefetch the
812 former. */
813 if (by_is_before)
814 ref->prefetch_before = 0;
816 return;
819 if (!step)
821 /* If the reference addresses are invariant and fall into the
822 same cache line, prefetch just the first one. */
823 if (!by_is_before)
824 return;
826 if (ddown (ref->delta, PREFETCH_BLOCK)
827 != ddown (by->delta, PREFETCH_BLOCK))
828 return;
830 ref->prefetch_before = 0;
831 return;
834 /* Only prune the reference that is behind in the array. */
835 if (backward)
837 if (delta > 0)
838 return;
840 /* Transform the data so that we may assume that the accesses
841 are forward. */
842 delta = - delta;
843 step = -step;
844 delta_r = PREFETCH_BLOCK - 1 - delta_r;
845 delta_b = PREFETCH_BLOCK - 1 - delta_b;
847 else
849 if (delta < 0)
850 return;
853 /* Check whether the two references are likely to hit the same cache
854 line, and how distant the iterations in that it occurs are from
855 each other. */
857 if (step <= PREFETCH_BLOCK)
859 /* The accesses are sure to meet. Let us check when. */
860 hit_from = ddown (delta_b, PREFETCH_BLOCK) * PREFETCH_BLOCK;
861 prefetch_before = (hit_from - delta_r + step - 1) / step;
863 /* Do not reduce prefetch_before if we meet beyond cache size. */
864 if (prefetch_before > absu_hwi (L2_CACHE_SIZE_BYTES / step))
865 prefetch_before = PREFETCH_ALL;
866 if (prefetch_before < ref->prefetch_before)
867 ref->prefetch_before = prefetch_before;
869 return;
872 /* A more complicated case with step > prefetch_block. First reduce
873 the ratio between the step and the cache line size to its simplest
874 terms. The resulting denominator will then represent the number of
875 distinct iterations after which each address will go back to its
876 initial location within the cache line. This computation assumes
877 that PREFETCH_BLOCK is a power of two. */
878 prefetch_block = PREFETCH_BLOCK;
879 reduced_prefetch_block = prefetch_block;
880 reduced_step = step;
881 while ((reduced_step & 1) == 0
882 && reduced_prefetch_block > 1)
884 reduced_step >>= 1;
885 reduced_prefetch_block >>= 1;
888 prefetch_before = delta / step;
889 delta %= step;
890 ref_type = TREE_TYPE (ref->mem);
891 align_unit = TYPE_ALIGN (ref_type) / 8;
892 if (is_miss_rate_acceptable (prefetch_block, step, delta,
893 reduced_prefetch_block, align_unit))
895 /* Do not reduce prefetch_before if we meet beyond cache size. */
896 if (prefetch_before > L2_CACHE_SIZE_BYTES / PREFETCH_BLOCK)
897 prefetch_before = PREFETCH_ALL;
898 if (prefetch_before < ref->prefetch_before)
899 ref->prefetch_before = prefetch_before;
901 return;
904 /* Try also the following iteration. */
905 prefetch_before++;
906 delta = step - delta;
907 if (is_miss_rate_acceptable (prefetch_block, step, delta,
908 reduced_prefetch_block, align_unit))
910 if (prefetch_before < ref->prefetch_before)
911 ref->prefetch_before = prefetch_before;
913 return;
916 /* The ref probably does not reuse by. */
917 return;
920 /* Prune the prefetch candidate REF using the reuses with other references
921 in REFS. */
923 static void
924 prune_ref_by_reuse (struct mem_ref *ref, struct mem_ref *refs)
926 struct mem_ref *prune_by;
927 bool before = true;
929 prune_ref_by_self_reuse (ref);
931 for (prune_by = refs; prune_by; prune_by = prune_by->next)
933 if (prune_by == ref)
935 before = false;
936 continue;
939 if (!WRITE_CAN_USE_READ_PREFETCH
940 && ref->write_p
941 && !prune_by->write_p)
942 continue;
943 if (!READ_CAN_USE_WRITE_PREFETCH
944 && !ref->write_p
945 && prune_by->write_p)
946 continue;
948 prune_ref_by_group_reuse (ref, prune_by, before);
952 /* Prune the prefetch candidates in GROUP using the reuse analysis. */
954 static void
955 prune_group_by_reuse (struct mem_ref_group *group)
957 struct mem_ref *ref_pruned;
959 for (ref_pruned = group->refs; ref_pruned; ref_pruned = ref_pruned->next)
961 prune_ref_by_reuse (ref_pruned, group->refs);
963 if (dump_file && (dump_flags & TDF_DETAILS))
965 fprintf (dump_file, "Reference %p:", (void *) ref_pruned);
967 if (ref_pruned->prefetch_before == PREFETCH_ALL
968 && ref_pruned->prefetch_mod == 1)
969 fprintf (dump_file, " no restrictions");
970 else if (ref_pruned->prefetch_before == 0)
971 fprintf (dump_file, " do not prefetch");
972 else if (ref_pruned->prefetch_before <= ref_pruned->prefetch_mod)
973 fprintf (dump_file, " prefetch once");
974 else
976 if (ref_pruned->prefetch_before != PREFETCH_ALL)
978 fprintf (dump_file, " prefetch before ");
979 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC,
980 ref_pruned->prefetch_before);
982 if (ref_pruned->prefetch_mod != 1)
984 fprintf (dump_file, " prefetch mod ");
985 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC,
986 ref_pruned->prefetch_mod);
989 fprintf (dump_file, "\n");
994 /* Prune the list of prefetch candidates GROUPS using the reuse analysis. */
996 static void
997 prune_by_reuse (struct mem_ref_group *groups)
999 for (; groups; groups = groups->next)
1000 prune_group_by_reuse (groups);
1003 /* Returns true if we should issue prefetch for REF. */
1005 static bool
1006 should_issue_prefetch_p (struct mem_ref *ref)
1008 /* For now do not issue prefetches for only first few of the
1009 iterations. */
1010 if (ref->prefetch_before != PREFETCH_ALL)
1012 if (dump_file && (dump_flags & TDF_DETAILS))
1013 fprintf (dump_file, "Ignoring %p due to prefetch_before\n",
1014 (void *) ref);
1015 return false;
1018 /* Do not prefetch nontemporal stores. */
1019 if (ref->storent_p)
1021 if (dump_file && (dump_flags & TDF_DETAILS))
1022 fprintf (dump_file, "Ignoring nontemporal store %p\n", (void *) ref);
1023 return false;
1026 return true;
1029 /* Decide which of the prefetch candidates in GROUPS to prefetch.
1030 AHEAD is the number of iterations to prefetch ahead (which corresponds
1031 to the number of simultaneous instances of one prefetch running at a
1032 time). UNROLL_FACTOR is the factor by that the loop is going to be
1033 unrolled. Returns true if there is anything to prefetch. */
1035 static bool
1036 schedule_prefetches (struct mem_ref_group *groups, unsigned unroll_factor,
1037 unsigned ahead)
1039 unsigned remaining_prefetch_slots, n_prefetches, prefetch_slots;
1040 unsigned slots_per_prefetch;
1041 struct mem_ref *ref;
1042 bool any = false;
1044 /* At most SIMULTANEOUS_PREFETCHES should be running at the same time. */
1045 remaining_prefetch_slots = SIMULTANEOUS_PREFETCHES;
1047 /* The prefetch will run for AHEAD iterations of the original loop, i.e.,
1048 AHEAD / UNROLL_FACTOR iterations of the unrolled loop. In each iteration,
1049 it will need a prefetch slot. */
1050 slots_per_prefetch = (ahead + unroll_factor / 2) / unroll_factor;
1051 if (dump_file && (dump_flags & TDF_DETAILS))
1052 fprintf (dump_file, "Each prefetch instruction takes %u prefetch slots.\n",
1053 slots_per_prefetch);
1055 /* For now we just take memory references one by one and issue
1056 prefetches for as many as possible. The groups are sorted
1057 starting with the largest step, since the references with
1058 large step are more likely to cause many cache misses. */
1060 for (; groups; groups = groups->next)
1061 for (ref = groups->refs; ref; ref = ref->next)
1063 if (!should_issue_prefetch_p (ref))
1064 continue;
1066 /* The loop is far from being sufficiently unrolled for this
1067 prefetch. Do not generate prefetch to avoid many redudant
1068 prefetches. */
1069 if (ref->prefetch_mod / unroll_factor > PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO)
1070 continue;
1072 /* If we need to prefetch the reference each PREFETCH_MOD iterations,
1073 and we unroll the loop UNROLL_FACTOR times, we need to insert
1074 ceil (UNROLL_FACTOR / PREFETCH_MOD) instructions in each
1075 iteration. */
1076 n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
1077 / ref->prefetch_mod);
1078 prefetch_slots = n_prefetches * slots_per_prefetch;
1080 /* If more than half of the prefetches would be lost anyway, do not
1081 issue the prefetch. */
1082 if (2 * remaining_prefetch_slots < prefetch_slots)
1083 continue;
1085 ref->issue_prefetch_p = true;
1087 if (remaining_prefetch_slots <= prefetch_slots)
1088 return true;
1089 remaining_prefetch_slots -= prefetch_slots;
1090 any = true;
1093 return any;
1096 /* Return TRUE if no prefetch is going to be generated in the given
1097 GROUPS. */
1099 static bool
1100 nothing_to_prefetch_p (struct mem_ref_group *groups)
1102 struct mem_ref *ref;
1104 for (; groups; groups = groups->next)
1105 for (ref = groups->refs; ref; ref = ref->next)
1106 if (should_issue_prefetch_p (ref))
1107 return false;
1109 return true;
1112 /* Estimate the number of prefetches in the given GROUPS.
1113 UNROLL_FACTOR is the factor by which LOOP was unrolled. */
1115 static int
1116 estimate_prefetch_count (struct mem_ref_group *groups, unsigned unroll_factor)
1118 struct mem_ref *ref;
1119 unsigned n_prefetches;
1120 int prefetch_count = 0;
1122 for (; groups; groups = groups->next)
1123 for (ref = groups->refs; ref; ref = ref->next)
1124 if (should_issue_prefetch_p (ref))
1126 n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
1127 / ref->prefetch_mod);
1128 prefetch_count += n_prefetches;
1131 return prefetch_count;
1134 /* Issue prefetches for the reference REF into loop as decided before.
1135 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR
1136 is the factor by which LOOP was unrolled. */
1138 static void
1139 issue_prefetch_ref (struct mem_ref *ref, unsigned unroll_factor, unsigned ahead)
1141 HOST_WIDE_INT delta;
1142 tree addr, addr_base, write_p, local, forward;
1143 gcall *prefetch;
1144 gimple_stmt_iterator bsi;
1145 unsigned n_prefetches, ap;
1146 bool nontemporal = ref->reuse_distance >= L2_CACHE_SIZE_BYTES;
1148 if (dump_file && (dump_flags & TDF_DETAILS))
1149 fprintf (dump_file, "Issued%s prefetch for %p.\n",
1150 nontemporal ? " nontemporal" : "",
1151 (void *) ref);
1153 bsi = gsi_for_stmt (ref->stmt);
1155 n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
1156 / ref->prefetch_mod);
1157 addr_base = build_fold_addr_expr_with_type (ref->mem, ptr_type_node);
1158 addr_base = force_gimple_operand_gsi (&bsi, unshare_expr (addr_base),
1159 true, NULL, true, GSI_SAME_STMT);
1160 write_p = ref->write_p ? integer_one_node : integer_zero_node;
1161 local = nontemporal ? integer_zero_node : integer_three_node;
1163 for (ap = 0; ap < n_prefetches; ap++)
1165 if (cst_and_fits_in_hwi (ref->group->step))
1167 /* Determine the address to prefetch. */
1168 delta = (ahead + ap * ref->prefetch_mod) *
1169 int_cst_value (ref->group->step);
1170 addr = fold_build_pointer_plus_hwi (addr_base, delta);
1171 addr = force_gimple_operand_gsi (&bsi, unshare_expr (addr), true, NULL,
1172 true, GSI_SAME_STMT);
1174 else
1176 /* The step size is non-constant but loop-invariant. We use the
1177 heuristic to simply prefetch ahead iterations ahead. */
1178 forward = fold_build2 (MULT_EXPR, sizetype,
1179 fold_convert (sizetype, ref->group->step),
1180 fold_convert (sizetype, size_int (ahead)));
1181 addr = fold_build_pointer_plus (addr_base, forward);
1182 addr = force_gimple_operand_gsi (&bsi, unshare_expr (addr), true,
1183 NULL, true, GSI_SAME_STMT);
1185 /* Create the prefetch instruction. */
1186 prefetch = gimple_build_call (builtin_decl_explicit (BUILT_IN_PREFETCH),
1187 3, addr, write_p, local);
1188 gsi_insert_before (&bsi, prefetch, GSI_SAME_STMT);
1192 /* Issue prefetches for the references in GROUPS into loop as decided before.
1193 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR is the
1194 factor by that LOOP was unrolled. */
1196 static void
1197 issue_prefetches (struct mem_ref_group *groups,
1198 unsigned unroll_factor, unsigned ahead)
1200 struct mem_ref *ref;
1202 for (; groups; groups = groups->next)
1203 for (ref = groups->refs; ref; ref = ref->next)
1204 if (ref->issue_prefetch_p)
1205 issue_prefetch_ref (ref, unroll_factor, ahead);
1208 /* Returns true if REF is a memory write for that a nontemporal store insn
1209 can be used. */
1211 static bool
1212 nontemporal_store_p (struct mem_ref *ref)
1214 machine_mode mode;
1215 enum insn_code code;
1217 /* REF must be a write that is not reused. We require it to be independent
1218 on all other memory references in the loop, as the nontemporal stores may
1219 be reordered with respect to other memory references. */
1220 if (!ref->write_p
1221 || !ref->independent_p
1222 || ref->reuse_distance < L2_CACHE_SIZE_BYTES)
1223 return false;
1225 /* Check that we have the storent instruction for the mode. */
1226 mode = TYPE_MODE (TREE_TYPE (ref->mem));
1227 if (mode == BLKmode)
1228 return false;
1230 code = optab_handler (storent_optab, mode);
1231 return code != CODE_FOR_nothing;
1234 /* If REF is a nontemporal store, we mark the corresponding modify statement
1235 and return true. Otherwise, we return false. */
1237 static bool
1238 mark_nontemporal_store (struct mem_ref *ref)
1240 if (!nontemporal_store_p (ref))
1241 return false;
1243 if (dump_file && (dump_flags & TDF_DETAILS))
1244 fprintf (dump_file, "Marked reference %p as a nontemporal store.\n",
1245 (void *) ref);
1247 gimple_assign_set_nontemporal_move (ref->stmt, true);
1248 ref->storent_p = true;
1250 return true;
1253 /* Issue a memory fence instruction after LOOP. */
1255 static void
1256 emit_mfence_after_loop (struct loop *loop)
1258 vec<edge> exits = get_loop_exit_edges (loop);
1259 edge exit;
1260 gcall *call;
1261 gimple_stmt_iterator bsi;
1262 unsigned i;
1264 FOR_EACH_VEC_ELT (exits, i, exit)
1266 call = gimple_build_call (FENCE_FOLLOWING_MOVNT, 0);
1268 if (!single_pred_p (exit->dest)
1269 /* If possible, we prefer not to insert the fence on other paths
1270 in cfg. */
1271 && !(exit->flags & EDGE_ABNORMAL))
1272 split_loop_exit_edge (exit);
1273 bsi = gsi_after_labels (exit->dest);
1275 gsi_insert_before (&bsi, call, GSI_NEW_STMT);
1278 exits.release ();
1279 update_ssa (TODO_update_ssa_only_virtuals);
1282 /* Returns true if we can use storent in loop, false otherwise. */
1284 static bool
1285 may_use_storent_in_loop_p (struct loop *loop)
1287 bool ret = true;
1289 if (loop->inner != NULL)
1290 return false;
1292 /* If we must issue a mfence insn after using storent, check that there
1293 is a suitable place for it at each of the loop exits. */
1294 if (FENCE_FOLLOWING_MOVNT != NULL_TREE)
1296 vec<edge> exits = get_loop_exit_edges (loop);
1297 unsigned i;
1298 edge exit;
1300 FOR_EACH_VEC_ELT (exits, i, exit)
1301 if ((exit->flags & EDGE_ABNORMAL)
1302 && exit->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1303 ret = false;
1305 exits.release ();
1308 return ret;
1311 /* Marks nontemporal stores in LOOP. GROUPS contains the description of memory
1312 references in the loop. */
1314 static void
1315 mark_nontemporal_stores (struct loop *loop, struct mem_ref_group *groups)
1317 struct mem_ref *ref;
1318 bool any = false;
1320 if (!may_use_storent_in_loop_p (loop))
1321 return;
1323 for (; groups; groups = groups->next)
1324 for (ref = groups->refs; ref; ref = ref->next)
1325 any |= mark_nontemporal_store (ref);
1327 if (any && FENCE_FOLLOWING_MOVNT != NULL_TREE)
1328 emit_mfence_after_loop (loop);
1331 /* Determines whether we can profitably unroll LOOP FACTOR times, and if
1332 this is the case, fill in DESC by the description of number of
1333 iterations. */
1335 static bool
1336 should_unroll_loop_p (struct loop *loop, struct tree_niter_desc *desc,
1337 unsigned factor)
1339 if (!can_unroll_loop_p (loop, factor, desc))
1340 return false;
1342 /* We only consider loops without control flow for unrolling. This is not
1343 a hard restriction -- tree_unroll_loop works with arbitrary loops
1344 as well; but the unrolling/prefetching is usually more profitable for
1345 loops consisting of a single basic block, and we want to limit the
1346 code growth. */
1347 if (loop->num_nodes > 2)
1348 return false;
1350 return true;
1353 /* Determine the coefficient by that unroll LOOP, from the information
1354 contained in the list of memory references REFS. Description of
1355 umber of iterations of LOOP is stored to DESC. NINSNS is the number of
1356 insns of the LOOP. EST_NITER is the estimated number of iterations of
1357 the loop, or -1 if no estimate is available. */
1359 static unsigned
1360 determine_unroll_factor (struct loop *loop, struct mem_ref_group *refs,
1361 unsigned ninsns, struct tree_niter_desc *desc,
1362 HOST_WIDE_INT est_niter)
1364 unsigned upper_bound;
1365 unsigned nfactor, factor, mod_constraint;
1366 struct mem_ref_group *agp;
1367 struct mem_ref *ref;
1369 /* First check whether the loop is not too large to unroll. We ignore
1370 PARAM_MAX_UNROLL_TIMES, because for small loops, it prevented us
1371 from unrolling them enough to make exactly one cache line covered by each
1372 iteration. Also, the goal of PARAM_MAX_UNROLL_TIMES is to prevent
1373 us from unrolling the loops too many times in cases where we only expect
1374 gains from better scheduling and decreasing loop overhead, which is not
1375 the case here. */
1376 upper_bound = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / ninsns;
1378 /* If we unrolled the loop more times than it iterates, the unrolled version
1379 of the loop would be never entered. */
1380 if (est_niter >= 0 && est_niter < (HOST_WIDE_INT) upper_bound)
1381 upper_bound = est_niter;
1383 if (upper_bound <= 1)
1384 return 1;
1386 /* Choose the factor so that we may prefetch each cache just once,
1387 but bound the unrolling by UPPER_BOUND. */
1388 factor = 1;
1389 for (agp = refs; agp; agp = agp->next)
1390 for (ref = agp->refs; ref; ref = ref->next)
1391 if (should_issue_prefetch_p (ref))
1393 mod_constraint = ref->prefetch_mod;
1394 nfactor = least_common_multiple (mod_constraint, factor);
1395 if (nfactor <= upper_bound)
1396 factor = nfactor;
1399 if (!should_unroll_loop_p (loop, desc, factor))
1400 return 1;
1402 return factor;
1405 /* Returns the total volume of the memory references REFS, taking into account
1406 reuses in the innermost loop and cache line size. TODO -- we should also
1407 take into account reuses across the iterations of the loops in the loop
1408 nest. */
1410 static unsigned
1411 volume_of_references (struct mem_ref_group *refs)
1413 unsigned volume = 0;
1414 struct mem_ref_group *gr;
1415 struct mem_ref *ref;
1417 for (gr = refs; gr; gr = gr->next)
1418 for (ref = gr->refs; ref; ref = ref->next)
1420 /* Almost always reuses another value? */
1421 if (ref->prefetch_before != PREFETCH_ALL)
1422 continue;
1424 /* If several iterations access the same cache line, use the size of
1425 the line divided by this number. Otherwise, a cache line is
1426 accessed in each iteration. TODO -- in the latter case, we should
1427 take the size of the reference into account, rounding it up on cache
1428 line size multiple. */
1429 volume += L1_CACHE_LINE_SIZE / ref->prefetch_mod;
1431 return volume;
1434 /* Returns the volume of memory references accessed across VEC iterations of
1435 loops, whose sizes are described in the LOOP_SIZES array. N is the number
1436 of the loops in the nest (length of VEC and LOOP_SIZES vectors). */
1438 static unsigned
1439 volume_of_dist_vector (lambda_vector vec, unsigned *loop_sizes, unsigned n)
1441 unsigned i;
1443 for (i = 0; i < n; i++)
1444 if (vec[i] != 0)
1445 break;
1447 if (i == n)
1448 return 0;
1450 gcc_assert (vec[i] > 0);
1452 /* We ignore the parts of the distance vector in subloops, since usually
1453 the numbers of iterations are much smaller. */
1454 return loop_sizes[i] * vec[i];
1457 /* Add the steps of ACCESS_FN multiplied by STRIDE to the array STRIDE
1458 at the position corresponding to the loop of the step. N is the depth
1459 of the considered loop nest, and, LOOP is its innermost loop. */
1461 static void
1462 add_subscript_strides (tree access_fn, unsigned stride,
1463 HOST_WIDE_INT *strides, unsigned n, struct loop *loop)
1465 struct loop *aloop;
1466 tree step;
1467 HOST_WIDE_INT astep;
1468 unsigned min_depth = loop_depth (loop) - n;
1470 while (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
1472 aloop = get_chrec_loop (access_fn);
1473 step = CHREC_RIGHT (access_fn);
1474 access_fn = CHREC_LEFT (access_fn);
1476 if ((unsigned) loop_depth (aloop) <= min_depth)
1477 continue;
1479 if (tree_fits_shwi_p (step))
1480 astep = tree_to_shwi (step);
1481 else
1482 astep = L1_CACHE_LINE_SIZE;
1484 strides[n - 1 - loop_depth (loop) + loop_depth (aloop)] += astep * stride;
1489 /* Returns the volume of memory references accessed between two consecutive
1490 self-reuses of the reference DR. We consider the subscripts of DR in N
1491 loops, and LOOP_SIZES contains the volumes of accesses in each of the
1492 loops. LOOP is the innermost loop of the current loop nest. */
1494 static unsigned
1495 self_reuse_distance (data_reference_p dr, unsigned *loop_sizes, unsigned n,
1496 struct loop *loop)
1498 tree stride, access_fn;
1499 HOST_WIDE_INT *strides, astride;
1500 vec<tree> access_fns;
1501 tree ref = DR_REF (dr);
1502 unsigned i, ret = ~0u;
1504 /* In the following example:
1506 for (i = 0; i < N; i++)
1507 for (j = 0; j < N; j++)
1508 use (a[j][i]);
1509 the same cache line is accessed each N steps (except if the change from
1510 i to i + 1 crosses the boundary of the cache line). Thus, for self-reuse,
1511 we cannot rely purely on the results of the data dependence analysis.
1513 Instead, we compute the stride of the reference in each loop, and consider
1514 the innermost loop in that the stride is less than cache size. */
1516 strides = XCNEWVEC (HOST_WIDE_INT, n);
1517 access_fns = DR_ACCESS_FNS (dr);
1519 FOR_EACH_VEC_ELT (access_fns, i, access_fn)
1521 /* Keep track of the reference corresponding to the subscript, so that we
1522 know its stride. */
1523 while (handled_component_p (ref) && TREE_CODE (ref) != ARRAY_REF)
1524 ref = TREE_OPERAND (ref, 0);
1526 if (TREE_CODE (ref) == ARRAY_REF)
1528 stride = TYPE_SIZE_UNIT (TREE_TYPE (ref));
1529 if (tree_fits_uhwi_p (stride))
1530 astride = tree_to_uhwi (stride);
1531 else
1532 astride = L1_CACHE_LINE_SIZE;
1534 ref = TREE_OPERAND (ref, 0);
1536 else
1537 astride = 1;
1539 add_subscript_strides (access_fn, astride, strides, n, loop);
1542 for (i = n; i-- > 0; )
1544 unsigned HOST_WIDE_INT s;
1546 s = strides[i] < 0 ? -strides[i] : strides[i];
1548 if (s < (unsigned) L1_CACHE_LINE_SIZE
1549 && (loop_sizes[i]
1550 > (unsigned) (L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION)))
1552 ret = loop_sizes[i];
1553 break;
1557 free (strides);
1558 return ret;
1561 /* Determines the distance till the first reuse of each reference in REFS
1562 in the loop nest of LOOP. NO_OTHER_REFS is true if there are no other
1563 memory references in the loop. Return false if the analysis fails. */
1565 static bool
1566 determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
1567 bool no_other_refs)
1569 struct loop *nest, *aloop;
1570 vec<data_reference_p> datarefs = vNULL;
1571 vec<ddr_p> dependences = vNULL;
1572 struct mem_ref_group *gr;
1573 struct mem_ref *ref, *refb;
1574 vec<loop_p> vloops = vNULL;
1575 unsigned *loop_data_size;
1576 unsigned i, j, n;
1577 unsigned volume, dist, adist;
1578 HOST_WIDE_INT vol;
1579 data_reference_p dr;
1580 ddr_p dep;
1582 if (loop->inner)
1583 return true;
1585 /* Find the outermost loop of the loop nest of loop (we require that
1586 there are no sibling loops inside the nest). */
1587 nest = loop;
1588 while (1)
1590 aloop = loop_outer (nest);
1592 if (aloop == current_loops->tree_root
1593 || aloop->inner->next)
1594 break;
1596 nest = aloop;
1599 /* For each loop, determine the amount of data accessed in each iteration.
1600 We use this to estimate whether the reference is evicted from the
1601 cache before its reuse. */
1602 find_loop_nest (nest, &vloops);
1603 n = vloops.length ();
1604 loop_data_size = XNEWVEC (unsigned, n);
1605 volume = volume_of_references (refs);
1606 i = n;
1607 while (i-- != 0)
1609 loop_data_size[i] = volume;
1610 /* Bound the volume by the L2 cache size, since above this bound,
1611 all dependence distances are equivalent. */
1612 if (volume > L2_CACHE_SIZE_BYTES)
1613 continue;
1615 aloop = vloops[i];
1616 vol = estimated_stmt_executions_int (aloop);
1617 if (vol == -1)
1618 vol = expected_loop_iterations (aloop);
1619 volume *= vol;
1622 /* Prepare the references in the form suitable for data dependence
1623 analysis. We ignore unanalyzable data references (the results
1624 are used just as a heuristics to estimate temporality of the
1625 references, hence we do not need to worry about correctness). */
1626 for (gr = refs; gr; gr = gr->next)
1627 for (ref = gr->refs; ref; ref = ref->next)
1629 dr = create_data_ref (nest, loop_containing_stmt (ref->stmt),
1630 ref->mem, ref->stmt, !ref->write_p);
1632 if (dr)
1634 ref->reuse_distance = volume;
1635 dr->aux = ref;
1636 datarefs.safe_push (dr);
1638 else
1639 no_other_refs = false;
1642 FOR_EACH_VEC_ELT (datarefs, i, dr)
1644 dist = self_reuse_distance (dr, loop_data_size, n, loop);
1645 ref = (struct mem_ref *) dr->aux;
1646 if (ref->reuse_distance > dist)
1647 ref->reuse_distance = dist;
1649 if (no_other_refs)
1650 ref->independent_p = true;
1653 if (!compute_all_dependences (datarefs, &dependences, vloops, true))
1654 return false;
1656 FOR_EACH_VEC_ELT (dependences, i, dep)
1658 if (DDR_ARE_DEPENDENT (dep) == chrec_known)
1659 continue;
1661 ref = (struct mem_ref *) DDR_A (dep)->aux;
1662 refb = (struct mem_ref *) DDR_B (dep)->aux;
1664 if (DDR_ARE_DEPENDENT (dep) == chrec_dont_know
1665 || DDR_NUM_DIST_VECTS (dep) == 0)
1667 /* If the dependence cannot be analyzed, assume that there might be
1668 a reuse. */
1669 dist = 0;
1671 ref->independent_p = false;
1672 refb->independent_p = false;
1674 else
1676 /* The distance vectors are normalized to be always lexicographically
1677 positive, hence we cannot tell just from them whether DDR_A comes
1678 before DDR_B or vice versa. However, it is not important,
1679 anyway -- if DDR_A is close to DDR_B, then it is either reused in
1680 DDR_B (and it is not nontemporal), or it reuses the value of DDR_B
1681 in cache (and marking it as nontemporal would not affect
1682 anything). */
1684 dist = volume;
1685 for (j = 0; j < DDR_NUM_DIST_VECTS (dep); j++)
1687 adist = volume_of_dist_vector (DDR_DIST_VECT (dep, j),
1688 loop_data_size, n);
1690 /* If this is a dependence in the innermost loop (i.e., the
1691 distances in all superloops are zero) and it is not
1692 the trivial self-dependence with distance zero, record that
1693 the references are not completely independent. */
1694 if (lambda_vector_zerop (DDR_DIST_VECT (dep, j), n - 1)
1695 && (ref != refb
1696 || DDR_DIST_VECT (dep, j)[n-1] != 0))
1698 ref->independent_p = false;
1699 refb->independent_p = false;
1702 /* Ignore accesses closer than
1703 L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
1704 so that we use nontemporal prefetches e.g. if single memory
1705 location is accessed several times in a single iteration of
1706 the loop. */
1707 if (adist < L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION)
1708 continue;
1710 if (adist < dist)
1711 dist = adist;
1715 if (ref->reuse_distance > dist)
1716 ref->reuse_distance = dist;
1717 if (refb->reuse_distance > dist)
1718 refb->reuse_distance = dist;
1721 free_dependence_relations (dependences);
1722 free_data_refs (datarefs);
1723 free (loop_data_size);
1725 if (dump_file && (dump_flags & TDF_DETAILS))
1727 fprintf (dump_file, "Reuse distances:\n");
1728 for (gr = refs; gr; gr = gr->next)
1729 for (ref = gr->refs; ref; ref = ref->next)
1730 fprintf (dump_file, " ref %p distance %u\n",
1731 (void *) ref, ref->reuse_distance);
1734 return true;
1737 /* Determine whether or not the trip count to ahead ratio is too small based
1738 on prefitablility consideration.
1739 AHEAD: the iteration ahead distance,
1740 EST_NITER: the estimated trip count. */
1742 static bool
1743 trip_count_to_ahead_ratio_too_small_p (unsigned ahead, HOST_WIDE_INT est_niter)
1745 /* Assume trip count to ahead ratio is big enough if the trip count could not
1746 be estimated at compile time. */
1747 if (est_niter < 0)
1748 return false;
1750 if (est_niter < (HOST_WIDE_INT) (TRIP_COUNT_TO_AHEAD_RATIO * ahead))
1752 if (dump_file && (dump_flags & TDF_DETAILS))
1753 fprintf (dump_file,
1754 "Not prefetching -- loop estimated to roll only %d times\n",
1755 (int) est_niter);
1756 return true;
1759 return false;
1762 /* Determine whether or not the number of memory references in the loop is
1763 reasonable based on the profitablity and compilation time considerations.
1764 NINSNS: estimated number of instructions in the loop,
1765 MEM_REF_COUNT: total number of memory references in the loop. */
1767 static bool
1768 mem_ref_count_reasonable_p (unsigned ninsns, unsigned mem_ref_count)
1770 int insn_to_mem_ratio;
1772 if (mem_ref_count == 0)
1773 return false;
1775 /* Miss rate computation (is_miss_rate_acceptable) and dependence analysis
1776 (compute_all_dependences) have high costs based on quadratic complexity.
1777 To avoid huge compilation time, we give up prefetching if mem_ref_count
1778 is too large. */
1779 if (mem_ref_count > PREFETCH_MAX_MEM_REFS_PER_LOOP)
1780 return false;
1782 /* Prefetching improves performance by overlapping cache missing
1783 memory accesses with CPU operations. If the loop does not have
1784 enough CPU operations to overlap with memory operations, prefetching
1785 won't give a significant benefit. One approximate way of checking
1786 this is to require the ratio of instructions to memory references to
1787 be above a certain limit. This approximation works well in practice.
1788 TODO: Implement a more precise computation by estimating the time
1789 for each CPU or memory op in the loop. Time estimates for memory ops
1790 should account for cache misses. */
1791 insn_to_mem_ratio = ninsns / mem_ref_count;
1793 if (insn_to_mem_ratio < PREFETCH_MIN_INSN_TO_MEM_RATIO)
1795 if (dump_file && (dump_flags & TDF_DETAILS))
1796 fprintf (dump_file,
1797 "Not prefetching -- instruction to memory reference ratio (%d) too small\n",
1798 insn_to_mem_ratio);
1799 return false;
1802 return true;
1805 /* Determine whether or not the instruction to prefetch ratio in the loop is
1806 too small based on the profitablity consideration.
1807 NINSNS: estimated number of instructions in the loop,
1808 PREFETCH_COUNT: an estimate of the number of prefetches,
1809 UNROLL_FACTOR: the factor to unroll the loop if prefetching. */
1811 static bool
1812 insn_to_prefetch_ratio_too_small_p (unsigned ninsns, unsigned prefetch_count,
1813 unsigned unroll_factor)
1815 int insn_to_prefetch_ratio;
1817 /* Prefetching most likely causes performance degradation when the instruction
1818 to prefetch ratio is too small. Too many prefetch instructions in a loop
1819 may reduce the I-cache performance.
1820 (unroll_factor * ninsns) is used to estimate the number of instructions in
1821 the unrolled loop. This implementation is a bit simplistic -- the number
1822 of issued prefetch instructions is also affected by unrolling. So,
1823 prefetch_mod and the unroll factor should be taken into account when
1824 determining prefetch_count. Also, the number of insns of the unrolled
1825 loop will usually be significantly smaller than the number of insns of the
1826 original loop * unroll_factor (at least the induction variable increases
1827 and the exit branches will get eliminated), so it might be better to use
1828 tree_estimate_loop_size + estimated_unrolled_size. */
1829 insn_to_prefetch_ratio = (unroll_factor * ninsns) / prefetch_count;
1830 if (insn_to_prefetch_ratio < MIN_INSN_TO_PREFETCH_RATIO)
1832 if (dump_file && (dump_flags & TDF_DETAILS))
1833 fprintf (dump_file,
1834 "Not prefetching -- instruction to prefetch ratio (%d) too small\n",
1835 insn_to_prefetch_ratio);
1836 return true;
1839 return false;
1843 /* Issue prefetch instructions for array references in LOOP. Returns
1844 true if the LOOP was unrolled. */
1846 static bool
1847 loop_prefetch_arrays (struct loop *loop)
1849 struct mem_ref_group *refs;
1850 unsigned ahead, ninsns, time, unroll_factor;
1851 HOST_WIDE_INT est_niter;
1852 struct tree_niter_desc desc;
1853 bool unrolled = false, no_other_refs;
1854 unsigned prefetch_count;
1855 unsigned mem_ref_count;
1857 if (optimize_loop_nest_for_size_p (loop))
1859 if (dump_file && (dump_flags & TDF_DETAILS))
1860 fprintf (dump_file, " ignored (cold area)\n");
1861 return false;
1864 /* FIXME: the time should be weighted by the probabilities of the blocks in
1865 the loop body. */
1866 time = tree_num_loop_insns (loop, &eni_time_weights);
1867 if (time == 0)
1868 return false;
1870 ahead = (PREFETCH_LATENCY + time - 1) / time;
1871 est_niter = estimated_stmt_executions_int (loop);
1872 if (est_niter == -1)
1873 est_niter = max_stmt_executions_int (loop);
1875 /* Prefetching is not likely to be profitable if the trip count to ahead
1876 ratio is too small. */
1877 if (trip_count_to_ahead_ratio_too_small_p (ahead, est_niter))
1878 return false;
1880 ninsns = tree_num_loop_insns (loop, &eni_size_weights);
1882 /* Step 1: gather the memory references. */
1883 refs = gather_memory_references (loop, &no_other_refs, &mem_ref_count);
1885 /* Give up prefetching if the number of memory references in the
1886 loop is not reasonable based on profitablity and compilation time
1887 considerations. */
1888 if (!mem_ref_count_reasonable_p (ninsns, mem_ref_count))
1889 goto fail;
1891 /* Step 2: estimate the reuse effects. */
1892 prune_by_reuse (refs);
1894 if (nothing_to_prefetch_p (refs))
1895 goto fail;
1897 if (!determine_loop_nest_reuse (loop, refs, no_other_refs))
1898 goto fail;
1900 /* Step 3: determine unroll factor. */
1901 unroll_factor = determine_unroll_factor (loop, refs, ninsns, &desc,
1902 est_niter);
1904 /* Estimate prefetch count for the unrolled loop. */
1905 prefetch_count = estimate_prefetch_count (refs, unroll_factor);
1906 if (prefetch_count == 0)
1907 goto fail;
1909 if (dump_file && (dump_flags & TDF_DETAILS))
1910 fprintf (dump_file, "Ahead %d, unroll factor %d, trip count "
1911 HOST_WIDE_INT_PRINT_DEC "\n"
1912 "insn count %d, mem ref count %d, prefetch count %d\n",
1913 ahead, unroll_factor, est_niter,
1914 ninsns, mem_ref_count, prefetch_count);
1916 /* Prefetching is not likely to be profitable if the instruction to prefetch
1917 ratio is too small. */
1918 if (insn_to_prefetch_ratio_too_small_p (ninsns, prefetch_count,
1919 unroll_factor))
1920 goto fail;
1922 mark_nontemporal_stores (loop, refs);
1924 /* Step 4: what to prefetch? */
1925 if (!schedule_prefetches (refs, unroll_factor, ahead))
1926 goto fail;
1928 /* Step 5: unroll the loop. TODO -- peeling of first and last few
1929 iterations so that we do not issue superfluous prefetches. */
1930 if (unroll_factor != 1)
1932 tree_unroll_loop (loop, unroll_factor,
1933 single_dom_exit (loop), &desc);
1934 unrolled = true;
1937 /* Step 6: issue the prefetches. */
1938 issue_prefetches (refs, unroll_factor, ahead);
1940 fail:
1941 release_mem_refs (refs);
1942 return unrolled;
1945 /* Issue prefetch instructions for array references in loops. */
1947 unsigned int
1948 tree_ssa_prefetch_arrays (void)
1950 struct loop *loop;
1951 bool unrolled = false;
1952 int todo_flags = 0;
1954 if (!targetm.have_prefetch ()
1955 /* It is possible to ask compiler for say -mtune=i486 -march=pentium4.
1956 -mtune=i486 causes us having PREFETCH_BLOCK 0, since this is part
1957 of processor costs and i486 does not have prefetch, but
1958 -march=pentium4 causes targetm.have_prefetch to be true. Ugh. */
1959 || PREFETCH_BLOCK == 0)
1960 return 0;
1962 if (dump_file && (dump_flags & TDF_DETAILS))
1964 fprintf (dump_file, "Prefetching parameters:\n");
1965 fprintf (dump_file, " simultaneous prefetches: %d\n",
1966 SIMULTANEOUS_PREFETCHES);
1967 fprintf (dump_file, " prefetch latency: %d\n", PREFETCH_LATENCY);
1968 fprintf (dump_file, " prefetch block size: %d\n", PREFETCH_BLOCK);
1969 fprintf (dump_file, " L1 cache size: %d lines, %d kB\n",
1970 L1_CACHE_SIZE_BYTES / L1_CACHE_LINE_SIZE, L1_CACHE_SIZE);
1971 fprintf (dump_file, " L1 cache line size: %d\n", L1_CACHE_LINE_SIZE);
1972 fprintf (dump_file, " L2 cache size: %d kB\n", L2_CACHE_SIZE);
1973 fprintf (dump_file, " min insn-to-prefetch ratio: %d \n",
1974 MIN_INSN_TO_PREFETCH_RATIO);
1975 fprintf (dump_file, " min insn-to-mem ratio: %d \n",
1976 PREFETCH_MIN_INSN_TO_MEM_RATIO);
1977 fprintf (dump_file, "\n");
1980 initialize_original_copy_tables ();
1982 if (!builtin_decl_explicit_p (BUILT_IN_PREFETCH))
1984 tree type = build_function_type_list (void_type_node,
1985 const_ptr_type_node, NULL_TREE);
1986 tree decl = add_builtin_function ("__builtin_prefetch", type,
1987 BUILT_IN_PREFETCH, BUILT_IN_NORMAL,
1988 NULL, NULL_TREE);
1989 DECL_IS_NOVOPS (decl) = true;
1990 set_builtin_decl (BUILT_IN_PREFETCH, decl, false);
1993 /* We assume that size of cache line is a power of two, so verify this
1994 here. */
1995 gcc_assert ((PREFETCH_BLOCK & (PREFETCH_BLOCK - 1)) == 0);
1997 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1999 if (dump_file && (dump_flags & TDF_DETAILS))
2000 fprintf (dump_file, "Processing loop %d:\n", loop->num);
2002 unrolled |= loop_prefetch_arrays (loop);
2004 if (dump_file && (dump_flags & TDF_DETAILS))
2005 fprintf (dump_file, "\n\n");
2008 if (unrolled)
2010 scev_reset ();
2011 todo_flags |= TODO_cleanup_cfg;
2014 free_original_copy_tables ();
2015 return todo_flags;
2018 /* Prefetching. */
2020 namespace {
2022 const pass_data pass_data_loop_prefetch =
2024 GIMPLE_PASS, /* type */
2025 "aprefetch", /* name */
2026 OPTGROUP_LOOP, /* optinfo_flags */
2027 TV_TREE_PREFETCH, /* tv_id */
2028 ( PROP_cfg | PROP_ssa ), /* properties_required */
2029 0, /* properties_provided */
2030 0, /* properties_destroyed */
2031 0, /* todo_flags_start */
2032 0, /* todo_flags_finish */
2035 class pass_loop_prefetch : public gimple_opt_pass
2037 public:
2038 pass_loop_prefetch (gcc::context *ctxt)
2039 : gimple_opt_pass (pass_data_loop_prefetch, ctxt)
2042 /* opt_pass methods: */
2043 virtual bool gate (function *) { return flag_prefetch_loop_arrays > 0; }
2044 virtual unsigned int execute (function *);
2046 }; // class pass_loop_prefetch
2048 unsigned int
2049 pass_loop_prefetch::execute (function *fun)
2051 if (number_of_loops (fun) <= 1)
2052 return 0;
2054 return tree_ssa_prefetch_arrays ();
2057 } // anon namespace
2059 gimple_opt_pass *
2060 make_pass_loop_prefetch (gcc::context *ctxt)
2062 return new pass_loop_prefetch (ctxt);