tree-flow.h (struct gimple_df): Remove syms_to_rename member, add ssa_renaming_needed...
[gcc.git] / gcc / tree-ssa-loop-prefetch.c
1 /* Array prefetching.
2 Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
10 later version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "tm_p.h"
27 #include "basic-block.h"
28 #include "tree-pretty-print.h"
29 #include "tree-flow.h"
30 #include "cfgloop.h"
31 #include "tree-pass.h"
32 #include "insn-config.h"
33 #include "hashtab.h"
34 #include "tree-chrec.h"
35 #include "tree-scalar-evolution.h"
36 #include "diagnostic-core.h"
37 #include "params.h"
38 #include "langhooks.h"
39 #include "tree-inline.h"
40 #include "tree-data-ref.h"
41
42
43 /* FIXME: Needed for optabs, but this should all be moved to a TBD interface
44 between the GIMPLE and RTL worlds. */
45 #include "expr.h"
46 #include "optabs.h"
47 #include "recog.h"
48
49 /* This pass inserts prefetch instructions to optimize cache usage during
50 accesses to arrays in loops. It processes loops sequentially and:
51
52 1) Gathers all memory references in the single loop.
53 2) For each of the references it decides when it is profitable to prefetch
54 it. To do it, we evaluate the reuse among the accesses, and determines
55 two values: PREFETCH_BEFORE (meaning that it only makes sense to do
56 prefetching in the first PREFETCH_BEFORE iterations of the loop) and
57 PREFETCH_MOD (meaning that it only makes sense to prefetch in the
58 iterations of the loop that are zero modulo PREFETCH_MOD). For example
59 (assuming cache line size is 64 bytes, char has size 1 byte and there
60 is no hardware sequential prefetch):
61
62 char *a;
63 for (i = 0; i < max; i++)
64 {
65 a[255] = ...; (0)
66 a[i] = ...; (1)
67 a[i + 64] = ...; (2)
68 a[16*i] = ...; (3)
69 a[187*i] = ...; (4)
70 a[187*i + 50] = ...; (5)
71 }
72
73 (0) obviously has PREFETCH_BEFORE 1
74 (1) has PREFETCH_BEFORE 64, since (2) accesses the same memory
75 location 64 iterations before it, and PREFETCH_MOD 64 (since
76 it hits the same cache line otherwise).
77 (2) has PREFETCH_MOD 64
78 (3) has PREFETCH_MOD 4
79 (4) has PREFETCH_MOD 1. We do not set PREFETCH_BEFORE here, since
80 the cache line accessed by (5) is the same with probability only
81 7/32.
82 (5) has PREFETCH_MOD 1 as well.
83
84 Additionally, we use data dependence analysis to determine for each
85 reference the distance till the first reuse; this information is used
86 to determine the temporality of the issued prefetch instruction.
87
88 3) We determine how much ahead we need to prefetch. The number of
89 iterations needed is time to fetch / time spent in one iteration of
90 the loop. The problem is that we do not know either of these values,
91 so we just make a heuristic guess based on a magic (possibly)
92 target-specific constant and size of the loop.
93
94 4) Determine which of the references we prefetch. We take into account
95 that there is a maximum number of simultaneous prefetches (provided
96 by machine description). We prefetch as many prefetches as possible
97 while still within this bound (starting with those with lowest
98 prefetch_mod, since they are responsible for most of the cache
99 misses).
100
101 5) We unroll and peel loops so that we are able to satisfy PREFETCH_MOD
102 and PREFETCH_BEFORE requirements (within some bounds), and to avoid
103 prefetching nonaccessed memory.
104 TODO -- actually implement peeling.
105
106 6) We actually emit the prefetch instructions. ??? Perhaps emit the
107 prefetch instructions with guards in cases where 5) was not sufficient
108 to satisfy the constraints?
109
110 A cost model is implemented to determine whether or not prefetching is
111 profitable for a given loop. The cost model has three heuristics:
112
113 1. Function trip_count_to_ahead_ratio_too_small_p implements a
114 heuristic that determines whether or not the loop has too few
115 iterations (compared to ahead). Prefetching is not likely to be
116 beneficial if the trip count to ahead ratio is below a certain
117 minimum.
118
119 2. Function mem_ref_count_reasonable_p implements a heuristic that
120 determines whether the given loop has enough CPU ops that can be
121 overlapped with cache missing memory ops. If not, the loop
122 won't benefit from prefetching. In the implementation,
123 prefetching is not considered beneficial if the ratio between
124 the instruction count and the mem ref count is below a certain
125 minimum.
126
127 3. Function insn_to_prefetch_ratio_too_small_p implements a
128 heuristic that disables prefetching in a loop if the prefetching
129 cost is above a certain limit. The relative prefetching cost is
130 estimated by taking the ratio between the prefetch count and the
131 total intruction count (this models the I-cache cost).
132
133 The limits used in these heuristics are defined as parameters with
134 reasonable default values. Machine-specific default values will be
135 added later.
136
137 Some other TODO:
138 -- write and use more general reuse analysis (that could be also used
139 in other cache aimed loop optimizations)
140 -- make it behave sanely together with the prefetches given by user
141 (now we just ignore them; at the very least we should avoid
142 optimizing loops in that user put his own prefetches)
143 -- we assume cache line size alignment of arrays; this could be
144 improved. */
145
146 /* Magic constants follow. These should be replaced by machine specific
147 numbers. */
148
149 /* True if write can be prefetched by a read prefetch. */
150
151 #ifndef WRITE_CAN_USE_READ_PREFETCH
152 #define WRITE_CAN_USE_READ_PREFETCH 1
153 #endif
154
155 /* True if read can be prefetched by a write prefetch. */
156
157 #ifndef READ_CAN_USE_WRITE_PREFETCH
158 #define READ_CAN_USE_WRITE_PREFETCH 0
159 #endif
160
161 /* The size of the block loaded by a single prefetch. Usually, this is
162 the same as cache line size (at the moment, we only consider one level
163 of cache hierarchy). */
164
165 #ifndef PREFETCH_BLOCK
166 #define PREFETCH_BLOCK L1_CACHE_LINE_SIZE
167 #endif
168
169 /* Do we have a forward hardware sequential prefetching? */
170
171 #ifndef HAVE_FORWARD_PREFETCH
172 #define HAVE_FORWARD_PREFETCH 0
173 #endif
174
175 /* Do we have a backward hardware sequential prefetching? */
176
177 #ifndef HAVE_BACKWARD_PREFETCH
178 #define HAVE_BACKWARD_PREFETCH 0
179 #endif
180
181 /* In some cases we are only able to determine that there is a certain
182 probability that the two accesses hit the same cache line. In this
183 case, we issue the prefetches for both of them if this probability
184 is less then (1000 - ACCEPTABLE_MISS_RATE) per thousand. */
185
186 #ifndef ACCEPTABLE_MISS_RATE
187 #define ACCEPTABLE_MISS_RATE 50
188 #endif
189
190 #ifndef HAVE_prefetch
191 #define HAVE_prefetch 0
192 #endif
193
194 #define L1_CACHE_SIZE_BYTES ((unsigned) (L1_CACHE_SIZE * 1024))
195 #define L2_CACHE_SIZE_BYTES ((unsigned) (L2_CACHE_SIZE * 1024))
196
197 /* We consider a memory access nontemporal if it is not reused sooner than
198 after L2_CACHE_SIZE_BYTES of memory are accessed. However, we ignore
199 accesses closer than L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
200 so that we use nontemporal prefetches e.g. if single memory location
201 is accessed several times in a single iteration of the loop. */
202 #define NONTEMPORAL_FRACTION 16
203
204 /* In case we have to emit a memory fence instruction after the loop that
205 uses nontemporal stores, this defines the builtin to use. */
206
207 #ifndef FENCE_FOLLOWING_MOVNT
208 #define FENCE_FOLLOWING_MOVNT NULL_TREE
209 #endif
210
211 /* It is not profitable to prefetch when the trip count is not at
212 least TRIP_COUNT_TO_AHEAD_RATIO times the prefetch ahead distance.
213 For example, in a loop with a prefetch ahead distance of 10,
214 supposing that TRIP_COUNT_TO_AHEAD_RATIO is equal to 4, it is
215 profitable to prefetch when the trip count is greater or equal to
216 40. In that case, 30 out of the 40 iterations will benefit from
217 prefetching. */
218
219 #ifndef TRIP_COUNT_TO_AHEAD_RATIO
220 #define TRIP_COUNT_TO_AHEAD_RATIO 4
221 #endif
222
223 /* The group of references between that reuse may occur. */
224
225 struct mem_ref_group
226 {
227 tree base; /* Base of the reference. */
228 tree step; /* Step of the reference. */
229 struct mem_ref *refs; /* References in the group. */
230 struct mem_ref_group *next; /* Next group of references. */
231 };
232
233 /* Assigned to PREFETCH_BEFORE when all iterations are to be prefetched. */
234
235 #define PREFETCH_ALL (~(unsigned HOST_WIDE_INT) 0)
236
237 /* Do not generate a prefetch if the unroll factor is significantly less
238 than what is required by the prefetch. This is to avoid redundant
239 prefetches. For example, when prefetch_mod is 16 and unroll_factor is
240 2, prefetching requires unrolling the loop 16 times, but
241 the loop is actually unrolled twice. In this case (ratio = 8),
242 prefetching is not likely to be beneficial. */
243
244 #ifndef PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
245 #define PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO 4
246 #endif
247
248 /* Some of the prefetch computations have quadratic complexity. We want to
249 avoid huge compile times and, therefore, want to limit the amount of
250 memory references per loop where we consider prefetching. */
251
252 #ifndef PREFETCH_MAX_MEM_REFS_PER_LOOP
253 #define PREFETCH_MAX_MEM_REFS_PER_LOOP 200
254 #endif
255
256 /* The memory reference. */
257
258 struct mem_ref
259 {
260 gimple stmt; /* Statement in that the reference appears. */
261 tree mem; /* The reference. */
262 HOST_WIDE_INT delta; /* Constant offset of the reference. */
263 struct mem_ref_group *group; /* The group of references it belongs to. */
264 unsigned HOST_WIDE_INT prefetch_mod;
265 /* Prefetch only each PREFETCH_MOD-th
266 iteration. */
267 unsigned HOST_WIDE_INT prefetch_before;
268 /* Prefetch only first PREFETCH_BEFORE
269 iterations. */
270 unsigned reuse_distance; /* The amount of data accessed before the first
271 reuse of this value. */
272 struct mem_ref *next; /* The next reference in the group. */
273 unsigned write_p : 1; /* Is it a write? */
274 unsigned independent_p : 1; /* True if the reference is independent on
275 all other references inside the loop. */
276 unsigned issue_prefetch_p : 1; /* Should we really issue the prefetch? */
277 unsigned storent_p : 1; /* True if we changed the store to a
278 nontemporal one. */
279 };
280
281 /* Dumps information about reference REF to FILE. */
282
283 static void
284 dump_mem_ref (FILE *file, struct mem_ref *ref)
285 {
286 fprintf (file, "Reference %p:\n", (void *) ref);
287
288 fprintf (file, " group %p (base ", (void *) ref->group);
289 print_generic_expr (file, ref->group->base, TDF_SLIM);
290 fprintf (file, ", step ");
291 if (cst_and_fits_in_hwi (ref->group->step))
292 fprintf (file, HOST_WIDE_INT_PRINT_DEC, int_cst_value (ref->group->step));
293 else
294 print_generic_expr (file, ref->group->step, TDF_TREE);
295 fprintf (file, ")\n");
296
297 fprintf (file, " delta ");
298 fprintf (file, HOST_WIDE_INT_PRINT_DEC, ref->delta);
299 fprintf (file, "\n");
300
301 fprintf (file, " %s\n", ref->write_p ? "write" : "read");
302
303 fprintf (file, "\n");
304 }
305
306 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
307 exist. */
308
309 static struct mem_ref_group *
310 find_or_create_group (struct mem_ref_group **groups, tree base, tree step)
311 {
312 struct mem_ref_group *group;
313
314 for (; *groups; groups = &(*groups)->next)
315 {
316 if (operand_equal_p ((*groups)->step, step, 0)
317 && operand_equal_p ((*groups)->base, base, 0))
318 return *groups;
319
320 /* If step is an integer constant, keep the list of groups sorted
321 by decreasing step. */
322 if (cst_and_fits_in_hwi ((*groups)->step) && cst_and_fits_in_hwi (step)
323 && int_cst_value ((*groups)->step) < int_cst_value (step))
324 break;
325 }
326
327 group = XNEW (struct mem_ref_group);
328 group->base = base;
329 group->step = step;
330 group->refs = NULL;
331 group->next = *groups;
332 *groups = group;
333
334 return group;
335 }
336
337 /* Records a memory reference MEM in GROUP with offset DELTA and write status
338 WRITE_P. The reference occurs in statement STMT. */
339
340 static void
341 record_ref (struct mem_ref_group *group, gimple stmt, tree mem,
342 HOST_WIDE_INT delta, bool write_p)
343 {
344 struct mem_ref **aref;
345
346 /* Do not record the same address twice. */
347 for (aref = &group->refs; *aref; aref = &(*aref)->next)
348 {
349 /* It does not have to be possible for write reference to reuse the read
350 prefetch, or vice versa. */
351 if (!WRITE_CAN_USE_READ_PREFETCH
352 && write_p
353 && !(*aref)->write_p)
354 continue;
355 if (!READ_CAN_USE_WRITE_PREFETCH
356 && !write_p
357 && (*aref)->write_p)
358 continue;
359
360 if ((*aref)->delta == delta)
361 return;
362 }
363
364 (*aref) = XNEW (struct mem_ref);
365 (*aref)->stmt = stmt;
366 (*aref)->mem = mem;
367 (*aref)->delta = delta;
368 (*aref)->write_p = write_p;
369 (*aref)->prefetch_before = PREFETCH_ALL;
370 (*aref)->prefetch_mod = 1;
371 (*aref)->reuse_distance = 0;
372 (*aref)->issue_prefetch_p = false;
373 (*aref)->group = group;
374 (*aref)->next = NULL;
375 (*aref)->independent_p = false;
376 (*aref)->storent_p = false;
377
378 if (dump_file && (dump_flags & TDF_DETAILS))
379 dump_mem_ref (dump_file, *aref);
380 }
381
382 /* Release memory references in GROUPS. */
383
384 static void
385 release_mem_refs (struct mem_ref_group *groups)
386 {
387 struct mem_ref_group *next_g;
388 struct mem_ref *ref, *next_r;
389
390 for (; groups; groups = next_g)
391 {
392 next_g = groups->next;
393 for (ref = groups->refs; ref; ref = next_r)
394 {
395 next_r = ref->next;
396 free (ref);
397 }
398 free (groups);
399 }
400 }
401
402 /* A structure used to pass arguments to idx_analyze_ref. */
403
404 struct ar_data
405 {
406 struct loop *loop; /* Loop of the reference. */
407 gimple stmt; /* Statement of the reference. */
408 tree *step; /* Step of the memory reference. */
409 HOST_WIDE_INT *delta; /* Offset of the memory reference. */
410 };
411
412 /* Analyzes a single INDEX of a memory reference to obtain information
413 described at analyze_ref. Callback for for_each_index. */
414
415 static bool
416 idx_analyze_ref (tree base, tree *index, void *data)
417 {
418 struct ar_data *ar_data = (struct ar_data *) data;
419 tree ibase, step, stepsize;
420 HOST_WIDE_INT idelta = 0, imult = 1;
421 affine_iv iv;
422
423 if (!simple_iv (ar_data->loop, loop_containing_stmt (ar_data->stmt),
424 *index, &iv, true))
425 return false;
426 ibase = iv.base;
427 step = iv.step;
428
429 if (TREE_CODE (ibase) == POINTER_PLUS_EXPR
430 && cst_and_fits_in_hwi (TREE_OPERAND (ibase, 1)))
431 {
432 idelta = int_cst_value (TREE_OPERAND (ibase, 1));
433 ibase = TREE_OPERAND (ibase, 0);
434 }
435 if (cst_and_fits_in_hwi (ibase))
436 {
437 idelta += int_cst_value (ibase);
438 ibase = build_int_cst (TREE_TYPE (ibase), 0);
439 }
440
441 if (TREE_CODE (base) == ARRAY_REF)
442 {
443 stepsize = array_ref_element_size (base);
444 if (!cst_and_fits_in_hwi (stepsize))
445 return false;
446 imult = int_cst_value (stepsize);
447 step = fold_build2 (MULT_EXPR, sizetype,
448 fold_convert (sizetype, step),
449 fold_convert (sizetype, stepsize));
450 idelta *= imult;
451 }
452
453 if (*ar_data->step == NULL_TREE)
454 *ar_data->step = step;
455 else
456 *ar_data->step = fold_build2 (PLUS_EXPR, sizetype,
457 fold_convert (sizetype, *ar_data->step),
458 fold_convert (sizetype, step));
459 *ar_data->delta += idelta;
460 *index = ibase;
461
462 return true;
463 }
464
465 /* Tries to express REF_P in shape &BASE + STEP * iter + DELTA, where DELTA and
466 STEP are integer constants and iter is number of iterations of LOOP. The
467 reference occurs in statement STMT. Strips nonaddressable component
468 references from REF_P. */
469
470 static bool
471 analyze_ref (struct loop *loop, tree *ref_p, tree *base,
472 tree *step, HOST_WIDE_INT *delta,
473 gimple stmt)
474 {
475 struct ar_data ar_data;
476 tree off;
477 HOST_WIDE_INT bit_offset;
478 tree ref = *ref_p;
479
480 *step = NULL_TREE;
481 *delta = 0;
482
483 /* First strip off the component references. Ignore bitfields.
484 Also strip off the real and imagine parts of a complex, so that
485 they can have the same base. */
486 if (TREE_CODE (ref) == REALPART_EXPR
487 || TREE_CODE (ref) == IMAGPART_EXPR
488 || (TREE_CODE (ref) == COMPONENT_REF
489 && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref, 1))))
490 {
491 if (TREE_CODE (ref) == IMAGPART_EXPR)
492 *delta += int_size_in_bytes (TREE_TYPE (ref));
493 ref = TREE_OPERAND (ref, 0);
494 }
495
496 *ref_p = ref;
497
498 for (; TREE_CODE (ref) == COMPONENT_REF; ref = TREE_OPERAND (ref, 0))
499 {
500 off = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1));
501 bit_offset = TREE_INT_CST_LOW (off);
502 gcc_assert (bit_offset % BITS_PER_UNIT == 0);
503
504 *delta += bit_offset / BITS_PER_UNIT;
505 }
506
507 *base = unshare_expr (ref);
508 ar_data.loop = loop;
509 ar_data.stmt = stmt;
510 ar_data.step = step;
511 ar_data.delta = delta;
512 return for_each_index (base, idx_analyze_ref, &ar_data);
513 }
514
515 /* Record a memory reference REF to the list REFS. The reference occurs in
516 LOOP in statement STMT and it is write if WRITE_P. Returns true if the
517 reference was recorded, false otherwise. */
518
519 static bool
520 gather_memory_references_ref (struct loop *loop, struct mem_ref_group **refs,
521 tree ref, bool write_p, gimple stmt)
522 {
523 tree base, step;
524 HOST_WIDE_INT delta;
525 struct mem_ref_group *agrp;
526
527 if (get_base_address (ref) == NULL)
528 return false;
529
530 if (!analyze_ref (loop, &ref, &base, &step, &delta, stmt))
531 return false;
532 /* If analyze_ref fails the default is a NULL_TREE. We can stop here. */
533 if (step == NULL_TREE)
534 return false;
535
536 /* Stop if the address of BASE could not be taken. */
537 if (may_be_nonaddressable_p (base))
538 return false;
539
540 /* Limit non-constant step prefetching only to the innermost loops. */
541 if (!cst_and_fits_in_hwi (step) && loop->inner != NULL)
542 return false;
543
544 /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
545 are integer constants. */
546 agrp = find_or_create_group (refs, base, step);
547 record_ref (agrp, stmt, ref, delta, write_p);
548
549 return true;
550 }
551
552 /* Record the suitable memory references in LOOP. NO_OTHER_REFS is set to
553 true if there are no other memory references inside the loop. */
554
555 static struct mem_ref_group *
556 gather_memory_references (struct loop *loop, bool *no_other_refs, unsigned *ref_count)
557 {
558 basic_block *body = get_loop_body_in_dom_order (loop);
559 basic_block bb;
560 unsigned i;
561 gimple_stmt_iterator bsi;
562 gimple stmt;
563 tree lhs, rhs;
564 struct mem_ref_group *refs = NULL;
565
566 *no_other_refs = true;
567 *ref_count = 0;
568
569 /* Scan the loop body in order, so that the former references precede the
570 later ones. */
571 for (i = 0; i < loop->num_nodes; i++)
572 {
573 bb = body[i];
574 if (bb->loop_father != loop)
575 continue;
576
577 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
578 {
579 stmt = gsi_stmt (bsi);
580
581 if (gimple_code (stmt) != GIMPLE_ASSIGN)
582 {
583 if (gimple_vuse (stmt)
584 || (is_gimple_call (stmt)
585 && !(gimple_call_flags (stmt) & ECF_CONST)))
586 *no_other_refs = false;
587 continue;
588 }
589
590 lhs = gimple_assign_lhs (stmt);
591 rhs = gimple_assign_rhs1 (stmt);
592
593 if (REFERENCE_CLASS_P (rhs))
594 {
595 *no_other_refs &= gather_memory_references_ref (loop, &refs,
596 rhs, false, stmt);
597 *ref_count += 1;
598 }
599 if (REFERENCE_CLASS_P (lhs))
600 {
601 *no_other_refs &= gather_memory_references_ref (loop, &refs,
602 lhs, true, stmt);
603 *ref_count += 1;
604 }
605 }
606 }
607 free (body);
608
609 return refs;
610 }
611
612 /* Prune the prefetch candidate REF using the self-reuse. */
613
614 static void
615 prune_ref_by_self_reuse (struct mem_ref *ref)
616 {
617 HOST_WIDE_INT step;
618 bool backward;
619
620 /* If the step size is non constant, we cannot calculate prefetch_mod. */
621 if (!cst_and_fits_in_hwi (ref->group->step))
622 return;
623
624 step = int_cst_value (ref->group->step);
625
626 backward = step < 0;
627
628 if (step == 0)
629 {
630 /* Prefetch references to invariant address just once. */
631 ref->prefetch_before = 1;
632 return;
633 }
634
635 if (backward)
636 step = -step;
637
638 if (step > PREFETCH_BLOCK)
639 return;
640
641 if ((backward && HAVE_BACKWARD_PREFETCH)
642 || (!backward && HAVE_FORWARD_PREFETCH))
643 {
644 ref->prefetch_before = 1;
645 return;
646 }
647
648 ref->prefetch_mod = PREFETCH_BLOCK / step;
649 }
650
651 /* Divides X by BY, rounding down. */
652
653 static HOST_WIDE_INT
654 ddown (HOST_WIDE_INT x, unsigned HOST_WIDE_INT by)
655 {
656 gcc_assert (by > 0);
657
658 if (x >= 0)
659 return x / by;
660 else
661 return (x + by - 1) / by;
662 }
663
664 /* Given a CACHE_LINE_SIZE and two inductive memory references
665 with a common STEP greater than CACHE_LINE_SIZE and an address
666 difference DELTA, compute the probability that they will fall
667 in different cache lines. Return true if the computed miss rate
668 is not greater than the ACCEPTABLE_MISS_RATE. DISTINCT_ITERS is the
669 number of distinct iterations after which the pattern repeats itself.
670 ALIGN_UNIT is the unit of alignment in bytes. */
671
672 static bool
673 is_miss_rate_acceptable (unsigned HOST_WIDE_INT cache_line_size,
674 HOST_WIDE_INT step, HOST_WIDE_INT delta,
675 unsigned HOST_WIDE_INT distinct_iters,
676 int align_unit)
677 {
678 unsigned align, iter;
679 int total_positions, miss_positions, max_allowed_miss_positions;
680 int address1, address2, cache_line1, cache_line2;
681
682 /* It always misses if delta is greater than or equal to the cache
683 line size. */
684 if (delta >= (HOST_WIDE_INT) cache_line_size)
685 return false;
686
687 miss_positions = 0;
688 total_positions = (cache_line_size / align_unit) * distinct_iters;
689 max_allowed_miss_positions = (ACCEPTABLE_MISS_RATE * total_positions) / 1000;
690
691 /* Iterate through all possible alignments of the first
692 memory reference within its cache line. */
693 for (align = 0; align < cache_line_size; align += align_unit)
694
695 /* Iterate through all distinct iterations. */
696 for (iter = 0; iter < distinct_iters; iter++)
697 {
698 address1 = align + step * iter;
699 address2 = address1 + delta;
700 cache_line1 = address1 / cache_line_size;
701 cache_line2 = address2 / cache_line_size;
702 if (cache_line1 != cache_line2)
703 {
704 miss_positions += 1;
705 if (miss_positions > max_allowed_miss_positions)
706 return false;
707 }
708 }
709 return true;
710 }
711
712 /* Prune the prefetch candidate REF using the reuse with BY.
713 If BY_IS_BEFORE is true, BY is before REF in the loop. */
714
715 static void
716 prune_ref_by_group_reuse (struct mem_ref *ref, struct mem_ref *by,
717 bool by_is_before)
718 {
719 HOST_WIDE_INT step;
720 bool backward;
721 HOST_WIDE_INT delta_r = ref->delta, delta_b = by->delta;
722 HOST_WIDE_INT delta = delta_b - delta_r;
723 HOST_WIDE_INT hit_from;
724 unsigned HOST_WIDE_INT prefetch_before, prefetch_block;
725 HOST_WIDE_INT reduced_step;
726 unsigned HOST_WIDE_INT reduced_prefetch_block;
727 tree ref_type;
728 int align_unit;
729
730 /* If the step is non constant we cannot calculate prefetch_before. */
731 if (!cst_and_fits_in_hwi (ref->group->step)) {
732 return;
733 }
734
735 step = int_cst_value (ref->group->step);
736
737 backward = step < 0;
738
739
740 if (delta == 0)
741 {
742 /* If the references has the same address, only prefetch the
743 former. */
744 if (by_is_before)
745 ref->prefetch_before = 0;
746
747 return;
748 }
749
750 if (!step)
751 {
752 /* If the reference addresses are invariant and fall into the
753 same cache line, prefetch just the first one. */
754 if (!by_is_before)
755 return;
756
757 if (ddown (ref->delta, PREFETCH_BLOCK)
758 != ddown (by->delta, PREFETCH_BLOCK))
759 return;
760
761 ref->prefetch_before = 0;
762 return;
763 }
764
765 /* Only prune the reference that is behind in the array. */
766 if (backward)
767 {
768 if (delta > 0)
769 return;
770
771 /* Transform the data so that we may assume that the accesses
772 are forward. */
773 delta = - delta;
774 step = -step;
775 delta_r = PREFETCH_BLOCK - 1 - delta_r;
776 delta_b = PREFETCH_BLOCK - 1 - delta_b;
777 }
778 else
779 {
780 if (delta < 0)
781 return;
782 }
783
784 /* Check whether the two references are likely to hit the same cache
785 line, and how distant the iterations in that it occurs are from
786 each other. */
787
788 if (step <= PREFETCH_BLOCK)
789 {
790 /* The accesses are sure to meet. Let us check when. */
791 hit_from = ddown (delta_b, PREFETCH_BLOCK) * PREFETCH_BLOCK;
792 prefetch_before = (hit_from - delta_r + step - 1) / step;
793
794 /* Do not reduce prefetch_before if we meet beyond cache size. */
795 if (prefetch_before > absu_hwi (L2_CACHE_SIZE_BYTES / step))
796 prefetch_before = PREFETCH_ALL;
797 if (prefetch_before < ref->prefetch_before)
798 ref->prefetch_before = prefetch_before;
799
800 return;
801 }
802
803 /* A more complicated case with step > prefetch_block. First reduce
804 the ratio between the step and the cache line size to its simplest
805 terms. The resulting denominator will then represent the number of
806 distinct iterations after which each address will go back to its
807 initial location within the cache line. This computation assumes
808 that PREFETCH_BLOCK is a power of two. */
809 prefetch_block = PREFETCH_BLOCK;
810 reduced_prefetch_block = prefetch_block;
811 reduced_step = step;
812 while ((reduced_step & 1) == 0
813 && reduced_prefetch_block > 1)
814 {
815 reduced_step >>= 1;
816 reduced_prefetch_block >>= 1;
817 }
818
819 prefetch_before = delta / step;
820 delta %= step;
821 ref_type = TREE_TYPE (ref->mem);
822 align_unit = TYPE_ALIGN (ref_type) / 8;
823 if (is_miss_rate_acceptable (prefetch_block, step, delta,
824 reduced_prefetch_block, align_unit))
825 {
826 /* Do not reduce prefetch_before if we meet beyond cache size. */
827 if (prefetch_before > L2_CACHE_SIZE_BYTES / PREFETCH_BLOCK)
828 prefetch_before = PREFETCH_ALL;
829 if (prefetch_before < ref->prefetch_before)
830 ref->prefetch_before = prefetch_before;
831
832 return;
833 }
834
835 /* Try also the following iteration. */
836 prefetch_before++;
837 delta = step - delta;
838 if (is_miss_rate_acceptable (prefetch_block, step, delta,
839 reduced_prefetch_block, align_unit))
840 {
841 if (prefetch_before < ref->prefetch_before)
842 ref->prefetch_before = prefetch_before;
843
844 return;
845 }
846
847 /* The ref probably does not reuse by. */
848 return;
849 }
850
851 /* Prune the prefetch candidate REF using the reuses with other references
852 in REFS. */
853
854 static void
855 prune_ref_by_reuse (struct mem_ref *ref, struct mem_ref *refs)
856 {
857 struct mem_ref *prune_by;
858 bool before = true;
859
860 prune_ref_by_self_reuse (ref);
861
862 for (prune_by = refs; prune_by; prune_by = prune_by->next)
863 {
864 if (prune_by == ref)
865 {
866 before = false;
867 continue;
868 }
869
870 if (!WRITE_CAN_USE_READ_PREFETCH
871 && ref->write_p
872 && !prune_by->write_p)
873 continue;
874 if (!READ_CAN_USE_WRITE_PREFETCH
875 && !ref->write_p
876 && prune_by->write_p)
877 continue;
878
879 prune_ref_by_group_reuse (ref, prune_by, before);
880 }
881 }
882
883 /* Prune the prefetch candidates in GROUP using the reuse analysis. */
884
885 static void
886 prune_group_by_reuse (struct mem_ref_group *group)
887 {
888 struct mem_ref *ref_pruned;
889
890 for (ref_pruned = group->refs; ref_pruned; ref_pruned = ref_pruned->next)
891 {
892 prune_ref_by_reuse (ref_pruned, group->refs);
893
894 if (dump_file && (dump_flags & TDF_DETAILS))
895 {
896 fprintf (dump_file, "Reference %p:", (void *) ref_pruned);
897
898 if (ref_pruned->prefetch_before == PREFETCH_ALL
899 && ref_pruned->prefetch_mod == 1)
900 fprintf (dump_file, " no restrictions");
901 else if (ref_pruned->prefetch_before == 0)
902 fprintf (dump_file, " do not prefetch");
903 else if (ref_pruned->prefetch_before <= ref_pruned->prefetch_mod)
904 fprintf (dump_file, " prefetch once");
905 else
906 {
907 if (ref_pruned->prefetch_before != PREFETCH_ALL)
908 {
909 fprintf (dump_file, " prefetch before ");
910 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC,
911 ref_pruned->prefetch_before);
912 }
913 if (ref_pruned->prefetch_mod != 1)
914 {
915 fprintf (dump_file, " prefetch mod ");
916 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC,
917 ref_pruned->prefetch_mod);
918 }
919 }
920 fprintf (dump_file, "\n");
921 }
922 }
923 }
924
925 /* Prune the list of prefetch candidates GROUPS using the reuse analysis. */
926
927 static void
928 prune_by_reuse (struct mem_ref_group *groups)
929 {
930 for (; groups; groups = groups->next)
931 prune_group_by_reuse (groups);
932 }
933
934 /* Returns true if we should issue prefetch for REF. */
935
936 static bool
937 should_issue_prefetch_p (struct mem_ref *ref)
938 {
939 /* For now do not issue prefetches for only first few of the
940 iterations. */
941 if (ref->prefetch_before != PREFETCH_ALL)
942 {
943 if (dump_file && (dump_flags & TDF_DETAILS))
944 fprintf (dump_file, "Ignoring %p due to prefetch_before\n",
945 (void *) ref);
946 return false;
947 }
948
949 /* Do not prefetch nontemporal stores. */
950 if (ref->storent_p)
951 {
952 if (dump_file && (dump_flags & TDF_DETAILS))
953 fprintf (dump_file, "Ignoring nontemporal store %p\n", (void *) ref);
954 return false;
955 }
956
957 return true;
958 }
959
960 /* Decide which of the prefetch candidates in GROUPS to prefetch.
961 AHEAD is the number of iterations to prefetch ahead (which corresponds
962 to the number of simultaneous instances of one prefetch running at a
963 time). UNROLL_FACTOR is the factor by that the loop is going to be
964 unrolled. Returns true if there is anything to prefetch. */
965
966 static bool
967 schedule_prefetches (struct mem_ref_group *groups, unsigned unroll_factor,
968 unsigned ahead)
969 {
970 unsigned remaining_prefetch_slots, n_prefetches, prefetch_slots;
971 unsigned slots_per_prefetch;
972 struct mem_ref *ref;
973 bool any = false;
974
975 /* At most SIMULTANEOUS_PREFETCHES should be running at the same time. */
976 remaining_prefetch_slots = SIMULTANEOUS_PREFETCHES;
977
978 /* The prefetch will run for AHEAD iterations of the original loop, i.e.,
979 AHEAD / UNROLL_FACTOR iterations of the unrolled loop. In each iteration,
980 it will need a prefetch slot. */
981 slots_per_prefetch = (ahead + unroll_factor / 2) / unroll_factor;
982 if (dump_file && (dump_flags & TDF_DETAILS))
983 fprintf (dump_file, "Each prefetch instruction takes %u prefetch slots.\n",
984 slots_per_prefetch);
985
986 /* For now we just take memory references one by one and issue
987 prefetches for as many as possible. The groups are sorted
988 starting with the largest step, since the references with
989 large step are more likely to cause many cache misses. */
990
991 for (; groups; groups = groups->next)
992 for (ref = groups->refs; ref; ref = ref->next)
993 {
994 if (!should_issue_prefetch_p (ref))
995 continue;
996
997 /* The loop is far from being sufficiently unrolled for this
998 prefetch. Do not generate prefetch to avoid many redudant
999 prefetches. */
1000 if (ref->prefetch_mod / unroll_factor > PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO)
1001 continue;
1002
1003 /* If we need to prefetch the reference each PREFETCH_MOD iterations,
1004 and we unroll the loop UNROLL_FACTOR times, we need to insert
1005 ceil (UNROLL_FACTOR / PREFETCH_MOD) instructions in each
1006 iteration. */
1007 n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
1008 / ref->prefetch_mod);
1009 prefetch_slots = n_prefetches * slots_per_prefetch;
1010
1011 /* If more than half of the prefetches would be lost anyway, do not
1012 issue the prefetch. */
1013 if (2 * remaining_prefetch_slots < prefetch_slots)
1014 continue;
1015
1016 ref->issue_prefetch_p = true;
1017
1018 if (remaining_prefetch_slots <= prefetch_slots)
1019 return true;
1020 remaining_prefetch_slots -= prefetch_slots;
1021 any = true;
1022 }
1023
1024 return any;
1025 }
1026
1027 /* Return TRUE if no prefetch is going to be generated in the given
1028 GROUPS. */
1029
1030 static bool
1031 nothing_to_prefetch_p (struct mem_ref_group *groups)
1032 {
1033 struct mem_ref *ref;
1034
1035 for (; groups; groups = groups->next)
1036 for (ref = groups->refs; ref; ref = ref->next)
1037 if (should_issue_prefetch_p (ref))
1038 return false;
1039
1040 return true;
1041 }
1042
1043 /* Estimate the number of prefetches in the given GROUPS.
1044 UNROLL_FACTOR is the factor by which LOOP was unrolled. */
1045
1046 static int
1047 estimate_prefetch_count (struct mem_ref_group *groups, unsigned unroll_factor)
1048 {
1049 struct mem_ref *ref;
1050 unsigned n_prefetches;
1051 int prefetch_count = 0;
1052
1053 for (; groups; groups = groups->next)
1054 for (ref = groups->refs; ref; ref = ref->next)
1055 if (should_issue_prefetch_p (ref))
1056 {
1057 n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
1058 / ref->prefetch_mod);
1059 prefetch_count += n_prefetches;
1060 }
1061
1062 return prefetch_count;
1063 }
1064
1065 /* Issue prefetches for the reference REF into loop as decided before.
1066 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR
1067 is the factor by which LOOP was unrolled. */
1068
1069 static void
1070 issue_prefetch_ref (struct mem_ref *ref, unsigned unroll_factor, unsigned ahead)
1071 {
1072 HOST_WIDE_INT delta;
1073 tree addr, addr_base, write_p, local, forward;
1074 gimple prefetch;
1075 gimple_stmt_iterator bsi;
1076 unsigned n_prefetches, ap;
1077 bool nontemporal = ref->reuse_distance >= L2_CACHE_SIZE_BYTES;
1078
1079 if (dump_file && (dump_flags & TDF_DETAILS))
1080 fprintf (dump_file, "Issued%s prefetch for %p.\n",
1081 nontemporal ? " nontemporal" : "",
1082 (void *) ref);
1083
1084 bsi = gsi_for_stmt (ref->stmt);
1085
1086 n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
1087 / ref->prefetch_mod);
1088 addr_base = build_fold_addr_expr_with_type (ref->mem, ptr_type_node);
1089 addr_base = force_gimple_operand_gsi (&bsi, unshare_expr (addr_base),
1090 true, NULL, true, GSI_SAME_STMT);
1091 write_p = ref->write_p ? integer_one_node : integer_zero_node;
1092 local = nontemporal ? integer_zero_node : integer_three_node;
1093
1094 for (ap = 0; ap < n_prefetches; ap++)
1095 {
1096 if (cst_and_fits_in_hwi (ref->group->step))
1097 {
1098 /* Determine the address to prefetch. */
1099 delta = (ahead + ap * ref->prefetch_mod) *
1100 int_cst_value (ref->group->step);
1101 addr = fold_build_pointer_plus_hwi (addr_base, delta);
1102 addr = force_gimple_operand_gsi (&bsi, unshare_expr (addr), true, NULL,
1103 true, GSI_SAME_STMT);
1104 }
1105 else
1106 {
1107 /* The step size is non-constant but loop-invariant. We use the
1108 heuristic to simply prefetch ahead iterations ahead. */
1109 forward = fold_build2 (MULT_EXPR, sizetype,
1110 fold_convert (sizetype, ref->group->step),
1111 fold_convert (sizetype, size_int (ahead)));
1112 addr = fold_build_pointer_plus (addr_base, forward);
1113 addr = force_gimple_operand_gsi (&bsi, unshare_expr (addr), true,
1114 NULL, true, GSI_SAME_STMT);
1115 }
1116 /* Create the prefetch instruction. */
1117 prefetch = gimple_build_call (builtin_decl_explicit (BUILT_IN_PREFETCH),
1118 3, addr, write_p, local);
1119 gsi_insert_before (&bsi, prefetch, GSI_SAME_STMT);
1120 }
1121 }
1122
1123 /* Issue prefetches for the references in GROUPS into loop as decided before.
1124 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR is the
1125 factor by that LOOP was unrolled. */
1126
1127 static void
1128 issue_prefetches (struct mem_ref_group *groups,
1129 unsigned unroll_factor, unsigned ahead)
1130 {
1131 struct mem_ref *ref;
1132
1133 for (; groups; groups = groups->next)
1134 for (ref = groups->refs; ref; ref = ref->next)
1135 if (ref->issue_prefetch_p)
1136 issue_prefetch_ref (ref, unroll_factor, ahead);
1137 }
1138
1139 /* Returns true if REF is a memory write for that a nontemporal store insn
1140 can be used. */
1141
1142 static bool
1143 nontemporal_store_p (struct mem_ref *ref)
1144 {
1145 enum machine_mode mode;
1146 enum insn_code code;
1147
1148 /* REF must be a write that is not reused. We require it to be independent
1149 on all other memory references in the loop, as the nontemporal stores may
1150 be reordered with respect to other memory references. */
1151 if (!ref->write_p
1152 || !ref->independent_p
1153 || ref->reuse_distance < L2_CACHE_SIZE_BYTES)
1154 return false;
1155
1156 /* Check that we have the storent instruction for the mode. */
1157 mode = TYPE_MODE (TREE_TYPE (ref->mem));
1158 if (mode == BLKmode)
1159 return false;
1160
1161 code = optab_handler (storent_optab, mode);
1162 return code != CODE_FOR_nothing;
1163 }
1164
1165 /* If REF is a nontemporal store, we mark the corresponding modify statement
1166 and return true. Otherwise, we return false. */
1167
1168 static bool
1169 mark_nontemporal_store (struct mem_ref *ref)
1170 {
1171 if (!nontemporal_store_p (ref))
1172 return false;
1173
1174 if (dump_file && (dump_flags & TDF_DETAILS))
1175 fprintf (dump_file, "Marked reference %p as a nontemporal store.\n",
1176 (void *) ref);
1177
1178 gimple_assign_set_nontemporal_move (ref->stmt, true);
1179 ref->storent_p = true;
1180
1181 return true;
1182 }
1183
1184 /* Issue a memory fence instruction after LOOP. */
1185
1186 static void
1187 emit_mfence_after_loop (struct loop *loop)
1188 {
1189 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1190 edge exit;
1191 gimple call;
1192 gimple_stmt_iterator bsi;
1193 unsigned i;
1194
1195 FOR_EACH_VEC_ELT (edge, exits, i, exit)
1196 {
1197 call = gimple_build_call (FENCE_FOLLOWING_MOVNT, 0);
1198
1199 if (!single_pred_p (exit->dest)
1200 /* If possible, we prefer not to insert the fence on other paths
1201 in cfg. */
1202 && !(exit->flags & EDGE_ABNORMAL))
1203 split_loop_exit_edge (exit);
1204 bsi = gsi_after_labels (exit->dest);
1205
1206 gsi_insert_before (&bsi, call, GSI_NEW_STMT);
1207 }
1208
1209 VEC_free (edge, heap, exits);
1210 update_ssa (TODO_update_ssa_only_virtuals);
1211 }
1212
1213 /* Returns true if we can use storent in loop, false otherwise. */
1214
1215 static bool
1216 may_use_storent_in_loop_p (struct loop *loop)
1217 {
1218 bool ret = true;
1219
1220 if (loop->inner != NULL)
1221 return false;
1222
1223 /* If we must issue a mfence insn after using storent, check that there
1224 is a suitable place for it at each of the loop exits. */
1225 if (FENCE_FOLLOWING_MOVNT != NULL_TREE)
1226 {
1227 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1228 unsigned i;
1229 edge exit;
1230
1231 FOR_EACH_VEC_ELT (edge, exits, i, exit)
1232 if ((exit->flags & EDGE_ABNORMAL)
1233 && exit->dest == EXIT_BLOCK_PTR)
1234 ret = false;
1235
1236 VEC_free (edge, heap, exits);
1237 }
1238
1239 return ret;
1240 }
1241
1242 /* Marks nontemporal stores in LOOP. GROUPS contains the description of memory
1243 references in the loop. */
1244
1245 static void
1246 mark_nontemporal_stores (struct loop *loop, struct mem_ref_group *groups)
1247 {
1248 struct mem_ref *ref;
1249 bool any = false;
1250
1251 if (!may_use_storent_in_loop_p (loop))
1252 return;
1253
1254 for (; groups; groups = groups->next)
1255 for (ref = groups->refs; ref; ref = ref->next)
1256 any |= mark_nontemporal_store (ref);
1257
1258 if (any && FENCE_FOLLOWING_MOVNT != NULL_TREE)
1259 emit_mfence_after_loop (loop);
1260 }
1261
1262 /* Determines whether we can profitably unroll LOOP FACTOR times, and if
1263 this is the case, fill in DESC by the description of number of
1264 iterations. */
1265
1266 static bool
1267 should_unroll_loop_p (struct loop *loop, struct tree_niter_desc *desc,
1268 unsigned factor)
1269 {
1270 if (!can_unroll_loop_p (loop, factor, desc))
1271 return false;
1272
1273 /* We only consider loops without control flow for unrolling. This is not
1274 a hard restriction -- tree_unroll_loop works with arbitrary loops
1275 as well; but the unrolling/prefetching is usually more profitable for
1276 loops consisting of a single basic block, and we want to limit the
1277 code growth. */
1278 if (loop->num_nodes > 2)
1279 return false;
1280
1281 return true;
1282 }
1283
1284 /* Determine the coefficient by that unroll LOOP, from the information
1285 contained in the list of memory references REFS. Description of
1286 umber of iterations of LOOP is stored to DESC. NINSNS is the number of
1287 insns of the LOOP. EST_NITER is the estimated number of iterations of
1288 the loop, or -1 if no estimate is available. */
1289
1290 static unsigned
1291 determine_unroll_factor (struct loop *loop, struct mem_ref_group *refs,
1292 unsigned ninsns, struct tree_niter_desc *desc,
1293 HOST_WIDE_INT est_niter)
1294 {
1295 unsigned upper_bound;
1296 unsigned nfactor, factor, mod_constraint;
1297 struct mem_ref_group *agp;
1298 struct mem_ref *ref;
1299
1300 /* First check whether the loop is not too large to unroll. We ignore
1301 PARAM_MAX_UNROLL_TIMES, because for small loops, it prevented us
1302 from unrolling them enough to make exactly one cache line covered by each
1303 iteration. Also, the goal of PARAM_MAX_UNROLL_TIMES is to prevent
1304 us from unrolling the loops too many times in cases where we only expect
1305 gains from better scheduling and decreasing loop overhead, which is not
1306 the case here. */
1307 upper_bound = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / ninsns;
1308
1309 /* If we unrolled the loop more times than it iterates, the unrolled version
1310 of the loop would be never entered. */
1311 if (est_niter >= 0 && est_niter < (HOST_WIDE_INT) upper_bound)
1312 upper_bound = est_niter;
1313
1314 if (upper_bound <= 1)
1315 return 1;
1316
1317 /* Choose the factor so that we may prefetch each cache just once,
1318 but bound the unrolling by UPPER_BOUND. */
1319 factor = 1;
1320 for (agp = refs; agp; agp = agp->next)
1321 for (ref = agp->refs; ref; ref = ref->next)
1322 if (should_issue_prefetch_p (ref))
1323 {
1324 mod_constraint = ref->prefetch_mod;
1325 nfactor = least_common_multiple (mod_constraint, factor);
1326 if (nfactor <= upper_bound)
1327 factor = nfactor;
1328 }
1329
1330 if (!should_unroll_loop_p (loop, desc, factor))
1331 return 1;
1332
1333 return factor;
1334 }
1335
1336 /* Returns the total volume of the memory references REFS, taking into account
1337 reuses in the innermost loop and cache line size. TODO -- we should also
1338 take into account reuses across the iterations of the loops in the loop
1339 nest. */
1340
1341 static unsigned
1342 volume_of_references (struct mem_ref_group *refs)
1343 {
1344 unsigned volume = 0;
1345 struct mem_ref_group *gr;
1346 struct mem_ref *ref;
1347
1348 for (gr = refs; gr; gr = gr->next)
1349 for (ref = gr->refs; ref; ref = ref->next)
1350 {
1351 /* Almost always reuses another value? */
1352 if (ref->prefetch_before != PREFETCH_ALL)
1353 continue;
1354
1355 /* If several iterations access the same cache line, use the size of
1356 the line divided by this number. Otherwise, a cache line is
1357 accessed in each iteration. TODO -- in the latter case, we should
1358 take the size of the reference into account, rounding it up on cache
1359 line size multiple. */
1360 volume += L1_CACHE_LINE_SIZE / ref->prefetch_mod;
1361 }
1362 return volume;
1363 }
1364
1365 /* Returns the volume of memory references accessed across VEC iterations of
1366 loops, whose sizes are described in the LOOP_SIZES array. N is the number
1367 of the loops in the nest (length of VEC and LOOP_SIZES vectors). */
1368
1369 static unsigned
1370 volume_of_dist_vector (lambda_vector vec, unsigned *loop_sizes, unsigned n)
1371 {
1372 unsigned i;
1373
1374 for (i = 0; i < n; i++)
1375 if (vec[i] != 0)
1376 break;
1377
1378 if (i == n)
1379 return 0;
1380
1381 gcc_assert (vec[i] > 0);
1382
1383 /* We ignore the parts of the distance vector in subloops, since usually
1384 the numbers of iterations are much smaller. */
1385 return loop_sizes[i] * vec[i];
1386 }
1387
1388 /* Add the steps of ACCESS_FN multiplied by STRIDE to the array STRIDE
1389 at the position corresponding to the loop of the step. N is the depth
1390 of the considered loop nest, and, LOOP is its innermost loop. */
1391
1392 static void
1393 add_subscript_strides (tree access_fn, unsigned stride,
1394 HOST_WIDE_INT *strides, unsigned n, struct loop *loop)
1395 {
1396 struct loop *aloop;
1397 tree step;
1398 HOST_WIDE_INT astep;
1399 unsigned min_depth = loop_depth (loop) - n;
1400
1401 while (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
1402 {
1403 aloop = get_chrec_loop (access_fn);
1404 step = CHREC_RIGHT (access_fn);
1405 access_fn = CHREC_LEFT (access_fn);
1406
1407 if ((unsigned) loop_depth (aloop) <= min_depth)
1408 continue;
1409
1410 if (host_integerp (step, 0))
1411 astep = tree_low_cst (step, 0);
1412 else
1413 astep = L1_CACHE_LINE_SIZE;
1414
1415 strides[n - 1 - loop_depth (loop) + loop_depth (aloop)] += astep * stride;
1416
1417 }
1418 }
1419
1420 /* Returns the volume of memory references accessed between two consecutive
1421 self-reuses of the reference DR. We consider the subscripts of DR in N
1422 loops, and LOOP_SIZES contains the volumes of accesses in each of the
1423 loops. LOOP is the innermost loop of the current loop nest. */
1424
1425 static unsigned
1426 self_reuse_distance (data_reference_p dr, unsigned *loop_sizes, unsigned n,
1427 struct loop *loop)
1428 {
1429 tree stride, access_fn;
1430 HOST_WIDE_INT *strides, astride;
1431 VEC (tree, heap) *access_fns;
1432 tree ref = DR_REF (dr);
1433 unsigned i, ret = ~0u;
1434
1435 /* In the following example:
1436
1437 for (i = 0; i < N; i++)
1438 for (j = 0; j < N; j++)
1439 use (a[j][i]);
1440 the same cache line is accessed each N steps (except if the change from
1441 i to i + 1 crosses the boundary of the cache line). Thus, for self-reuse,
1442 we cannot rely purely on the results of the data dependence analysis.
1443
1444 Instead, we compute the stride of the reference in each loop, and consider
1445 the innermost loop in that the stride is less than cache size. */
1446
1447 strides = XCNEWVEC (HOST_WIDE_INT, n);
1448 access_fns = DR_ACCESS_FNS (dr);
1449
1450 FOR_EACH_VEC_ELT (tree, access_fns, i, access_fn)
1451 {
1452 /* Keep track of the reference corresponding to the subscript, so that we
1453 know its stride. */
1454 while (handled_component_p (ref) && TREE_CODE (ref) != ARRAY_REF)
1455 ref = TREE_OPERAND (ref, 0);
1456
1457 if (TREE_CODE (ref) == ARRAY_REF)
1458 {
1459 stride = TYPE_SIZE_UNIT (TREE_TYPE (ref));
1460 if (host_integerp (stride, 1))
1461 astride = tree_low_cst (stride, 1);
1462 else
1463 astride = L1_CACHE_LINE_SIZE;
1464
1465 ref = TREE_OPERAND (ref, 0);
1466 }
1467 else
1468 astride = 1;
1469
1470 add_subscript_strides (access_fn, astride, strides, n, loop);
1471 }
1472
1473 for (i = n; i-- > 0; )
1474 {
1475 unsigned HOST_WIDE_INT s;
1476
1477 s = strides[i] < 0 ? -strides[i] : strides[i];
1478
1479 if (s < (unsigned) L1_CACHE_LINE_SIZE
1480 && (loop_sizes[i]
1481 > (unsigned) (L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION)))
1482 {
1483 ret = loop_sizes[i];
1484 break;
1485 }
1486 }
1487
1488 free (strides);
1489 return ret;
1490 }
1491
1492 /* Determines the distance till the first reuse of each reference in REFS
1493 in the loop nest of LOOP. NO_OTHER_REFS is true if there are no other
1494 memory references in the loop. Return false if the analysis fails. */
1495
1496 static bool
1497 determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
1498 bool no_other_refs)
1499 {
1500 struct loop *nest, *aloop;
1501 VEC (data_reference_p, heap) *datarefs = NULL;
1502 VEC (ddr_p, heap) *dependences = NULL;
1503 struct mem_ref_group *gr;
1504 struct mem_ref *ref, *refb;
1505 VEC (loop_p, heap) *vloops = NULL;
1506 unsigned *loop_data_size;
1507 unsigned i, j, n;
1508 unsigned volume, dist, adist;
1509 HOST_WIDE_INT vol;
1510 data_reference_p dr;
1511 ddr_p dep;
1512
1513 if (loop->inner)
1514 return true;
1515
1516 /* Find the outermost loop of the loop nest of loop (we require that
1517 there are no sibling loops inside the nest). */
1518 nest = loop;
1519 while (1)
1520 {
1521 aloop = loop_outer (nest);
1522
1523 if (aloop == current_loops->tree_root
1524 || aloop->inner->next)
1525 break;
1526
1527 nest = aloop;
1528 }
1529
1530 /* For each loop, determine the amount of data accessed in each iteration.
1531 We use this to estimate whether the reference is evicted from the
1532 cache before its reuse. */
1533 find_loop_nest (nest, &vloops);
1534 n = VEC_length (loop_p, vloops);
1535 loop_data_size = XNEWVEC (unsigned, n);
1536 volume = volume_of_references (refs);
1537 i = n;
1538 while (i-- != 0)
1539 {
1540 loop_data_size[i] = volume;
1541 /* Bound the volume by the L2 cache size, since above this bound,
1542 all dependence distances are equivalent. */
1543 if (volume > L2_CACHE_SIZE_BYTES)
1544 continue;
1545
1546 aloop = VEC_index (loop_p, vloops, i);
1547 vol = estimated_stmt_executions_int (aloop);
1548 if (vol == -1)
1549 vol = expected_loop_iterations (aloop);
1550 volume *= vol;
1551 }
1552
1553 /* Prepare the references in the form suitable for data dependence
1554 analysis. We ignore unanalyzable data references (the results
1555 are used just as a heuristics to estimate temporality of the
1556 references, hence we do not need to worry about correctness). */
1557 for (gr = refs; gr; gr = gr->next)
1558 for (ref = gr->refs; ref; ref = ref->next)
1559 {
1560 dr = create_data_ref (nest, loop_containing_stmt (ref->stmt),
1561 ref->mem, ref->stmt, !ref->write_p);
1562
1563 if (dr)
1564 {
1565 ref->reuse_distance = volume;
1566 dr->aux = ref;
1567 VEC_safe_push (data_reference_p, heap, datarefs, dr);
1568 }
1569 else
1570 no_other_refs = false;
1571 }
1572
1573 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
1574 {
1575 dist = self_reuse_distance (dr, loop_data_size, n, loop);
1576 ref = (struct mem_ref *) dr->aux;
1577 if (ref->reuse_distance > dist)
1578 ref->reuse_distance = dist;
1579
1580 if (no_other_refs)
1581 ref->independent_p = true;
1582 }
1583
1584 if (!compute_all_dependences (datarefs, &dependences, vloops, true))
1585 return false;
1586
1587 FOR_EACH_VEC_ELT (ddr_p, dependences, i, dep)
1588 {
1589 if (DDR_ARE_DEPENDENT (dep) == chrec_known)
1590 continue;
1591
1592 ref = (struct mem_ref *) DDR_A (dep)->aux;
1593 refb = (struct mem_ref *) DDR_B (dep)->aux;
1594
1595 if (DDR_ARE_DEPENDENT (dep) == chrec_dont_know
1596 || DDR_NUM_DIST_VECTS (dep) == 0)
1597 {
1598 /* If the dependence cannot be analyzed, assume that there might be
1599 a reuse. */
1600 dist = 0;
1601
1602 ref->independent_p = false;
1603 refb->independent_p = false;
1604 }
1605 else
1606 {
1607 /* The distance vectors are normalized to be always lexicographically
1608 positive, hence we cannot tell just from them whether DDR_A comes
1609 before DDR_B or vice versa. However, it is not important,
1610 anyway -- if DDR_A is close to DDR_B, then it is either reused in
1611 DDR_B (and it is not nontemporal), or it reuses the value of DDR_B
1612 in cache (and marking it as nontemporal would not affect
1613 anything). */
1614
1615 dist = volume;
1616 for (j = 0; j < DDR_NUM_DIST_VECTS (dep); j++)
1617 {
1618 adist = volume_of_dist_vector (DDR_DIST_VECT (dep, j),
1619 loop_data_size, n);
1620
1621 /* If this is a dependence in the innermost loop (i.e., the
1622 distances in all superloops are zero) and it is not
1623 the trivial self-dependence with distance zero, record that
1624 the references are not completely independent. */
1625 if (lambda_vector_zerop (DDR_DIST_VECT (dep, j), n - 1)
1626 && (ref != refb
1627 || DDR_DIST_VECT (dep, j)[n-1] != 0))
1628 {
1629 ref->independent_p = false;
1630 refb->independent_p = false;
1631 }
1632
1633 /* Ignore accesses closer than
1634 L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
1635 so that we use nontemporal prefetches e.g. if single memory
1636 location is accessed several times in a single iteration of
1637 the loop. */
1638 if (adist < L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION)
1639 continue;
1640
1641 if (adist < dist)
1642 dist = adist;
1643 }
1644 }
1645
1646 if (ref->reuse_distance > dist)
1647 ref->reuse_distance = dist;
1648 if (refb->reuse_distance > dist)
1649 refb->reuse_distance = dist;
1650 }
1651
1652 free_dependence_relations (dependences);
1653 free_data_refs (datarefs);
1654 free (loop_data_size);
1655
1656 if (dump_file && (dump_flags & TDF_DETAILS))
1657 {
1658 fprintf (dump_file, "Reuse distances:\n");
1659 for (gr = refs; gr; gr = gr->next)
1660 for (ref = gr->refs; ref; ref = ref->next)
1661 fprintf (dump_file, " ref %p distance %u\n",
1662 (void *) ref, ref->reuse_distance);
1663 }
1664
1665 return true;
1666 }
1667
1668 /* Determine whether or not the trip count to ahead ratio is too small based
1669 on prefitablility consideration.
1670 AHEAD: the iteration ahead distance,
1671 EST_NITER: the estimated trip count. */
1672
1673 static bool
1674 trip_count_to_ahead_ratio_too_small_p (unsigned ahead, HOST_WIDE_INT est_niter)
1675 {
1676 /* Assume trip count to ahead ratio is big enough if the trip count could not
1677 be estimated at compile time. */
1678 if (est_niter < 0)
1679 return false;
1680
1681 if (est_niter < (HOST_WIDE_INT) (TRIP_COUNT_TO_AHEAD_RATIO * ahead))
1682 {
1683 if (dump_file && (dump_flags & TDF_DETAILS))
1684 fprintf (dump_file,
1685 "Not prefetching -- loop estimated to roll only %d times\n",
1686 (int) est_niter);
1687 return true;
1688 }
1689
1690 return false;
1691 }
1692
1693 /* Determine whether or not the number of memory references in the loop is
1694 reasonable based on the profitablity and compilation time considerations.
1695 NINSNS: estimated number of instructions in the loop,
1696 MEM_REF_COUNT: total number of memory references in the loop. */
1697
1698 static bool
1699 mem_ref_count_reasonable_p (unsigned ninsns, unsigned mem_ref_count)
1700 {
1701 int insn_to_mem_ratio;
1702
1703 if (mem_ref_count == 0)
1704 return false;
1705
1706 /* Miss rate computation (is_miss_rate_acceptable) and dependence analysis
1707 (compute_all_dependences) have high costs based on quadratic complexity.
1708 To avoid huge compilation time, we give up prefetching if mem_ref_count
1709 is too large. */
1710 if (mem_ref_count > PREFETCH_MAX_MEM_REFS_PER_LOOP)
1711 return false;
1712
1713 /* Prefetching improves performance by overlapping cache missing
1714 memory accesses with CPU operations. If the loop does not have
1715 enough CPU operations to overlap with memory operations, prefetching
1716 won't give a significant benefit. One approximate way of checking
1717 this is to require the ratio of instructions to memory references to
1718 be above a certain limit. This approximation works well in practice.
1719 TODO: Implement a more precise computation by estimating the time
1720 for each CPU or memory op in the loop. Time estimates for memory ops
1721 should account for cache misses. */
1722 insn_to_mem_ratio = ninsns / mem_ref_count;
1723
1724 if (insn_to_mem_ratio < PREFETCH_MIN_INSN_TO_MEM_RATIO)
1725 {
1726 if (dump_file && (dump_flags & TDF_DETAILS))
1727 fprintf (dump_file,
1728 "Not prefetching -- instruction to memory reference ratio (%d) too small\n",
1729 insn_to_mem_ratio);
1730 return false;
1731 }
1732
1733 return true;
1734 }
1735
1736 /* Determine whether or not the instruction to prefetch ratio in the loop is
1737 too small based on the profitablity consideration.
1738 NINSNS: estimated number of instructions in the loop,
1739 PREFETCH_COUNT: an estimate of the number of prefetches,
1740 UNROLL_FACTOR: the factor to unroll the loop if prefetching. */
1741
1742 static bool
1743 insn_to_prefetch_ratio_too_small_p (unsigned ninsns, unsigned prefetch_count,
1744 unsigned unroll_factor)
1745 {
1746 int insn_to_prefetch_ratio;
1747
1748 /* Prefetching most likely causes performance degradation when the instruction
1749 to prefetch ratio is too small. Too many prefetch instructions in a loop
1750 may reduce the I-cache performance.
1751 (unroll_factor * ninsns) is used to estimate the number of instructions in
1752 the unrolled loop. This implementation is a bit simplistic -- the number
1753 of issued prefetch instructions is also affected by unrolling. So,
1754 prefetch_mod and the unroll factor should be taken into account when
1755 determining prefetch_count. Also, the number of insns of the unrolled
1756 loop will usually be significantly smaller than the number of insns of the
1757 original loop * unroll_factor (at least the induction variable increases
1758 and the exit branches will get eliminated), so it might be better to use
1759 tree_estimate_loop_size + estimated_unrolled_size. */
1760 insn_to_prefetch_ratio = (unroll_factor * ninsns) / prefetch_count;
1761 if (insn_to_prefetch_ratio < MIN_INSN_TO_PREFETCH_RATIO)
1762 {
1763 if (dump_file && (dump_flags & TDF_DETAILS))
1764 fprintf (dump_file,
1765 "Not prefetching -- instruction to prefetch ratio (%d) too small\n",
1766 insn_to_prefetch_ratio);
1767 return true;
1768 }
1769
1770 return false;
1771 }
1772
1773
1774 /* Issue prefetch instructions for array references in LOOP. Returns
1775 true if the LOOP was unrolled. */
1776
1777 static bool
1778 loop_prefetch_arrays (struct loop *loop)
1779 {
1780 struct mem_ref_group *refs;
1781 unsigned ahead, ninsns, time, unroll_factor;
1782 HOST_WIDE_INT est_niter;
1783 struct tree_niter_desc desc;
1784 bool unrolled = false, no_other_refs;
1785 unsigned prefetch_count;
1786 unsigned mem_ref_count;
1787
1788 if (optimize_loop_nest_for_size_p (loop))
1789 {
1790 if (dump_file && (dump_flags & TDF_DETAILS))
1791 fprintf (dump_file, " ignored (cold area)\n");
1792 return false;
1793 }
1794
1795 /* FIXME: the time should be weighted by the probabilities of the blocks in
1796 the loop body. */
1797 time = tree_num_loop_insns (loop, &eni_time_weights);
1798 if (time == 0)
1799 return false;
1800
1801 ahead = (PREFETCH_LATENCY + time - 1) / time;
1802 est_niter = estimated_stmt_executions_int (loop);
1803 if (est_niter == -1)
1804 est_niter = max_stmt_executions_int (loop);
1805
1806 /* Prefetching is not likely to be profitable if the trip count to ahead
1807 ratio is too small. */
1808 if (trip_count_to_ahead_ratio_too_small_p (ahead, est_niter))
1809 return false;
1810
1811 ninsns = tree_num_loop_insns (loop, &eni_size_weights);
1812
1813 /* Step 1: gather the memory references. */
1814 refs = gather_memory_references (loop, &no_other_refs, &mem_ref_count);
1815
1816 /* Give up prefetching if the number of memory references in the
1817 loop is not reasonable based on profitablity and compilation time
1818 considerations. */
1819 if (!mem_ref_count_reasonable_p (ninsns, mem_ref_count))
1820 goto fail;
1821
1822 /* Step 2: estimate the reuse effects. */
1823 prune_by_reuse (refs);
1824
1825 if (nothing_to_prefetch_p (refs))
1826 goto fail;
1827
1828 if (!determine_loop_nest_reuse (loop, refs, no_other_refs))
1829 goto fail;
1830
1831 /* Step 3: determine unroll factor. */
1832 unroll_factor = determine_unroll_factor (loop, refs, ninsns, &desc,
1833 est_niter);
1834
1835 /* Estimate prefetch count for the unrolled loop. */
1836 prefetch_count = estimate_prefetch_count (refs, unroll_factor);
1837 if (prefetch_count == 0)
1838 goto fail;
1839
1840 if (dump_file && (dump_flags & TDF_DETAILS))
1841 fprintf (dump_file, "Ahead %d, unroll factor %d, trip count "
1842 HOST_WIDE_INT_PRINT_DEC "\n"
1843 "insn count %d, mem ref count %d, prefetch count %d\n",
1844 ahead, unroll_factor, est_niter,
1845 ninsns, mem_ref_count, prefetch_count);
1846
1847 /* Prefetching is not likely to be profitable if the instruction to prefetch
1848 ratio is too small. */
1849 if (insn_to_prefetch_ratio_too_small_p (ninsns, prefetch_count,
1850 unroll_factor))
1851 goto fail;
1852
1853 mark_nontemporal_stores (loop, refs);
1854
1855 /* Step 4: what to prefetch? */
1856 if (!schedule_prefetches (refs, unroll_factor, ahead))
1857 goto fail;
1858
1859 /* Step 5: unroll the loop. TODO -- peeling of first and last few
1860 iterations so that we do not issue superfluous prefetches. */
1861 if (unroll_factor != 1)
1862 {
1863 tree_unroll_loop (loop, unroll_factor,
1864 single_dom_exit (loop), &desc);
1865 unrolled = true;
1866 }
1867
1868 /* Step 6: issue the prefetches. */
1869 issue_prefetches (refs, unroll_factor, ahead);
1870
1871 fail:
1872 release_mem_refs (refs);
1873 return unrolled;
1874 }
1875
1876 /* Issue prefetch instructions for array references in loops. */
1877
1878 unsigned int
1879 tree_ssa_prefetch_arrays (void)
1880 {
1881 loop_iterator li;
1882 struct loop *loop;
1883 bool unrolled = false;
1884 int todo_flags = 0;
1885
1886 if (!HAVE_prefetch
1887 /* It is possible to ask compiler for say -mtune=i486 -march=pentium4.
1888 -mtune=i486 causes us having PREFETCH_BLOCK 0, since this is part
1889 of processor costs and i486 does not have prefetch, but
1890 -march=pentium4 causes HAVE_prefetch to be true. Ugh. */
1891 || PREFETCH_BLOCK == 0)
1892 return 0;
1893
1894 if (dump_file && (dump_flags & TDF_DETAILS))
1895 {
1896 fprintf (dump_file, "Prefetching parameters:\n");
1897 fprintf (dump_file, " simultaneous prefetches: %d\n",
1898 SIMULTANEOUS_PREFETCHES);
1899 fprintf (dump_file, " prefetch latency: %d\n", PREFETCH_LATENCY);
1900 fprintf (dump_file, " prefetch block size: %d\n", PREFETCH_BLOCK);
1901 fprintf (dump_file, " L1 cache size: %d lines, %d kB\n",
1902 L1_CACHE_SIZE_BYTES / L1_CACHE_LINE_SIZE, L1_CACHE_SIZE);
1903 fprintf (dump_file, " L1 cache line size: %d\n", L1_CACHE_LINE_SIZE);
1904 fprintf (dump_file, " L2 cache size: %d kB\n", L2_CACHE_SIZE);
1905 fprintf (dump_file, " min insn-to-prefetch ratio: %d \n",
1906 MIN_INSN_TO_PREFETCH_RATIO);
1907 fprintf (dump_file, " min insn-to-mem ratio: %d \n",
1908 PREFETCH_MIN_INSN_TO_MEM_RATIO);
1909 fprintf (dump_file, "\n");
1910 }
1911
1912 initialize_original_copy_tables ();
1913
1914 if (!builtin_decl_explicit_p (BUILT_IN_PREFETCH))
1915 {
1916 tree type = build_function_type_list (void_type_node,
1917 const_ptr_type_node, NULL_TREE);
1918 tree decl = add_builtin_function ("__builtin_prefetch", type,
1919 BUILT_IN_PREFETCH, BUILT_IN_NORMAL,
1920 NULL, NULL_TREE);
1921 DECL_IS_NOVOPS (decl) = true;
1922 set_builtin_decl (BUILT_IN_PREFETCH, decl, false);
1923 }
1924
1925 /* We assume that size of cache line is a power of two, so verify this
1926 here. */
1927 gcc_assert ((PREFETCH_BLOCK & (PREFETCH_BLOCK - 1)) == 0);
1928
1929 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1930 {
1931 if (dump_file && (dump_flags & TDF_DETAILS))
1932 fprintf (dump_file, "Processing loop %d:\n", loop->num);
1933
1934 unrolled |= loop_prefetch_arrays (loop);
1935
1936 if (dump_file && (dump_flags & TDF_DETAILS))
1937 fprintf (dump_file, "\n\n");
1938 }
1939
1940 if (unrolled)
1941 {
1942 scev_reset ();
1943 todo_flags |= TODO_cleanup_cfg;
1944 }
1945
1946 free_original_copy_tables ();
1947 return todo_flags;
1948 }