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