2 Copyright (C) 2005-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
26 #include "basic-block.h"
27 #include "tree-pretty-print.h"
30 #include "gimple-iterator.h"
31 #include "gimplify-me.h"
32 #include "gimple-ssa.h"
33 #include "tree-ssa-loop-ivopts.h"
34 #include "tree-ssa-loop-manip.h"
35 #include "tree-ssa-loop-niter.h"
36 #include "tree-ssa-loop.h"
37 #include "tree-into-ssa.h"
39 #include "tree-pass.h"
40 #include "insn-config.h"
42 #include "tree-chrec.h"
43 #include "tree-scalar-evolution.h"
44 #include "diagnostic-core.h"
46 #include "langhooks.h"
47 #include "tree-inline.h"
48 #include "tree-data-ref.h"
51 /* FIXME: Needed for optabs, but this should all be moved to a TBD interface
52 between the GIMPLE and RTL worlds. */
57 /* This pass inserts prefetch instructions to optimize cache usage during
58 accesses to arrays in loops. It processes loops sequentially and:
60 1) Gathers all memory references in the single loop.
61 2) For each of the references it decides when it is profitable to prefetch
62 it. To do it, we evaluate the reuse among the accesses, and determines
63 two values: PREFETCH_BEFORE (meaning that it only makes sense to do
64 prefetching in the first PREFETCH_BEFORE iterations of the loop) and
65 PREFETCH_MOD (meaning that it only makes sense to prefetch in the
66 iterations of the loop that are zero modulo PREFETCH_MOD). For example
67 (assuming cache line size is 64 bytes, char has size 1 byte and there
68 is no hardware sequential prefetch):
71 for (i = 0; i < max; i++)
78 a[187*i + 50] = ...; (5)
81 (0) obviously has PREFETCH_BEFORE 1
82 (1) has PREFETCH_BEFORE 64, since (2) accesses the same memory
83 location 64 iterations before it, and PREFETCH_MOD 64 (since
84 it hits the same cache line otherwise).
85 (2) has PREFETCH_MOD 64
86 (3) has PREFETCH_MOD 4
87 (4) has PREFETCH_MOD 1. We do not set PREFETCH_BEFORE here, since
88 the cache line accessed by (5) is the same with probability only
90 (5) has PREFETCH_MOD 1 as well.
92 Additionally, we use data dependence analysis to determine for each
93 reference the distance till the first reuse; this information is used
94 to determine the temporality of the issued prefetch instruction.
96 3) We determine how much ahead we need to prefetch. The number of
97 iterations needed is time to fetch / time spent in one iteration of
98 the loop. The problem is that we do not know either of these values,
99 so we just make a heuristic guess based on a magic (possibly)
100 target-specific constant and size of the loop.
102 4) Determine which of the references we prefetch. We take into account
103 that there is a maximum number of simultaneous prefetches (provided
104 by machine description). We prefetch as many prefetches as possible
105 while still within this bound (starting with those with lowest
106 prefetch_mod, since they are responsible for most of the cache
109 5) We unroll and peel loops so that we are able to satisfy PREFETCH_MOD
110 and PREFETCH_BEFORE requirements (within some bounds), and to avoid
111 prefetching nonaccessed memory.
112 TODO -- actually implement peeling.
114 6) We actually emit the prefetch instructions. ??? Perhaps emit the
115 prefetch instructions with guards in cases where 5) was not sufficient
116 to satisfy the constraints?
118 A cost model is implemented to determine whether or not prefetching is
119 profitable for a given loop. The cost model has three heuristics:
121 1. Function trip_count_to_ahead_ratio_too_small_p implements a
122 heuristic that determines whether or not the loop has too few
123 iterations (compared to ahead). Prefetching is not likely to be
124 beneficial if the trip count to ahead ratio is below a certain
127 2. Function mem_ref_count_reasonable_p implements a heuristic that
128 determines whether the given loop has enough CPU ops that can be
129 overlapped with cache missing memory ops. If not, the loop
130 won't benefit from prefetching. In the implementation,
131 prefetching is not considered beneficial if the ratio between
132 the instruction count and the mem ref count is below a certain
135 3. Function insn_to_prefetch_ratio_too_small_p implements a
136 heuristic that disables prefetching in a loop if the prefetching
137 cost is above a certain limit. The relative prefetching cost is
138 estimated by taking the ratio between the prefetch count and the
139 total intruction count (this models the I-cache cost).
141 The limits used in these heuristics are defined as parameters with
142 reasonable default values. Machine-specific default values will be
146 -- write and use more general reuse analysis (that could be also used
147 in other cache aimed loop optimizations)
148 -- make it behave sanely together with the prefetches given by user
149 (now we just ignore them; at the very least we should avoid
150 optimizing loops in that user put his own prefetches)
151 -- we assume cache line size alignment of arrays; this could be
154 /* Magic constants follow. These should be replaced by machine specific
157 /* True if write can be prefetched by a read prefetch. */
159 #ifndef WRITE_CAN_USE_READ_PREFETCH
160 #define WRITE_CAN_USE_READ_PREFETCH 1
163 /* True if read can be prefetched by a write prefetch. */
165 #ifndef READ_CAN_USE_WRITE_PREFETCH
166 #define READ_CAN_USE_WRITE_PREFETCH 0
169 /* The size of the block loaded by a single prefetch. Usually, this is
170 the same as cache line size (at the moment, we only consider one level
171 of cache hierarchy). */
173 #ifndef PREFETCH_BLOCK
174 #define PREFETCH_BLOCK L1_CACHE_LINE_SIZE
177 /* Do we have a forward hardware sequential prefetching? */
179 #ifndef HAVE_FORWARD_PREFETCH
180 #define HAVE_FORWARD_PREFETCH 0
183 /* Do we have a backward hardware sequential prefetching? */
185 #ifndef HAVE_BACKWARD_PREFETCH
186 #define HAVE_BACKWARD_PREFETCH 0
189 /* In some cases we are only able to determine that there is a certain
190 probability that the two accesses hit the same cache line. In this
191 case, we issue the prefetches for both of them if this probability
192 is less then (1000 - ACCEPTABLE_MISS_RATE) per thousand. */
194 #ifndef ACCEPTABLE_MISS_RATE
195 #define ACCEPTABLE_MISS_RATE 50
198 #ifndef HAVE_prefetch
199 #define HAVE_prefetch 0
202 #define L1_CACHE_SIZE_BYTES ((unsigned) (L1_CACHE_SIZE * 1024))
203 #define L2_CACHE_SIZE_BYTES ((unsigned) (L2_CACHE_SIZE * 1024))
205 /* We consider a memory access nontemporal if it is not reused sooner than
206 after L2_CACHE_SIZE_BYTES of memory are accessed. However, we ignore
207 accesses closer than L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
208 so that we use nontemporal prefetches e.g. if single memory location
209 is accessed several times in a single iteration of the loop. */
210 #define NONTEMPORAL_FRACTION 16
212 /* In case we have to emit a memory fence instruction after the loop that
213 uses nontemporal stores, this defines the builtin to use. */
215 #ifndef FENCE_FOLLOWING_MOVNT
216 #define FENCE_FOLLOWING_MOVNT NULL_TREE
219 /* It is not profitable to prefetch when the trip count is not at
220 least TRIP_COUNT_TO_AHEAD_RATIO times the prefetch ahead distance.
221 For example, in a loop with a prefetch ahead distance of 10,
222 supposing that TRIP_COUNT_TO_AHEAD_RATIO is equal to 4, it is
223 profitable to prefetch when the trip count is greater or equal to
224 40. In that case, 30 out of the 40 iterations will benefit from
227 #ifndef TRIP_COUNT_TO_AHEAD_RATIO
228 #define TRIP_COUNT_TO_AHEAD_RATIO 4
231 /* The group of references between that reuse may occur. */
235 tree base
; /* Base of the reference. */
236 tree step
; /* Step of the reference. */
237 struct mem_ref
*refs
; /* References in the group. */
238 struct mem_ref_group
*next
; /* Next group of references. */
241 /* Assigned to PREFETCH_BEFORE when all iterations are to be prefetched. */
243 #define PREFETCH_ALL (~(unsigned HOST_WIDE_INT) 0)
245 /* Do not generate a prefetch if the unroll factor is significantly less
246 than what is required by the prefetch. This is to avoid redundant
247 prefetches. For example, when prefetch_mod is 16 and unroll_factor is
248 2, prefetching requires unrolling the loop 16 times, but
249 the loop is actually unrolled twice. In this case (ratio = 8),
250 prefetching is not likely to be beneficial. */
252 #ifndef PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
253 #define PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO 4
256 /* Some of the prefetch computations have quadratic complexity. We want to
257 avoid huge compile times and, therefore, want to limit the amount of
258 memory references per loop where we consider prefetching. */
260 #ifndef PREFETCH_MAX_MEM_REFS_PER_LOOP
261 #define PREFETCH_MAX_MEM_REFS_PER_LOOP 200
264 /* The memory reference. */
268 gimple stmt
; /* Statement in that the reference appears. */
269 tree mem
; /* The reference. */
270 HOST_WIDE_INT delta
; /* Constant offset of the reference. */
271 struct mem_ref_group
*group
; /* The group of references it belongs to. */
272 unsigned HOST_WIDE_INT prefetch_mod
;
273 /* Prefetch only each PREFETCH_MOD-th
275 unsigned HOST_WIDE_INT prefetch_before
;
276 /* Prefetch only first PREFETCH_BEFORE
278 unsigned reuse_distance
; /* The amount of data accessed before the first
279 reuse of this value. */
280 struct mem_ref
*next
; /* The next reference in the group. */
281 unsigned write_p
: 1; /* Is it a write? */
282 unsigned independent_p
: 1; /* True if the reference is independent on
283 all other references inside the loop. */
284 unsigned issue_prefetch_p
: 1; /* Should we really issue the prefetch? */
285 unsigned storent_p
: 1; /* True if we changed the store to a
289 /* Dumps information about memory reference */
291 dump_mem_details (FILE *file
, tree base
, tree step
,
292 HOST_WIDE_INT delta
, bool write_p
)
294 fprintf (file
, "(base ");
295 print_generic_expr (file
, base
, TDF_SLIM
);
296 fprintf (file
, ", step ");
297 if (cst_and_fits_in_hwi (step
))
298 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, int_cst_value (step
));
300 print_generic_expr (file
, step
, TDF_TREE
);
301 fprintf (file
, ")\n");
302 fprintf (file
, " delta ");
303 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, delta
);
304 fprintf (file
, "\n");
305 fprintf (file
, " %s\n", write_p
? "write" : "read");
306 fprintf (file
, "\n");
309 /* Dumps information about reference REF to FILE. */
312 dump_mem_ref (FILE *file
, struct mem_ref
*ref
)
314 fprintf (file
, "Reference %p:\n", (void *) ref
);
316 fprintf (file
, " group %p ", (void *) ref
->group
);
318 dump_mem_details (file
, ref
->group
->base
, ref
->group
->step
, ref
->delta
,
322 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
325 static struct mem_ref_group
*
326 find_or_create_group (struct mem_ref_group
**groups
, tree base
, tree step
)
328 struct mem_ref_group
*group
;
330 for (; *groups
; groups
= &(*groups
)->next
)
332 if (operand_equal_p ((*groups
)->step
, step
, 0)
333 && operand_equal_p ((*groups
)->base
, base
, 0))
336 /* If step is an integer constant, keep the list of groups sorted
337 by decreasing step. */
338 if (cst_and_fits_in_hwi ((*groups
)->step
) && cst_and_fits_in_hwi (step
)
339 && int_cst_value ((*groups
)->step
) < int_cst_value (step
))
343 group
= XNEW (struct mem_ref_group
);
347 group
->next
= *groups
;
353 /* Records a memory reference MEM in GROUP with offset DELTA and write status
354 WRITE_P. The reference occurs in statement STMT. */
357 record_ref (struct mem_ref_group
*group
, gimple stmt
, tree mem
,
358 HOST_WIDE_INT delta
, bool write_p
)
360 struct mem_ref
**aref
;
362 /* Do not record the same address twice. */
363 for (aref
= &group
->refs
; *aref
; aref
= &(*aref
)->next
)
365 /* It does not have to be possible for write reference to reuse the read
366 prefetch, or vice versa. */
367 if (!WRITE_CAN_USE_READ_PREFETCH
369 && !(*aref
)->write_p
)
371 if (!READ_CAN_USE_WRITE_PREFETCH
376 if ((*aref
)->delta
== delta
)
380 (*aref
) = XNEW (struct mem_ref
);
381 (*aref
)->stmt
= stmt
;
383 (*aref
)->delta
= delta
;
384 (*aref
)->write_p
= write_p
;
385 (*aref
)->prefetch_before
= PREFETCH_ALL
;
386 (*aref
)->prefetch_mod
= 1;
387 (*aref
)->reuse_distance
= 0;
388 (*aref
)->issue_prefetch_p
= false;
389 (*aref
)->group
= group
;
390 (*aref
)->next
= NULL
;
391 (*aref
)->independent_p
= false;
392 (*aref
)->storent_p
= false;
394 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
395 dump_mem_ref (dump_file
, *aref
);
398 /* Release memory references in GROUPS. */
401 release_mem_refs (struct mem_ref_group
*groups
)
403 struct mem_ref_group
*next_g
;
404 struct mem_ref
*ref
, *next_r
;
406 for (; groups
; groups
= next_g
)
408 next_g
= groups
->next
;
409 for (ref
= groups
->refs
; ref
; ref
= next_r
)
418 /* A structure used to pass arguments to idx_analyze_ref. */
422 struct loop
*loop
; /* Loop of the reference. */
423 gimple stmt
; /* Statement of the reference. */
424 tree
*step
; /* Step of the memory reference. */
425 HOST_WIDE_INT
*delta
; /* Offset of the memory reference. */
428 /* Analyzes a single INDEX of a memory reference to obtain information
429 described at analyze_ref. Callback for for_each_index. */
432 idx_analyze_ref (tree base
, tree
*index
, void *data
)
434 struct ar_data
*ar_data
= (struct ar_data
*) data
;
435 tree ibase
, step
, stepsize
;
436 HOST_WIDE_INT idelta
= 0, imult
= 1;
439 if (!simple_iv (ar_data
->loop
, loop_containing_stmt (ar_data
->stmt
),
445 if (TREE_CODE (ibase
) == POINTER_PLUS_EXPR
446 && cst_and_fits_in_hwi (TREE_OPERAND (ibase
, 1)))
448 idelta
= int_cst_value (TREE_OPERAND (ibase
, 1));
449 ibase
= TREE_OPERAND (ibase
, 0);
451 if (cst_and_fits_in_hwi (ibase
))
453 idelta
+= int_cst_value (ibase
);
454 ibase
= build_int_cst (TREE_TYPE (ibase
), 0);
457 if (TREE_CODE (base
) == ARRAY_REF
)
459 stepsize
= array_ref_element_size (base
);
460 if (!cst_and_fits_in_hwi (stepsize
))
462 imult
= int_cst_value (stepsize
);
463 step
= fold_build2 (MULT_EXPR
, sizetype
,
464 fold_convert (sizetype
, step
),
465 fold_convert (sizetype
, stepsize
));
469 if (*ar_data
->step
== NULL_TREE
)
470 *ar_data
->step
= step
;
472 *ar_data
->step
= fold_build2 (PLUS_EXPR
, sizetype
,
473 fold_convert (sizetype
, *ar_data
->step
),
474 fold_convert (sizetype
, step
));
475 *ar_data
->delta
+= idelta
;
481 /* Tries to express REF_P in shape &BASE + STEP * iter + DELTA, where DELTA and
482 STEP are integer constants and iter is number of iterations of LOOP. The
483 reference occurs in statement STMT. Strips nonaddressable component
484 references from REF_P. */
487 analyze_ref (struct loop
*loop
, tree
*ref_p
, tree
*base
,
488 tree
*step
, HOST_WIDE_INT
*delta
,
491 struct ar_data ar_data
;
493 HOST_WIDE_INT bit_offset
;
499 /* First strip off the component references. Ignore bitfields.
500 Also strip off the real and imagine parts of a complex, so that
501 they can have the same base. */
502 if (TREE_CODE (ref
) == REALPART_EXPR
503 || TREE_CODE (ref
) == IMAGPART_EXPR
504 || (TREE_CODE (ref
) == COMPONENT_REF
505 && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref
, 1))))
507 if (TREE_CODE (ref
) == IMAGPART_EXPR
)
508 *delta
+= int_size_in_bytes (TREE_TYPE (ref
));
509 ref
= TREE_OPERAND (ref
, 0);
514 for (; TREE_CODE (ref
) == COMPONENT_REF
; ref
= TREE_OPERAND (ref
, 0))
516 off
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
517 bit_offset
= TREE_INT_CST_LOW (off
);
518 gcc_assert (bit_offset
% BITS_PER_UNIT
== 0);
520 *delta
+= bit_offset
/ BITS_PER_UNIT
;
523 *base
= unshare_expr (ref
);
527 ar_data
.delta
= delta
;
528 return for_each_index (base
, idx_analyze_ref
, &ar_data
);
531 /* Record a memory reference REF to the list REFS. The reference occurs in
532 LOOP in statement STMT and it is write if WRITE_P. Returns true if the
533 reference was recorded, false otherwise. */
536 gather_memory_references_ref (struct loop
*loop
, struct mem_ref_group
**refs
,
537 tree ref
, bool write_p
, gimple stmt
)
541 struct mem_ref_group
*agrp
;
543 if (get_base_address (ref
) == NULL
)
546 if (!analyze_ref (loop
, &ref
, &base
, &step
, &delta
, stmt
))
548 /* If analyze_ref fails the default is a NULL_TREE. We can stop here. */
549 if (step
== NULL_TREE
)
552 /* Stop if the address of BASE could not be taken. */
553 if (may_be_nonaddressable_p (base
))
556 /* Limit non-constant step prefetching only to the innermost loops and
557 only when the step is loop invariant in the entire loop nest. */
558 if (!cst_and_fits_in_hwi (step
))
560 if (loop
->inner
!= NULL
)
562 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
564 fprintf (dump_file
, "Memory expression %p\n",(void *) ref
);
565 print_generic_expr (dump_file
, ref
, TDF_TREE
);
566 fprintf (dump_file
,":");
567 dump_mem_details (dump_file
, base
, step
, delta
, write_p
);
569 "Ignoring %p, non-constant step prefetching is "
570 "limited to inner most loops \n",
577 if (!expr_invariant_in_loop_p (loop_outermost (loop
), step
))
579 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
581 fprintf (dump_file
, "Memory expression %p\n",(void *) ref
);
582 print_generic_expr (dump_file
, ref
, TDF_TREE
);
583 fprintf (dump_file
,":");
584 dump_mem_details (dump_file
, base
, step
, delta
, write_p
);
586 "Not prefetching, ignoring %p due to "
587 "loop variant step\n",
595 /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
596 are integer constants. */
597 agrp
= find_or_create_group (refs
, base
, step
);
598 record_ref (agrp
, stmt
, ref
, delta
, write_p
);
603 /* Record the suitable memory references in LOOP. NO_OTHER_REFS is set to
604 true if there are no other memory references inside the loop. */
606 static struct mem_ref_group
*
607 gather_memory_references (struct loop
*loop
, bool *no_other_refs
, unsigned *ref_count
)
609 basic_block
*body
= get_loop_body_in_dom_order (loop
);
612 gimple_stmt_iterator bsi
;
615 struct mem_ref_group
*refs
= NULL
;
617 *no_other_refs
= true;
620 /* Scan the loop body in order, so that the former references precede the
622 for (i
= 0; i
< loop
->num_nodes
; i
++)
625 if (bb
->loop_father
!= loop
)
628 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
630 stmt
= gsi_stmt (bsi
);
632 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
634 if (gimple_vuse (stmt
)
635 || (is_gimple_call (stmt
)
636 && !(gimple_call_flags (stmt
) & ECF_CONST
)))
637 *no_other_refs
= false;
641 lhs
= gimple_assign_lhs (stmt
);
642 rhs
= gimple_assign_rhs1 (stmt
);
644 if (REFERENCE_CLASS_P (rhs
))
646 *no_other_refs
&= gather_memory_references_ref (loop
, &refs
,
650 if (REFERENCE_CLASS_P (lhs
))
652 *no_other_refs
&= gather_memory_references_ref (loop
, &refs
,
663 /* Prune the prefetch candidate REF using the self-reuse. */
666 prune_ref_by_self_reuse (struct mem_ref
*ref
)
671 /* If the step size is non constant, we cannot calculate prefetch_mod. */
672 if (!cst_and_fits_in_hwi (ref
->group
->step
))
675 step
= int_cst_value (ref
->group
->step
);
681 /* Prefetch references to invariant address just once. */
682 ref
->prefetch_before
= 1;
689 if (step
> PREFETCH_BLOCK
)
692 if ((backward
&& HAVE_BACKWARD_PREFETCH
)
693 || (!backward
&& HAVE_FORWARD_PREFETCH
))
695 ref
->prefetch_before
= 1;
699 ref
->prefetch_mod
= PREFETCH_BLOCK
/ step
;
702 /* Divides X by BY, rounding down. */
705 ddown (HOST_WIDE_INT x
, unsigned HOST_WIDE_INT by
)
712 return (x
+ by
- 1) / by
;
715 /* Given a CACHE_LINE_SIZE and two inductive memory references
716 with a common STEP greater than CACHE_LINE_SIZE and an address
717 difference DELTA, compute the probability that they will fall
718 in different cache lines. Return true if the computed miss rate
719 is not greater than the ACCEPTABLE_MISS_RATE. DISTINCT_ITERS is the
720 number of distinct iterations after which the pattern repeats itself.
721 ALIGN_UNIT is the unit of alignment in bytes. */
724 is_miss_rate_acceptable (unsigned HOST_WIDE_INT cache_line_size
,
725 HOST_WIDE_INT step
, HOST_WIDE_INT delta
,
726 unsigned HOST_WIDE_INT distinct_iters
,
729 unsigned align
, iter
;
730 int total_positions
, miss_positions
, max_allowed_miss_positions
;
731 int address1
, address2
, cache_line1
, cache_line2
;
733 /* It always misses if delta is greater than or equal to the cache
735 if (delta
>= (HOST_WIDE_INT
) cache_line_size
)
739 total_positions
= (cache_line_size
/ align_unit
) * distinct_iters
;
740 max_allowed_miss_positions
= (ACCEPTABLE_MISS_RATE
* total_positions
) / 1000;
742 /* Iterate through all possible alignments of the first
743 memory reference within its cache line. */
744 for (align
= 0; align
< cache_line_size
; align
+= align_unit
)
746 /* Iterate through all distinct iterations. */
747 for (iter
= 0; iter
< distinct_iters
; iter
++)
749 address1
= align
+ step
* iter
;
750 address2
= address1
+ delta
;
751 cache_line1
= address1
/ cache_line_size
;
752 cache_line2
= address2
/ cache_line_size
;
753 if (cache_line1
!= cache_line2
)
756 if (miss_positions
> max_allowed_miss_positions
)
763 /* Prune the prefetch candidate REF using the reuse with BY.
764 If BY_IS_BEFORE is true, BY is before REF in the loop. */
767 prune_ref_by_group_reuse (struct mem_ref
*ref
, struct mem_ref
*by
,
772 HOST_WIDE_INT delta_r
= ref
->delta
, delta_b
= by
->delta
;
773 HOST_WIDE_INT delta
= delta_b
- delta_r
;
774 HOST_WIDE_INT hit_from
;
775 unsigned HOST_WIDE_INT prefetch_before
, prefetch_block
;
776 HOST_WIDE_INT reduced_step
;
777 unsigned HOST_WIDE_INT reduced_prefetch_block
;
781 /* If the step is non constant we cannot calculate prefetch_before. */
782 if (!cst_and_fits_in_hwi (ref
->group
->step
)) {
786 step
= int_cst_value (ref
->group
->step
);
793 /* If the references has the same address, only prefetch the
796 ref
->prefetch_before
= 0;
803 /* If the reference addresses are invariant and fall into the
804 same cache line, prefetch just the first one. */
808 if (ddown (ref
->delta
, PREFETCH_BLOCK
)
809 != ddown (by
->delta
, PREFETCH_BLOCK
))
812 ref
->prefetch_before
= 0;
816 /* Only prune the reference that is behind in the array. */
822 /* Transform the data so that we may assume that the accesses
826 delta_r
= PREFETCH_BLOCK
- 1 - delta_r
;
827 delta_b
= PREFETCH_BLOCK
- 1 - delta_b
;
835 /* Check whether the two references are likely to hit the same cache
836 line, and how distant the iterations in that it occurs are from
839 if (step
<= PREFETCH_BLOCK
)
841 /* The accesses are sure to meet. Let us check when. */
842 hit_from
= ddown (delta_b
, PREFETCH_BLOCK
) * PREFETCH_BLOCK
;
843 prefetch_before
= (hit_from
- delta_r
+ step
- 1) / step
;
845 /* Do not reduce prefetch_before if we meet beyond cache size. */
846 if (prefetch_before
> absu_hwi (L2_CACHE_SIZE_BYTES
/ step
))
847 prefetch_before
= PREFETCH_ALL
;
848 if (prefetch_before
< ref
->prefetch_before
)
849 ref
->prefetch_before
= prefetch_before
;
854 /* A more complicated case with step > prefetch_block. First reduce
855 the ratio between the step and the cache line size to its simplest
856 terms. The resulting denominator will then represent the number of
857 distinct iterations after which each address will go back to its
858 initial location within the cache line. This computation assumes
859 that PREFETCH_BLOCK is a power of two. */
860 prefetch_block
= PREFETCH_BLOCK
;
861 reduced_prefetch_block
= prefetch_block
;
863 while ((reduced_step
& 1) == 0
864 && reduced_prefetch_block
> 1)
867 reduced_prefetch_block
>>= 1;
870 prefetch_before
= delta
/ step
;
872 ref_type
= TREE_TYPE (ref
->mem
);
873 align_unit
= TYPE_ALIGN (ref_type
) / 8;
874 if (is_miss_rate_acceptable (prefetch_block
, step
, delta
,
875 reduced_prefetch_block
, align_unit
))
877 /* Do not reduce prefetch_before if we meet beyond cache size. */
878 if (prefetch_before
> L2_CACHE_SIZE_BYTES
/ PREFETCH_BLOCK
)
879 prefetch_before
= PREFETCH_ALL
;
880 if (prefetch_before
< ref
->prefetch_before
)
881 ref
->prefetch_before
= prefetch_before
;
886 /* Try also the following iteration. */
888 delta
= step
- delta
;
889 if (is_miss_rate_acceptable (prefetch_block
, step
, delta
,
890 reduced_prefetch_block
, align_unit
))
892 if (prefetch_before
< ref
->prefetch_before
)
893 ref
->prefetch_before
= prefetch_before
;
898 /* The ref probably does not reuse by. */
902 /* Prune the prefetch candidate REF using the reuses with other references
906 prune_ref_by_reuse (struct mem_ref
*ref
, struct mem_ref
*refs
)
908 struct mem_ref
*prune_by
;
911 prune_ref_by_self_reuse (ref
);
913 for (prune_by
= refs
; prune_by
; prune_by
= prune_by
->next
)
921 if (!WRITE_CAN_USE_READ_PREFETCH
923 && !prune_by
->write_p
)
925 if (!READ_CAN_USE_WRITE_PREFETCH
927 && prune_by
->write_p
)
930 prune_ref_by_group_reuse (ref
, prune_by
, before
);
934 /* Prune the prefetch candidates in GROUP using the reuse analysis. */
937 prune_group_by_reuse (struct mem_ref_group
*group
)
939 struct mem_ref
*ref_pruned
;
941 for (ref_pruned
= group
->refs
; ref_pruned
; ref_pruned
= ref_pruned
->next
)
943 prune_ref_by_reuse (ref_pruned
, group
->refs
);
945 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
947 fprintf (dump_file
, "Reference %p:", (void *) ref_pruned
);
949 if (ref_pruned
->prefetch_before
== PREFETCH_ALL
950 && ref_pruned
->prefetch_mod
== 1)
951 fprintf (dump_file
, " no restrictions");
952 else if (ref_pruned
->prefetch_before
== 0)
953 fprintf (dump_file
, " do not prefetch");
954 else if (ref_pruned
->prefetch_before
<= ref_pruned
->prefetch_mod
)
955 fprintf (dump_file
, " prefetch once");
958 if (ref_pruned
->prefetch_before
!= PREFETCH_ALL
)
960 fprintf (dump_file
, " prefetch before ");
961 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
962 ref_pruned
->prefetch_before
);
964 if (ref_pruned
->prefetch_mod
!= 1)
966 fprintf (dump_file
, " prefetch mod ");
967 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
968 ref_pruned
->prefetch_mod
);
971 fprintf (dump_file
, "\n");
976 /* Prune the list of prefetch candidates GROUPS using the reuse analysis. */
979 prune_by_reuse (struct mem_ref_group
*groups
)
981 for (; groups
; groups
= groups
->next
)
982 prune_group_by_reuse (groups
);
985 /* Returns true if we should issue prefetch for REF. */
988 should_issue_prefetch_p (struct mem_ref
*ref
)
990 /* For now do not issue prefetches for only first few of the
992 if (ref
->prefetch_before
!= PREFETCH_ALL
)
994 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
995 fprintf (dump_file
, "Ignoring %p due to prefetch_before\n",
1000 /* Do not prefetch nontemporal stores. */
1003 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1004 fprintf (dump_file
, "Ignoring nontemporal store %p\n", (void *) ref
);
1011 /* Decide which of the prefetch candidates in GROUPS to prefetch.
1012 AHEAD is the number of iterations to prefetch ahead (which corresponds
1013 to the number of simultaneous instances of one prefetch running at a
1014 time). UNROLL_FACTOR is the factor by that the loop is going to be
1015 unrolled. Returns true if there is anything to prefetch. */
1018 schedule_prefetches (struct mem_ref_group
*groups
, unsigned unroll_factor
,
1021 unsigned remaining_prefetch_slots
, n_prefetches
, prefetch_slots
;
1022 unsigned slots_per_prefetch
;
1023 struct mem_ref
*ref
;
1026 /* At most SIMULTANEOUS_PREFETCHES should be running at the same time. */
1027 remaining_prefetch_slots
= SIMULTANEOUS_PREFETCHES
;
1029 /* The prefetch will run for AHEAD iterations of the original loop, i.e.,
1030 AHEAD / UNROLL_FACTOR iterations of the unrolled loop. In each iteration,
1031 it will need a prefetch slot. */
1032 slots_per_prefetch
= (ahead
+ unroll_factor
/ 2) / unroll_factor
;
1033 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1034 fprintf (dump_file
, "Each prefetch instruction takes %u prefetch slots.\n",
1035 slots_per_prefetch
);
1037 /* For now we just take memory references one by one and issue
1038 prefetches for as many as possible. The groups are sorted
1039 starting with the largest step, since the references with
1040 large step are more likely to cause many cache misses. */
1042 for (; groups
; groups
= groups
->next
)
1043 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1045 if (!should_issue_prefetch_p (ref
))
1048 /* The loop is far from being sufficiently unrolled for this
1049 prefetch. Do not generate prefetch to avoid many redudant
1051 if (ref
->prefetch_mod
/ unroll_factor
> PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
)
1054 /* If we need to prefetch the reference each PREFETCH_MOD iterations,
1055 and we unroll the loop UNROLL_FACTOR times, we need to insert
1056 ceil (UNROLL_FACTOR / PREFETCH_MOD) instructions in each
1058 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1059 / ref
->prefetch_mod
);
1060 prefetch_slots
= n_prefetches
* slots_per_prefetch
;
1062 /* If more than half of the prefetches would be lost anyway, do not
1063 issue the prefetch. */
1064 if (2 * remaining_prefetch_slots
< prefetch_slots
)
1067 ref
->issue_prefetch_p
= true;
1069 if (remaining_prefetch_slots
<= prefetch_slots
)
1071 remaining_prefetch_slots
-= prefetch_slots
;
1078 /* Return TRUE if no prefetch is going to be generated in the given
1082 nothing_to_prefetch_p (struct mem_ref_group
*groups
)
1084 struct mem_ref
*ref
;
1086 for (; groups
; groups
= groups
->next
)
1087 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1088 if (should_issue_prefetch_p (ref
))
1094 /* Estimate the number of prefetches in the given GROUPS.
1095 UNROLL_FACTOR is the factor by which LOOP was unrolled. */
1098 estimate_prefetch_count (struct mem_ref_group
*groups
, unsigned unroll_factor
)
1100 struct mem_ref
*ref
;
1101 unsigned n_prefetches
;
1102 int prefetch_count
= 0;
1104 for (; groups
; groups
= groups
->next
)
1105 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1106 if (should_issue_prefetch_p (ref
))
1108 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1109 / ref
->prefetch_mod
);
1110 prefetch_count
+= n_prefetches
;
1113 return prefetch_count
;
1116 /* Issue prefetches for the reference REF into loop as decided before.
1117 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR
1118 is the factor by which LOOP was unrolled. */
1121 issue_prefetch_ref (struct mem_ref
*ref
, unsigned unroll_factor
, unsigned ahead
)
1123 HOST_WIDE_INT delta
;
1124 tree addr
, addr_base
, write_p
, local
, forward
;
1126 gimple_stmt_iterator bsi
;
1127 unsigned n_prefetches
, ap
;
1128 bool nontemporal
= ref
->reuse_distance
>= L2_CACHE_SIZE_BYTES
;
1130 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1131 fprintf (dump_file
, "Issued%s prefetch for %p.\n",
1132 nontemporal
? " nontemporal" : "",
1135 bsi
= gsi_for_stmt (ref
->stmt
);
1137 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1138 / ref
->prefetch_mod
);
1139 addr_base
= build_fold_addr_expr_with_type (ref
->mem
, ptr_type_node
);
1140 addr_base
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr_base
),
1141 true, NULL
, true, GSI_SAME_STMT
);
1142 write_p
= ref
->write_p
? integer_one_node
: integer_zero_node
;
1143 local
= nontemporal
? integer_zero_node
: integer_three_node
;
1145 for (ap
= 0; ap
< n_prefetches
; ap
++)
1147 if (cst_and_fits_in_hwi (ref
->group
->step
))
1149 /* Determine the address to prefetch. */
1150 delta
= (ahead
+ ap
* ref
->prefetch_mod
) *
1151 int_cst_value (ref
->group
->step
);
1152 addr
= fold_build_pointer_plus_hwi (addr_base
, delta
);
1153 addr
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr
), true, NULL
,
1154 true, GSI_SAME_STMT
);
1158 /* The step size is non-constant but loop-invariant. We use the
1159 heuristic to simply prefetch ahead iterations ahead. */
1160 forward
= fold_build2 (MULT_EXPR
, sizetype
,
1161 fold_convert (sizetype
, ref
->group
->step
),
1162 fold_convert (sizetype
, size_int (ahead
)));
1163 addr
= fold_build_pointer_plus (addr_base
, forward
);
1164 addr
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr
), true,
1165 NULL
, true, GSI_SAME_STMT
);
1167 /* Create the prefetch instruction. */
1168 prefetch
= gimple_build_call (builtin_decl_explicit (BUILT_IN_PREFETCH
),
1169 3, addr
, write_p
, local
);
1170 gsi_insert_before (&bsi
, prefetch
, GSI_SAME_STMT
);
1174 /* Issue prefetches for the references in GROUPS into loop as decided before.
1175 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR is the
1176 factor by that LOOP was unrolled. */
1179 issue_prefetches (struct mem_ref_group
*groups
,
1180 unsigned unroll_factor
, unsigned ahead
)
1182 struct mem_ref
*ref
;
1184 for (; groups
; groups
= groups
->next
)
1185 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1186 if (ref
->issue_prefetch_p
)
1187 issue_prefetch_ref (ref
, unroll_factor
, ahead
);
1190 /* Returns true if REF is a memory write for that a nontemporal store insn
1194 nontemporal_store_p (struct mem_ref
*ref
)
1196 enum machine_mode mode
;
1197 enum insn_code code
;
1199 /* REF must be a write that is not reused. We require it to be independent
1200 on all other memory references in the loop, as the nontemporal stores may
1201 be reordered with respect to other memory references. */
1203 || !ref
->independent_p
1204 || ref
->reuse_distance
< L2_CACHE_SIZE_BYTES
)
1207 /* Check that we have the storent instruction for the mode. */
1208 mode
= TYPE_MODE (TREE_TYPE (ref
->mem
));
1209 if (mode
== BLKmode
)
1212 code
= optab_handler (storent_optab
, mode
);
1213 return code
!= CODE_FOR_nothing
;
1216 /* If REF is a nontemporal store, we mark the corresponding modify statement
1217 and return true. Otherwise, we return false. */
1220 mark_nontemporal_store (struct mem_ref
*ref
)
1222 if (!nontemporal_store_p (ref
))
1225 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1226 fprintf (dump_file
, "Marked reference %p as a nontemporal store.\n",
1229 gimple_assign_set_nontemporal_move (ref
->stmt
, true);
1230 ref
->storent_p
= true;
1235 /* Issue a memory fence instruction after LOOP. */
1238 emit_mfence_after_loop (struct loop
*loop
)
1240 vec
<edge
> exits
= get_loop_exit_edges (loop
);
1243 gimple_stmt_iterator bsi
;
1246 FOR_EACH_VEC_ELT (exits
, i
, exit
)
1248 call
= gimple_build_call (FENCE_FOLLOWING_MOVNT
, 0);
1250 if (!single_pred_p (exit
->dest
)
1251 /* If possible, we prefer not to insert the fence on other paths
1253 && !(exit
->flags
& EDGE_ABNORMAL
))
1254 split_loop_exit_edge (exit
);
1255 bsi
= gsi_after_labels (exit
->dest
);
1257 gsi_insert_before (&bsi
, call
, GSI_NEW_STMT
);
1261 update_ssa (TODO_update_ssa_only_virtuals
);
1264 /* Returns true if we can use storent in loop, false otherwise. */
1267 may_use_storent_in_loop_p (struct loop
*loop
)
1271 if (loop
->inner
!= NULL
)
1274 /* If we must issue a mfence insn after using storent, check that there
1275 is a suitable place for it at each of the loop exits. */
1276 if (FENCE_FOLLOWING_MOVNT
!= NULL_TREE
)
1278 vec
<edge
> exits
= get_loop_exit_edges (loop
);
1282 FOR_EACH_VEC_ELT (exits
, i
, exit
)
1283 if ((exit
->flags
& EDGE_ABNORMAL
)
1284 && exit
->dest
== EXIT_BLOCK_PTR
)
1293 /* Marks nontemporal stores in LOOP. GROUPS contains the description of memory
1294 references in the loop. */
1297 mark_nontemporal_stores (struct loop
*loop
, struct mem_ref_group
*groups
)
1299 struct mem_ref
*ref
;
1302 if (!may_use_storent_in_loop_p (loop
))
1305 for (; groups
; groups
= groups
->next
)
1306 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1307 any
|= mark_nontemporal_store (ref
);
1309 if (any
&& FENCE_FOLLOWING_MOVNT
!= NULL_TREE
)
1310 emit_mfence_after_loop (loop
);
1313 /* Determines whether we can profitably unroll LOOP FACTOR times, and if
1314 this is the case, fill in DESC by the description of number of
1318 should_unroll_loop_p (struct loop
*loop
, struct tree_niter_desc
*desc
,
1321 if (!can_unroll_loop_p (loop
, factor
, desc
))
1324 /* We only consider loops without control flow for unrolling. This is not
1325 a hard restriction -- tree_unroll_loop works with arbitrary loops
1326 as well; but the unrolling/prefetching is usually more profitable for
1327 loops consisting of a single basic block, and we want to limit the
1329 if (loop
->num_nodes
> 2)
1335 /* Determine the coefficient by that unroll LOOP, from the information
1336 contained in the list of memory references REFS. Description of
1337 umber of iterations of LOOP is stored to DESC. NINSNS is the number of
1338 insns of the LOOP. EST_NITER is the estimated number of iterations of
1339 the loop, or -1 if no estimate is available. */
1342 determine_unroll_factor (struct loop
*loop
, struct mem_ref_group
*refs
,
1343 unsigned ninsns
, struct tree_niter_desc
*desc
,
1344 HOST_WIDE_INT est_niter
)
1346 unsigned upper_bound
;
1347 unsigned nfactor
, factor
, mod_constraint
;
1348 struct mem_ref_group
*agp
;
1349 struct mem_ref
*ref
;
1351 /* First check whether the loop is not too large to unroll. We ignore
1352 PARAM_MAX_UNROLL_TIMES, because for small loops, it prevented us
1353 from unrolling them enough to make exactly one cache line covered by each
1354 iteration. Also, the goal of PARAM_MAX_UNROLL_TIMES is to prevent
1355 us from unrolling the loops too many times in cases where we only expect
1356 gains from better scheduling and decreasing loop overhead, which is not
1358 upper_bound
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / ninsns
;
1360 /* If we unrolled the loop more times than it iterates, the unrolled version
1361 of the loop would be never entered. */
1362 if (est_niter
>= 0 && est_niter
< (HOST_WIDE_INT
) upper_bound
)
1363 upper_bound
= est_niter
;
1365 if (upper_bound
<= 1)
1368 /* Choose the factor so that we may prefetch each cache just once,
1369 but bound the unrolling by UPPER_BOUND. */
1371 for (agp
= refs
; agp
; agp
= agp
->next
)
1372 for (ref
= agp
->refs
; ref
; ref
= ref
->next
)
1373 if (should_issue_prefetch_p (ref
))
1375 mod_constraint
= ref
->prefetch_mod
;
1376 nfactor
= least_common_multiple (mod_constraint
, factor
);
1377 if (nfactor
<= upper_bound
)
1381 if (!should_unroll_loop_p (loop
, desc
, factor
))
1387 /* Returns the total volume of the memory references REFS, taking into account
1388 reuses in the innermost loop and cache line size. TODO -- we should also
1389 take into account reuses across the iterations of the loops in the loop
1393 volume_of_references (struct mem_ref_group
*refs
)
1395 unsigned volume
= 0;
1396 struct mem_ref_group
*gr
;
1397 struct mem_ref
*ref
;
1399 for (gr
= refs
; gr
; gr
= gr
->next
)
1400 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1402 /* Almost always reuses another value? */
1403 if (ref
->prefetch_before
!= PREFETCH_ALL
)
1406 /* If several iterations access the same cache line, use the size of
1407 the line divided by this number. Otherwise, a cache line is
1408 accessed in each iteration. TODO -- in the latter case, we should
1409 take the size of the reference into account, rounding it up on cache
1410 line size multiple. */
1411 volume
+= L1_CACHE_LINE_SIZE
/ ref
->prefetch_mod
;
1416 /* Returns the volume of memory references accessed across VEC iterations of
1417 loops, whose sizes are described in the LOOP_SIZES array. N is the number
1418 of the loops in the nest (length of VEC and LOOP_SIZES vectors). */
1421 volume_of_dist_vector (lambda_vector vec
, unsigned *loop_sizes
, unsigned n
)
1425 for (i
= 0; i
< n
; i
++)
1432 gcc_assert (vec
[i
] > 0);
1434 /* We ignore the parts of the distance vector in subloops, since usually
1435 the numbers of iterations are much smaller. */
1436 return loop_sizes
[i
] * vec
[i
];
1439 /* Add the steps of ACCESS_FN multiplied by STRIDE to the array STRIDE
1440 at the position corresponding to the loop of the step. N is the depth
1441 of the considered loop nest, and, LOOP is its innermost loop. */
1444 add_subscript_strides (tree access_fn
, unsigned stride
,
1445 HOST_WIDE_INT
*strides
, unsigned n
, struct loop
*loop
)
1449 HOST_WIDE_INT astep
;
1450 unsigned min_depth
= loop_depth (loop
) - n
;
1452 while (TREE_CODE (access_fn
) == POLYNOMIAL_CHREC
)
1454 aloop
= get_chrec_loop (access_fn
);
1455 step
= CHREC_RIGHT (access_fn
);
1456 access_fn
= CHREC_LEFT (access_fn
);
1458 if ((unsigned) loop_depth (aloop
) <= min_depth
)
1461 if (tree_fits_shwi_p (step
))
1462 astep
= tree_to_shwi (step
);
1464 astep
= L1_CACHE_LINE_SIZE
;
1466 strides
[n
- 1 - loop_depth (loop
) + loop_depth (aloop
)] += astep
* stride
;
1471 /* Returns the volume of memory references accessed between two consecutive
1472 self-reuses of the reference DR. We consider the subscripts of DR in N
1473 loops, and LOOP_SIZES contains the volumes of accesses in each of the
1474 loops. LOOP is the innermost loop of the current loop nest. */
1477 self_reuse_distance (data_reference_p dr
, unsigned *loop_sizes
, unsigned n
,
1480 tree stride
, access_fn
;
1481 HOST_WIDE_INT
*strides
, astride
;
1482 vec
<tree
> access_fns
;
1483 tree ref
= DR_REF (dr
);
1484 unsigned i
, ret
= ~0u;
1486 /* In the following example:
1488 for (i = 0; i < N; i++)
1489 for (j = 0; j < N; j++)
1491 the same cache line is accessed each N steps (except if the change from
1492 i to i + 1 crosses the boundary of the cache line). Thus, for self-reuse,
1493 we cannot rely purely on the results of the data dependence analysis.
1495 Instead, we compute the stride of the reference in each loop, and consider
1496 the innermost loop in that the stride is less than cache size. */
1498 strides
= XCNEWVEC (HOST_WIDE_INT
, n
);
1499 access_fns
= DR_ACCESS_FNS (dr
);
1501 FOR_EACH_VEC_ELT (access_fns
, i
, access_fn
)
1503 /* Keep track of the reference corresponding to the subscript, so that we
1505 while (handled_component_p (ref
) && TREE_CODE (ref
) != ARRAY_REF
)
1506 ref
= TREE_OPERAND (ref
, 0);
1508 if (TREE_CODE (ref
) == ARRAY_REF
)
1510 stride
= TYPE_SIZE_UNIT (TREE_TYPE (ref
));
1511 if (tree_fits_uhwi_p (stride
))
1512 astride
= tree_low_cst (stride
, 1);
1514 astride
= L1_CACHE_LINE_SIZE
;
1516 ref
= TREE_OPERAND (ref
, 0);
1521 add_subscript_strides (access_fn
, astride
, strides
, n
, loop
);
1524 for (i
= n
; i
-- > 0; )
1526 unsigned HOST_WIDE_INT s
;
1528 s
= strides
[i
] < 0 ? -strides
[i
] : strides
[i
];
1530 if (s
< (unsigned) L1_CACHE_LINE_SIZE
1532 > (unsigned) (L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)))
1534 ret
= loop_sizes
[i
];
1543 /* Determines the distance till the first reuse of each reference in REFS
1544 in the loop nest of LOOP. NO_OTHER_REFS is true if there are no other
1545 memory references in the loop. Return false if the analysis fails. */
1548 determine_loop_nest_reuse (struct loop
*loop
, struct mem_ref_group
*refs
,
1551 struct loop
*nest
, *aloop
;
1552 vec
<data_reference_p
> datarefs
= vNULL
;
1553 vec
<ddr_p
> dependences
= vNULL
;
1554 struct mem_ref_group
*gr
;
1555 struct mem_ref
*ref
, *refb
;
1556 vec
<loop_p
> vloops
= vNULL
;
1557 unsigned *loop_data_size
;
1559 unsigned volume
, dist
, adist
;
1561 data_reference_p dr
;
1567 /* Find the outermost loop of the loop nest of loop (we require that
1568 there are no sibling loops inside the nest). */
1572 aloop
= loop_outer (nest
);
1574 if (aloop
== current_loops
->tree_root
1575 || aloop
->inner
->next
)
1581 /* For each loop, determine the amount of data accessed in each iteration.
1582 We use this to estimate whether the reference is evicted from the
1583 cache before its reuse. */
1584 find_loop_nest (nest
, &vloops
);
1585 n
= vloops
.length ();
1586 loop_data_size
= XNEWVEC (unsigned, n
);
1587 volume
= volume_of_references (refs
);
1591 loop_data_size
[i
] = volume
;
1592 /* Bound the volume by the L2 cache size, since above this bound,
1593 all dependence distances are equivalent. */
1594 if (volume
> L2_CACHE_SIZE_BYTES
)
1598 vol
= estimated_stmt_executions_int (aloop
);
1600 vol
= expected_loop_iterations (aloop
);
1604 /* Prepare the references in the form suitable for data dependence
1605 analysis. We ignore unanalyzable data references (the results
1606 are used just as a heuristics to estimate temporality of the
1607 references, hence we do not need to worry about correctness). */
1608 for (gr
= refs
; gr
; gr
= gr
->next
)
1609 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1611 dr
= create_data_ref (nest
, loop_containing_stmt (ref
->stmt
),
1612 ref
->mem
, ref
->stmt
, !ref
->write_p
);
1616 ref
->reuse_distance
= volume
;
1618 datarefs
.safe_push (dr
);
1621 no_other_refs
= false;
1624 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
1626 dist
= self_reuse_distance (dr
, loop_data_size
, n
, loop
);
1627 ref
= (struct mem_ref
*) dr
->aux
;
1628 if (ref
->reuse_distance
> dist
)
1629 ref
->reuse_distance
= dist
;
1632 ref
->independent_p
= true;
1635 if (!compute_all_dependences (datarefs
, &dependences
, vloops
, true))
1638 FOR_EACH_VEC_ELT (dependences
, i
, dep
)
1640 if (DDR_ARE_DEPENDENT (dep
) == chrec_known
)
1643 ref
= (struct mem_ref
*) DDR_A (dep
)->aux
;
1644 refb
= (struct mem_ref
*) DDR_B (dep
)->aux
;
1646 if (DDR_ARE_DEPENDENT (dep
) == chrec_dont_know
1647 || DDR_NUM_DIST_VECTS (dep
) == 0)
1649 /* If the dependence cannot be analyzed, assume that there might be
1653 ref
->independent_p
= false;
1654 refb
->independent_p
= false;
1658 /* The distance vectors are normalized to be always lexicographically
1659 positive, hence we cannot tell just from them whether DDR_A comes
1660 before DDR_B or vice versa. However, it is not important,
1661 anyway -- if DDR_A is close to DDR_B, then it is either reused in
1662 DDR_B (and it is not nontemporal), or it reuses the value of DDR_B
1663 in cache (and marking it as nontemporal would not affect
1667 for (j
= 0; j
< DDR_NUM_DIST_VECTS (dep
); j
++)
1669 adist
= volume_of_dist_vector (DDR_DIST_VECT (dep
, j
),
1672 /* If this is a dependence in the innermost loop (i.e., the
1673 distances in all superloops are zero) and it is not
1674 the trivial self-dependence with distance zero, record that
1675 the references are not completely independent. */
1676 if (lambda_vector_zerop (DDR_DIST_VECT (dep
, j
), n
- 1)
1678 || DDR_DIST_VECT (dep
, j
)[n
-1] != 0))
1680 ref
->independent_p
= false;
1681 refb
->independent_p
= false;
1684 /* Ignore accesses closer than
1685 L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
1686 so that we use nontemporal prefetches e.g. if single memory
1687 location is accessed several times in a single iteration of
1689 if (adist
< L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)
1697 if (ref
->reuse_distance
> dist
)
1698 ref
->reuse_distance
= dist
;
1699 if (refb
->reuse_distance
> dist
)
1700 refb
->reuse_distance
= dist
;
1703 free_dependence_relations (dependences
);
1704 free_data_refs (datarefs
);
1705 free (loop_data_size
);
1707 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1709 fprintf (dump_file
, "Reuse distances:\n");
1710 for (gr
= refs
; gr
; gr
= gr
->next
)
1711 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1712 fprintf (dump_file
, " ref %p distance %u\n",
1713 (void *) ref
, ref
->reuse_distance
);
1719 /* Determine whether or not the trip count to ahead ratio is too small based
1720 on prefitablility consideration.
1721 AHEAD: the iteration ahead distance,
1722 EST_NITER: the estimated trip count. */
1725 trip_count_to_ahead_ratio_too_small_p (unsigned ahead
, HOST_WIDE_INT est_niter
)
1727 /* Assume trip count to ahead ratio is big enough if the trip count could not
1728 be estimated at compile time. */
1732 if (est_niter
< (HOST_WIDE_INT
) (TRIP_COUNT_TO_AHEAD_RATIO
* ahead
))
1734 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1736 "Not prefetching -- loop estimated to roll only %d times\n",
1744 /* Determine whether or not the number of memory references in the loop is
1745 reasonable based on the profitablity and compilation time considerations.
1746 NINSNS: estimated number of instructions in the loop,
1747 MEM_REF_COUNT: total number of memory references in the loop. */
1750 mem_ref_count_reasonable_p (unsigned ninsns
, unsigned mem_ref_count
)
1752 int insn_to_mem_ratio
;
1754 if (mem_ref_count
== 0)
1757 /* Miss rate computation (is_miss_rate_acceptable) and dependence analysis
1758 (compute_all_dependences) have high costs based on quadratic complexity.
1759 To avoid huge compilation time, we give up prefetching if mem_ref_count
1761 if (mem_ref_count
> PREFETCH_MAX_MEM_REFS_PER_LOOP
)
1764 /* Prefetching improves performance by overlapping cache missing
1765 memory accesses with CPU operations. If the loop does not have
1766 enough CPU operations to overlap with memory operations, prefetching
1767 won't give a significant benefit. One approximate way of checking
1768 this is to require the ratio of instructions to memory references to
1769 be above a certain limit. This approximation works well in practice.
1770 TODO: Implement a more precise computation by estimating the time
1771 for each CPU or memory op in the loop. Time estimates for memory ops
1772 should account for cache misses. */
1773 insn_to_mem_ratio
= ninsns
/ mem_ref_count
;
1775 if (insn_to_mem_ratio
< PREFETCH_MIN_INSN_TO_MEM_RATIO
)
1777 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1779 "Not prefetching -- instruction to memory reference ratio (%d) too small\n",
1787 /* Determine whether or not the instruction to prefetch ratio in the loop is
1788 too small based on the profitablity consideration.
1789 NINSNS: estimated number of instructions in the loop,
1790 PREFETCH_COUNT: an estimate of the number of prefetches,
1791 UNROLL_FACTOR: the factor to unroll the loop if prefetching. */
1794 insn_to_prefetch_ratio_too_small_p (unsigned ninsns
, unsigned prefetch_count
,
1795 unsigned unroll_factor
)
1797 int insn_to_prefetch_ratio
;
1799 /* Prefetching most likely causes performance degradation when the instruction
1800 to prefetch ratio is too small. Too many prefetch instructions in a loop
1801 may reduce the I-cache performance.
1802 (unroll_factor * ninsns) is used to estimate the number of instructions in
1803 the unrolled loop. This implementation is a bit simplistic -- the number
1804 of issued prefetch instructions is also affected by unrolling. So,
1805 prefetch_mod and the unroll factor should be taken into account when
1806 determining prefetch_count. Also, the number of insns of the unrolled
1807 loop will usually be significantly smaller than the number of insns of the
1808 original loop * unroll_factor (at least the induction variable increases
1809 and the exit branches will get eliminated), so it might be better to use
1810 tree_estimate_loop_size + estimated_unrolled_size. */
1811 insn_to_prefetch_ratio
= (unroll_factor
* ninsns
) / prefetch_count
;
1812 if (insn_to_prefetch_ratio
< MIN_INSN_TO_PREFETCH_RATIO
)
1814 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1816 "Not prefetching -- instruction to prefetch ratio (%d) too small\n",
1817 insn_to_prefetch_ratio
);
1825 /* Issue prefetch instructions for array references in LOOP. Returns
1826 true if the LOOP was unrolled. */
1829 loop_prefetch_arrays (struct loop
*loop
)
1831 struct mem_ref_group
*refs
;
1832 unsigned ahead
, ninsns
, time
, unroll_factor
;
1833 HOST_WIDE_INT est_niter
;
1834 struct tree_niter_desc desc
;
1835 bool unrolled
= false, no_other_refs
;
1836 unsigned prefetch_count
;
1837 unsigned mem_ref_count
;
1839 if (optimize_loop_nest_for_size_p (loop
))
1841 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1842 fprintf (dump_file
, " ignored (cold area)\n");
1846 /* FIXME: the time should be weighted by the probabilities of the blocks in
1848 time
= tree_num_loop_insns (loop
, &eni_time_weights
);
1852 ahead
= (PREFETCH_LATENCY
+ time
- 1) / time
;
1853 est_niter
= estimated_stmt_executions_int (loop
);
1854 if (est_niter
== -1)
1855 est_niter
= max_stmt_executions_int (loop
);
1857 /* Prefetching is not likely to be profitable if the trip count to ahead
1858 ratio is too small. */
1859 if (trip_count_to_ahead_ratio_too_small_p (ahead
, est_niter
))
1862 ninsns
= tree_num_loop_insns (loop
, &eni_size_weights
);
1864 /* Step 1: gather the memory references. */
1865 refs
= gather_memory_references (loop
, &no_other_refs
, &mem_ref_count
);
1867 /* Give up prefetching if the number of memory references in the
1868 loop is not reasonable based on profitablity and compilation time
1870 if (!mem_ref_count_reasonable_p (ninsns
, mem_ref_count
))
1873 /* Step 2: estimate the reuse effects. */
1874 prune_by_reuse (refs
);
1876 if (nothing_to_prefetch_p (refs
))
1879 if (!determine_loop_nest_reuse (loop
, refs
, no_other_refs
))
1882 /* Step 3: determine unroll factor. */
1883 unroll_factor
= determine_unroll_factor (loop
, refs
, ninsns
, &desc
,
1886 /* Estimate prefetch count for the unrolled loop. */
1887 prefetch_count
= estimate_prefetch_count (refs
, unroll_factor
);
1888 if (prefetch_count
== 0)
1891 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1892 fprintf (dump_file
, "Ahead %d, unroll factor %d, trip count "
1893 HOST_WIDE_INT_PRINT_DEC
"\n"
1894 "insn count %d, mem ref count %d, prefetch count %d\n",
1895 ahead
, unroll_factor
, est_niter
,
1896 ninsns
, mem_ref_count
, prefetch_count
);
1898 /* Prefetching is not likely to be profitable if the instruction to prefetch
1899 ratio is too small. */
1900 if (insn_to_prefetch_ratio_too_small_p (ninsns
, prefetch_count
,
1904 mark_nontemporal_stores (loop
, refs
);
1906 /* Step 4: what to prefetch? */
1907 if (!schedule_prefetches (refs
, unroll_factor
, ahead
))
1910 /* Step 5: unroll the loop. TODO -- peeling of first and last few
1911 iterations so that we do not issue superfluous prefetches. */
1912 if (unroll_factor
!= 1)
1914 tree_unroll_loop (loop
, unroll_factor
,
1915 single_dom_exit (loop
), &desc
);
1919 /* Step 6: issue the prefetches. */
1920 issue_prefetches (refs
, unroll_factor
, ahead
);
1923 release_mem_refs (refs
);
1927 /* Issue prefetch instructions for array references in loops. */
1930 tree_ssa_prefetch_arrays (void)
1934 bool unrolled
= false;
1938 /* It is possible to ask compiler for say -mtune=i486 -march=pentium4.
1939 -mtune=i486 causes us having PREFETCH_BLOCK 0, since this is part
1940 of processor costs and i486 does not have prefetch, but
1941 -march=pentium4 causes HAVE_prefetch to be true. Ugh. */
1942 || PREFETCH_BLOCK
== 0)
1945 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1947 fprintf (dump_file
, "Prefetching parameters:\n");
1948 fprintf (dump_file
, " simultaneous prefetches: %d\n",
1949 SIMULTANEOUS_PREFETCHES
);
1950 fprintf (dump_file
, " prefetch latency: %d\n", PREFETCH_LATENCY
);
1951 fprintf (dump_file
, " prefetch block size: %d\n", PREFETCH_BLOCK
);
1952 fprintf (dump_file
, " L1 cache size: %d lines, %d kB\n",
1953 L1_CACHE_SIZE_BYTES
/ L1_CACHE_LINE_SIZE
, L1_CACHE_SIZE
);
1954 fprintf (dump_file
, " L1 cache line size: %d\n", L1_CACHE_LINE_SIZE
);
1955 fprintf (dump_file
, " L2 cache size: %d kB\n", L2_CACHE_SIZE
);
1956 fprintf (dump_file
, " min insn-to-prefetch ratio: %d \n",
1957 MIN_INSN_TO_PREFETCH_RATIO
);
1958 fprintf (dump_file
, " min insn-to-mem ratio: %d \n",
1959 PREFETCH_MIN_INSN_TO_MEM_RATIO
);
1960 fprintf (dump_file
, "\n");
1963 initialize_original_copy_tables ();
1965 if (!builtin_decl_explicit_p (BUILT_IN_PREFETCH
))
1967 tree type
= build_function_type_list (void_type_node
,
1968 const_ptr_type_node
, NULL_TREE
);
1969 tree decl
= add_builtin_function ("__builtin_prefetch", type
,
1970 BUILT_IN_PREFETCH
, BUILT_IN_NORMAL
,
1972 DECL_IS_NOVOPS (decl
) = true;
1973 set_builtin_decl (BUILT_IN_PREFETCH
, decl
, false);
1976 /* We assume that size of cache line is a power of two, so verify this
1978 gcc_assert ((PREFETCH_BLOCK
& (PREFETCH_BLOCK
- 1)) == 0);
1980 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1982 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1983 fprintf (dump_file
, "Processing loop %d:\n", loop
->num
);
1985 unrolled
|= loop_prefetch_arrays (loop
);
1987 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1988 fprintf (dump_file
, "\n\n");
1994 todo_flags
|= TODO_cleanup_cfg
;
1997 free_original_copy_tables ();
2004 tree_ssa_loop_prefetch (void)
2006 if (number_of_loops (cfun
) <= 1)
2009 return tree_ssa_prefetch_arrays ();
2013 gate_tree_ssa_loop_prefetch (void)
2015 return flag_prefetch_loop_arrays
> 0;
2020 const pass_data pass_data_loop_prefetch
=
2022 GIMPLE_PASS
, /* type */
2023 "aprefetch", /* name */
2024 OPTGROUP_LOOP
, /* optinfo_flags */
2025 true, /* has_gate */
2026 true, /* has_execute */
2027 TV_TREE_PREFETCH
, /* tv_id */
2028 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2029 0, /* properties_provided */
2030 0, /* properties_destroyed */
2031 0, /* todo_flags_start */
2032 0, /* todo_flags_finish */
2035 class pass_loop_prefetch
: public gimple_opt_pass
2038 pass_loop_prefetch (gcc::context
*ctxt
)
2039 : gimple_opt_pass (pass_data_loop_prefetch
, ctxt
)
2042 /* opt_pass methods: */
2043 bool gate () { return gate_tree_ssa_loop_prefetch (); }
2044 unsigned int execute () { return tree_ssa_loop_prefetch (); }
2046 }; // class pass_loop_prefetch
2051 make_pass_loop_prefetch (gcc::context
*ctxt
)
2053 return new pass_loop_prefetch (ctxt
);