2 Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "basic-block.h"
28 #include "tree-pretty-print.h"
29 #include "tree-flow.h"
31 #include "tree-pass.h"
32 #include "insn-config.h"
34 #include "tree-chrec.h"
35 #include "tree-scalar-evolution.h"
36 #include "diagnostic-core.h"
38 #include "langhooks.h"
39 #include "tree-inline.h"
40 #include "tree-data-ref.h"
43 /* FIXME: Needed for optabs, but this should all be moved to a TBD interface
44 between the GIMPLE and RTL worlds. */
49 /* This pass inserts prefetch instructions to optimize cache usage during
50 accesses to arrays in loops. It processes loops sequentially and:
52 1) Gathers all memory references in the single loop.
53 2) For each of the references it decides when it is profitable to prefetch
54 it. To do it, we evaluate the reuse among the accesses, and determines
55 two values: PREFETCH_BEFORE (meaning that it only makes sense to do
56 prefetching in the first PREFETCH_BEFORE iterations of the loop) and
57 PREFETCH_MOD (meaning that it only makes sense to prefetch in the
58 iterations of the loop that are zero modulo PREFETCH_MOD). For example
59 (assuming cache line size is 64 bytes, char has size 1 byte and there
60 is no hardware sequential prefetch):
63 for (i = 0; i < max; i++)
70 a[187*i + 50] = ...; (5)
73 (0) obviously has PREFETCH_BEFORE 1
74 (1) has PREFETCH_BEFORE 64, since (2) accesses the same memory
75 location 64 iterations before it, and PREFETCH_MOD 64 (since
76 it hits the same cache line otherwise).
77 (2) has PREFETCH_MOD 64
78 (3) has PREFETCH_MOD 4
79 (4) has PREFETCH_MOD 1. We do not set PREFETCH_BEFORE here, since
80 the cache line accessed by (5) is the same with probability only
82 (5) has PREFETCH_MOD 1 as well.
84 Additionally, we use data dependence analysis to determine for each
85 reference the distance till the first reuse; this information is used
86 to determine the temporality of the issued prefetch instruction.
88 3) We determine how much ahead we need to prefetch. The number of
89 iterations needed is time to fetch / time spent in one iteration of
90 the loop. The problem is that we do not know either of these values,
91 so we just make a heuristic guess based on a magic (possibly)
92 target-specific constant and size of the loop.
94 4) Determine which of the references we prefetch. We take into account
95 that there is a maximum number of simultaneous prefetches (provided
96 by machine description). We prefetch as many prefetches as possible
97 while still within this bound (starting with those with lowest
98 prefetch_mod, since they are responsible for most of the cache
101 5) We unroll and peel loops so that we are able to satisfy PREFETCH_MOD
102 and PREFETCH_BEFORE requirements (within some bounds), and to avoid
103 prefetching nonaccessed memory.
104 TODO -- actually implement peeling.
106 6) We actually emit the prefetch instructions. ??? Perhaps emit the
107 prefetch instructions with guards in cases where 5) was not sufficient
108 to satisfy the constraints?
110 A cost model is implemented to determine whether or not prefetching is
111 profitable for a given loop. The cost model has three heuristics:
113 1. Function trip_count_to_ahead_ratio_too_small_p implements a
114 heuristic that determines whether or not the loop has too few
115 iterations (compared to ahead). Prefetching is not likely to be
116 beneficial if the trip count to ahead ratio is below a certain
119 2. Function mem_ref_count_reasonable_p implements a heuristic that
120 determines whether the given loop has enough CPU ops that can be
121 overlapped with cache missing memory ops. If not, the loop
122 won't benefit from prefetching. In the implementation,
123 prefetching is not considered beneficial if the ratio between
124 the instruction count and the mem ref count is below a certain
127 3. Function insn_to_prefetch_ratio_too_small_p implements a
128 heuristic that disables prefetching in a loop if the prefetching
129 cost is above a certain limit. The relative prefetching cost is
130 estimated by taking the ratio between the prefetch count and the
131 total intruction count (this models the I-cache cost).
133 The limits used in these heuristics are defined as parameters with
134 reasonable default values. Machine-specific default values will be
138 -- write and use more general reuse analysis (that could be also used
139 in other cache aimed loop optimizations)
140 -- make it behave sanely together with the prefetches given by user
141 (now we just ignore them; at the very least we should avoid
142 optimizing loops in that user put his own prefetches)
143 -- we assume cache line size alignment of arrays; this could be
146 /* Magic constants follow. These should be replaced by machine specific
149 /* True if write can be prefetched by a read prefetch. */
151 #ifndef WRITE_CAN_USE_READ_PREFETCH
152 #define WRITE_CAN_USE_READ_PREFETCH 1
155 /* True if read can be prefetched by a write prefetch. */
157 #ifndef READ_CAN_USE_WRITE_PREFETCH
158 #define READ_CAN_USE_WRITE_PREFETCH 0
161 /* The size of the block loaded by a single prefetch. Usually, this is
162 the same as cache line size (at the moment, we only consider one level
163 of cache hierarchy). */
165 #ifndef PREFETCH_BLOCK
166 #define PREFETCH_BLOCK L1_CACHE_LINE_SIZE
169 /* Do we have a forward hardware sequential prefetching? */
171 #ifndef HAVE_FORWARD_PREFETCH
172 #define HAVE_FORWARD_PREFETCH 0
175 /* Do we have a backward hardware sequential prefetching? */
177 #ifndef HAVE_BACKWARD_PREFETCH
178 #define HAVE_BACKWARD_PREFETCH 0
181 /* In some cases we are only able to determine that there is a certain
182 probability that the two accesses hit the same cache line. In this
183 case, we issue the prefetches for both of them if this probability
184 is less then (1000 - ACCEPTABLE_MISS_RATE) per thousand. */
186 #ifndef ACCEPTABLE_MISS_RATE
187 #define ACCEPTABLE_MISS_RATE 50
190 #ifndef HAVE_prefetch
191 #define HAVE_prefetch 0
194 #define L1_CACHE_SIZE_BYTES ((unsigned) (L1_CACHE_SIZE * 1024))
195 #define L2_CACHE_SIZE_BYTES ((unsigned) (L2_CACHE_SIZE * 1024))
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
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. */
207 #ifndef FENCE_FOLLOWING_MOVNT
208 #define FENCE_FOLLOWING_MOVNT NULL_TREE
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
219 #ifndef TRIP_COUNT_TO_AHEAD_RATIO
220 #define TRIP_COUNT_TO_AHEAD_RATIO 4
223 /* The group of references between that reuse may occur. */
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. */
233 /* Assigned to PREFETCH_BEFORE when all iterations are to be prefetched. */
235 #define PREFETCH_ALL (~(unsigned HOST_WIDE_INT) 0)
237 /* Do not generate a prefetch if the unroll factor is significantly less
238 than what is required by the prefetch. This is to avoid redundant
239 prefetches. For example, when prefetch_mod is 16 and unroll_factor is
240 2, prefetching requires unrolling the loop 16 times, but
241 the loop is actually unrolled twice. In this case (ratio = 8),
242 prefetching is not likely to be beneficial. */
244 #ifndef PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
245 #define PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO 4
248 /* Some of the prefetch computations have quadratic complexity. We want to
249 avoid huge compile times and, therefore, want to limit the amount of
250 memory references per loop where we consider prefetching. */
252 #ifndef PREFETCH_MAX_MEM_REFS_PER_LOOP
253 #define PREFETCH_MAX_MEM_REFS_PER_LOOP 200
256 /* The memory reference. */
260 gimple stmt
; /* Statement in that the reference appears. */
261 tree mem
; /* The reference. */
262 HOST_WIDE_INT delta
; /* Constant offset of the reference. */
263 struct mem_ref_group
*group
; /* The group of references it belongs to. */
264 unsigned HOST_WIDE_INT prefetch_mod
;
265 /* Prefetch only each PREFETCH_MOD-th
267 unsigned HOST_WIDE_INT prefetch_before
;
268 /* Prefetch only first PREFETCH_BEFORE
270 unsigned reuse_distance
; /* The amount of data accessed before the first
271 reuse of this value. */
272 struct mem_ref
*next
; /* The next reference in the group. */
273 unsigned write_p
: 1; /* Is it a write? */
274 unsigned independent_p
: 1; /* True if the reference is independent on
275 all other references inside the loop. */
276 unsigned issue_prefetch_p
: 1; /* Should we really issue the prefetch? */
277 unsigned storent_p
: 1; /* True if we changed the store to a
281 /* Dumps information about memory reference */
283 dump_mem_details (FILE *file
, tree base
, tree step
,
284 HOST_WIDE_INT delta
, bool write_p
)
286 fprintf (file
, "(base ");
287 print_generic_expr (file
, base
, TDF_SLIM
);
288 fprintf (file
, ", step ");
289 if (cst_and_fits_in_hwi (step
))
290 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, int_cst_value (step
));
292 print_generic_expr (file
, step
, TDF_TREE
);
293 fprintf (file
, ")\n");
294 fprintf (file
, " delta ");
295 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, delta
);
296 fprintf (file
, "\n");
297 fprintf (file
, " %s\n", write_p
? "write" : "read");
298 fprintf (file
, "\n");
301 /* Dumps information about reference REF to FILE. */
304 dump_mem_ref (FILE *file
, struct mem_ref
*ref
)
306 fprintf (file
, "Reference %p:\n", (void *) ref
);
308 fprintf (file
, " group %p ", (void *) ref
->group
);
310 dump_mem_details (file
, ref
->group
->base
, ref
->group
->step
, ref
->delta
,
314 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
317 static struct mem_ref_group
*
318 find_or_create_group (struct mem_ref_group
**groups
, tree base
, tree step
)
320 struct mem_ref_group
*group
;
322 for (; *groups
; groups
= &(*groups
)->next
)
324 if (operand_equal_p ((*groups
)->step
, step
, 0)
325 && operand_equal_p ((*groups
)->base
, base
, 0))
328 /* If step is an integer constant, keep the list of groups sorted
329 by decreasing step. */
330 if (cst_and_fits_in_hwi ((*groups
)->step
) && cst_and_fits_in_hwi (step
)
331 && int_cst_value ((*groups
)->step
) < int_cst_value (step
))
335 group
= XNEW (struct mem_ref_group
);
339 group
->next
= *groups
;
345 /* Records a memory reference MEM in GROUP with offset DELTA and write status
346 WRITE_P. The reference occurs in statement STMT. */
349 record_ref (struct mem_ref_group
*group
, gimple stmt
, tree mem
,
350 HOST_WIDE_INT delta
, bool write_p
)
352 struct mem_ref
**aref
;
354 /* Do not record the same address twice. */
355 for (aref
= &group
->refs
; *aref
; aref
= &(*aref
)->next
)
357 /* It does not have to be possible for write reference to reuse the read
358 prefetch, or vice versa. */
359 if (!WRITE_CAN_USE_READ_PREFETCH
361 && !(*aref
)->write_p
)
363 if (!READ_CAN_USE_WRITE_PREFETCH
368 if ((*aref
)->delta
== delta
)
372 (*aref
) = XNEW (struct mem_ref
);
373 (*aref
)->stmt
= stmt
;
375 (*aref
)->delta
= delta
;
376 (*aref
)->write_p
= write_p
;
377 (*aref
)->prefetch_before
= PREFETCH_ALL
;
378 (*aref
)->prefetch_mod
= 1;
379 (*aref
)->reuse_distance
= 0;
380 (*aref
)->issue_prefetch_p
= false;
381 (*aref
)->group
= group
;
382 (*aref
)->next
= NULL
;
383 (*aref
)->independent_p
= false;
384 (*aref
)->storent_p
= false;
386 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
387 dump_mem_ref (dump_file
, *aref
);
390 /* Release memory references in GROUPS. */
393 release_mem_refs (struct mem_ref_group
*groups
)
395 struct mem_ref_group
*next_g
;
396 struct mem_ref
*ref
, *next_r
;
398 for (; groups
; groups
= next_g
)
400 next_g
= groups
->next
;
401 for (ref
= groups
->refs
; ref
; ref
= next_r
)
410 /* A structure used to pass arguments to idx_analyze_ref. */
414 struct loop
*loop
; /* Loop of the reference. */
415 gimple stmt
; /* Statement of the reference. */
416 tree
*step
; /* Step of the memory reference. */
417 HOST_WIDE_INT
*delta
; /* Offset of the memory reference. */
420 /* Analyzes a single INDEX of a memory reference to obtain information
421 described at analyze_ref. Callback for for_each_index. */
424 idx_analyze_ref (tree base
, tree
*index
, void *data
)
426 struct ar_data
*ar_data
= (struct ar_data
*) data
;
427 tree ibase
, step
, stepsize
;
428 HOST_WIDE_INT idelta
= 0, imult
= 1;
431 if (!simple_iv (ar_data
->loop
, loop_containing_stmt (ar_data
->stmt
),
437 if (TREE_CODE (ibase
) == POINTER_PLUS_EXPR
438 && cst_and_fits_in_hwi (TREE_OPERAND (ibase
, 1)))
440 idelta
= int_cst_value (TREE_OPERAND (ibase
, 1));
441 ibase
= TREE_OPERAND (ibase
, 0);
443 if (cst_and_fits_in_hwi (ibase
))
445 idelta
+= int_cst_value (ibase
);
446 ibase
= build_int_cst (TREE_TYPE (ibase
), 0);
449 if (TREE_CODE (base
) == ARRAY_REF
)
451 stepsize
= array_ref_element_size (base
);
452 if (!cst_and_fits_in_hwi (stepsize
))
454 imult
= int_cst_value (stepsize
);
455 step
= fold_build2 (MULT_EXPR
, sizetype
,
456 fold_convert (sizetype
, step
),
457 fold_convert (sizetype
, stepsize
));
461 if (*ar_data
->step
== NULL_TREE
)
462 *ar_data
->step
= step
;
464 *ar_data
->step
= fold_build2 (PLUS_EXPR
, sizetype
,
465 fold_convert (sizetype
, *ar_data
->step
),
466 fold_convert (sizetype
, step
));
467 *ar_data
->delta
+= idelta
;
473 /* Tries to express REF_P in shape &BASE + STEP * iter + DELTA, where DELTA and
474 STEP are integer constants and iter is number of iterations of LOOP. The
475 reference occurs in statement STMT. Strips nonaddressable component
476 references from REF_P. */
479 analyze_ref (struct loop
*loop
, tree
*ref_p
, tree
*base
,
480 tree
*step
, HOST_WIDE_INT
*delta
,
483 struct ar_data ar_data
;
485 HOST_WIDE_INT bit_offset
;
491 /* First strip off the component references. Ignore bitfields.
492 Also strip off the real and imagine parts of a complex, so that
493 they can have the same base. */
494 if (TREE_CODE (ref
) == REALPART_EXPR
495 || TREE_CODE (ref
) == IMAGPART_EXPR
496 || (TREE_CODE (ref
) == COMPONENT_REF
497 && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref
, 1))))
499 if (TREE_CODE (ref
) == IMAGPART_EXPR
)
500 *delta
+= int_size_in_bytes (TREE_TYPE (ref
));
501 ref
= TREE_OPERAND (ref
, 0);
506 for (; TREE_CODE (ref
) == COMPONENT_REF
; ref
= TREE_OPERAND (ref
, 0))
508 off
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
509 bit_offset
= TREE_INT_CST_LOW (off
);
510 gcc_assert (bit_offset
% BITS_PER_UNIT
== 0);
512 *delta
+= bit_offset
/ BITS_PER_UNIT
;
515 *base
= unshare_expr (ref
);
519 ar_data
.delta
= delta
;
520 return for_each_index (base
, idx_analyze_ref
, &ar_data
);
523 /* Record a memory reference REF to the list REFS. The reference occurs in
524 LOOP in statement STMT and it is write if WRITE_P. Returns true if the
525 reference was recorded, false otherwise. */
528 gather_memory_references_ref (struct loop
*loop
, struct mem_ref_group
**refs
,
529 tree ref
, bool write_p
, gimple stmt
)
533 struct mem_ref_group
*agrp
;
535 if (get_base_address (ref
) == NULL
)
538 if (!analyze_ref (loop
, &ref
, &base
, &step
, &delta
, stmt
))
540 /* If analyze_ref fails the default is a NULL_TREE. We can stop here. */
541 if (step
== NULL_TREE
)
544 /* Stop if the address of BASE could not be taken. */
545 if (may_be_nonaddressable_p (base
))
548 /* Limit non-constant step prefetching only to the innermost loops and
549 only when the step is loop invariant in the entire loop nest. */
550 if (!cst_and_fits_in_hwi (step
))
552 if (loop
->inner
!= NULL
)
554 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
556 fprintf (dump_file
, "Memory expression %p\n",(void *) ref
);
557 print_generic_expr (dump_file
, ref
, TDF_TREE
);
558 fprintf (dump_file
,":");
559 dump_mem_details( dump_file
, base
, step
, delta
, write_p
);
561 "Ignoring %p, non-constant step prefetching is "
562 "limited to inner most loops \n",
569 if (!expr_invariant_in_loop_p (loop_outermost (loop
), step
))
571 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
573 fprintf (dump_file
, "Memory expression %p\n",(void *) ref
);
574 print_generic_expr (dump_file
, ref
, TDF_TREE
);
575 fprintf (dump_file
,":");
576 dump_mem_details(dump_file
, base
, step
, delta
, write_p
);
578 "Not prefetching, ignoring %p due to "
579 "loop variant step\n",
587 /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
588 are integer constants. */
589 agrp
= find_or_create_group (refs
, base
, step
);
590 record_ref (agrp
, stmt
, ref
, delta
, write_p
);
595 /* Record the suitable memory references in LOOP. NO_OTHER_REFS is set to
596 true if there are no other memory references inside the loop. */
598 static struct mem_ref_group
*
599 gather_memory_references (struct loop
*loop
, bool *no_other_refs
, unsigned *ref_count
)
601 basic_block
*body
= get_loop_body_in_dom_order (loop
);
604 gimple_stmt_iterator bsi
;
607 struct mem_ref_group
*refs
= NULL
;
609 *no_other_refs
= true;
612 /* Scan the loop body in order, so that the former references precede the
614 for (i
= 0; i
< loop
->num_nodes
; i
++)
617 if (bb
->loop_father
!= loop
)
620 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
622 stmt
= gsi_stmt (bsi
);
624 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
626 if (gimple_vuse (stmt
)
627 || (is_gimple_call (stmt
)
628 && !(gimple_call_flags (stmt
) & ECF_CONST
)))
629 *no_other_refs
= false;
633 lhs
= gimple_assign_lhs (stmt
);
634 rhs
= gimple_assign_rhs1 (stmt
);
636 if (REFERENCE_CLASS_P (rhs
))
638 *no_other_refs
&= gather_memory_references_ref (loop
, &refs
,
642 if (REFERENCE_CLASS_P (lhs
))
644 *no_other_refs
&= gather_memory_references_ref (loop
, &refs
,
655 /* Prune the prefetch candidate REF using the self-reuse. */
658 prune_ref_by_self_reuse (struct mem_ref
*ref
)
663 /* If the step size is non constant, we cannot calculate prefetch_mod. */
664 if (!cst_and_fits_in_hwi (ref
->group
->step
))
667 step
= int_cst_value (ref
->group
->step
);
673 /* Prefetch references to invariant address just once. */
674 ref
->prefetch_before
= 1;
681 if (step
> PREFETCH_BLOCK
)
684 if ((backward
&& HAVE_BACKWARD_PREFETCH
)
685 || (!backward
&& HAVE_FORWARD_PREFETCH
))
687 ref
->prefetch_before
= 1;
691 ref
->prefetch_mod
= PREFETCH_BLOCK
/ step
;
694 /* Divides X by BY, rounding down. */
697 ddown (HOST_WIDE_INT x
, unsigned HOST_WIDE_INT by
)
704 return (x
+ by
- 1) / by
;
707 /* Given a CACHE_LINE_SIZE and two inductive memory references
708 with a common STEP greater than CACHE_LINE_SIZE and an address
709 difference DELTA, compute the probability that they will fall
710 in different cache lines. Return true if the computed miss rate
711 is not greater than the ACCEPTABLE_MISS_RATE. DISTINCT_ITERS is the
712 number of distinct iterations after which the pattern repeats itself.
713 ALIGN_UNIT is the unit of alignment in bytes. */
716 is_miss_rate_acceptable (unsigned HOST_WIDE_INT cache_line_size
,
717 HOST_WIDE_INT step
, HOST_WIDE_INT delta
,
718 unsigned HOST_WIDE_INT distinct_iters
,
721 unsigned align
, iter
;
722 int total_positions
, miss_positions
, max_allowed_miss_positions
;
723 int address1
, address2
, cache_line1
, cache_line2
;
725 /* It always misses if delta is greater than or equal to the cache
727 if (delta
>= (HOST_WIDE_INT
) cache_line_size
)
731 total_positions
= (cache_line_size
/ align_unit
) * distinct_iters
;
732 max_allowed_miss_positions
= (ACCEPTABLE_MISS_RATE
* total_positions
) / 1000;
734 /* Iterate through all possible alignments of the first
735 memory reference within its cache line. */
736 for (align
= 0; align
< cache_line_size
; align
+= align_unit
)
738 /* Iterate through all distinct iterations. */
739 for (iter
= 0; iter
< distinct_iters
; iter
++)
741 address1
= align
+ step
* iter
;
742 address2
= address1
+ delta
;
743 cache_line1
= address1
/ cache_line_size
;
744 cache_line2
= address2
/ cache_line_size
;
745 if (cache_line1
!= cache_line2
)
748 if (miss_positions
> max_allowed_miss_positions
)
755 /* Prune the prefetch candidate REF using the reuse with BY.
756 If BY_IS_BEFORE is true, BY is before REF in the loop. */
759 prune_ref_by_group_reuse (struct mem_ref
*ref
, struct mem_ref
*by
,
764 HOST_WIDE_INT delta_r
= ref
->delta
, delta_b
= by
->delta
;
765 HOST_WIDE_INT delta
= delta_b
- delta_r
;
766 HOST_WIDE_INT hit_from
;
767 unsigned HOST_WIDE_INT prefetch_before
, prefetch_block
;
768 HOST_WIDE_INT reduced_step
;
769 unsigned HOST_WIDE_INT reduced_prefetch_block
;
773 /* If the step is non constant we cannot calculate prefetch_before. */
774 if (!cst_and_fits_in_hwi (ref
->group
->step
)) {
778 step
= int_cst_value (ref
->group
->step
);
785 /* If the references has the same address, only prefetch the
788 ref
->prefetch_before
= 0;
795 /* If the reference addresses are invariant and fall into the
796 same cache line, prefetch just the first one. */
800 if (ddown (ref
->delta
, PREFETCH_BLOCK
)
801 != ddown (by
->delta
, PREFETCH_BLOCK
))
804 ref
->prefetch_before
= 0;
808 /* Only prune the reference that is behind in the array. */
814 /* Transform the data so that we may assume that the accesses
818 delta_r
= PREFETCH_BLOCK
- 1 - delta_r
;
819 delta_b
= PREFETCH_BLOCK
- 1 - delta_b
;
827 /* Check whether the two references are likely to hit the same cache
828 line, and how distant the iterations in that it occurs are from
831 if (step
<= PREFETCH_BLOCK
)
833 /* The accesses are sure to meet. Let us check when. */
834 hit_from
= ddown (delta_b
, PREFETCH_BLOCK
) * PREFETCH_BLOCK
;
835 prefetch_before
= (hit_from
- delta_r
+ step
- 1) / step
;
837 /* Do not reduce prefetch_before if we meet beyond cache size. */
838 if (prefetch_before
> absu_hwi (L2_CACHE_SIZE_BYTES
/ step
))
839 prefetch_before
= PREFETCH_ALL
;
840 if (prefetch_before
< ref
->prefetch_before
)
841 ref
->prefetch_before
= prefetch_before
;
846 /* A more complicated case with step > prefetch_block. First reduce
847 the ratio between the step and the cache line size to its simplest
848 terms. The resulting denominator will then represent the number of
849 distinct iterations after which each address will go back to its
850 initial location within the cache line. This computation assumes
851 that PREFETCH_BLOCK is a power of two. */
852 prefetch_block
= PREFETCH_BLOCK
;
853 reduced_prefetch_block
= prefetch_block
;
855 while ((reduced_step
& 1) == 0
856 && reduced_prefetch_block
> 1)
859 reduced_prefetch_block
>>= 1;
862 prefetch_before
= delta
/ step
;
864 ref_type
= TREE_TYPE (ref
->mem
);
865 align_unit
= TYPE_ALIGN (ref_type
) / 8;
866 if (is_miss_rate_acceptable (prefetch_block
, step
, delta
,
867 reduced_prefetch_block
, align_unit
))
869 /* Do not reduce prefetch_before if we meet beyond cache size. */
870 if (prefetch_before
> L2_CACHE_SIZE_BYTES
/ PREFETCH_BLOCK
)
871 prefetch_before
= PREFETCH_ALL
;
872 if (prefetch_before
< ref
->prefetch_before
)
873 ref
->prefetch_before
= prefetch_before
;
878 /* Try also the following iteration. */
880 delta
= step
- delta
;
881 if (is_miss_rate_acceptable (prefetch_block
, step
, delta
,
882 reduced_prefetch_block
, align_unit
))
884 if (prefetch_before
< ref
->prefetch_before
)
885 ref
->prefetch_before
= prefetch_before
;
890 /* The ref probably does not reuse by. */
894 /* Prune the prefetch candidate REF using the reuses with other references
898 prune_ref_by_reuse (struct mem_ref
*ref
, struct mem_ref
*refs
)
900 struct mem_ref
*prune_by
;
903 prune_ref_by_self_reuse (ref
);
905 for (prune_by
= refs
; prune_by
; prune_by
= prune_by
->next
)
913 if (!WRITE_CAN_USE_READ_PREFETCH
915 && !prune_by
->write_p
)
917 if (!READ_CAN_USE_WRITE_PREFETCH
919 && prune_by
->write_p
)
922 prune_ref_by_group_reuse (ref
, prune_by
, before
);
926 /* Prune the prefetch candidates in GROUP using the reuse analysis. */
929 prune_group_by_reuse (struct mem_ref_group
*group
)
931 struct mem_ref
*ref_pruned
;
933 for (ref_pruned
= group
->refs
; ref_pruned
; ref_pruned
= ref_pruned
->next
)
935 prune_ref_by_reuse (ref_pruned
, group
->refs
);
937 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
939 fprintf (dump_file
, "Reference %p:", (void *) ref_pruned
);
941 if (ref_pruned
->prefetch_before
== PREFETCH_ALL
942 && ref_pruned
->prefetch_mod
== 1)
943 fprintf (dump_file
, " no restrictions");
944 else if (ref_pruned
->prefetch_before
== 0)
945 fprintf (dump_file
, " do not prefetch");
946 else if (ref_pruned
->prefetch_before
<= ref_pruned
->prefetch_mod
)
947 fprintf (dump_file
, " prefetch once");
950 if (ref_pruned
->prefetch_before
!= PREFETCH_ALL
)
952 fprintf (dump_file
, " prefetch before ");
953 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
954 ref_pruned
->prefetch_before
);
956 if (ref_pruned
->prefetch_mod
!= 1)
958 fprintf (dump_file
, " prefetch mod ");
959 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
960 ref_pruned
->prefetch_mod
);
963 fprintf (dump_file
, "\n");
968 /* Prune the list of prefetch candidates GROUPS using the reuse analysis. */
971 prune_by_reuse (struct mem_ref_group
*groups
)
973 for (; groups
; groups
= groups
->next
)
974 prune_group_by_reuse (groups
);
977 /* Returns true if we should issue prefetch for REF. */
980 should_issue_prefetch_p (struct mem_ref
*ref
)
982 /* For now do not issue prefetches for only first few of the
984 if (ref
->prefetch_before
!= PREFETCH_ALL
)
986 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
987 fprintf (dump_file
, "Ignoring %p due to prefetch_before\n",
992 /* Do not prefetch nontemporal stores. */
995 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
996 fprintf (dump_file
, "Ignoring nontemporal store %p\n", (void *) ref
);
1003 /* Decide which of the prefetch candidates in GROUPS to prefetch.
1004 AHEAD is the number of iterations to prefetch ahead (which corresponds
1005 to the number of simultaneous instances of one prefetch running at a
1006 time). UNROLL_FACTOR is the factor by that the loop is going to be
1007 unrolled. Returns true if there is anything to prefetch. */
1010 schedule_prefetches (struct mem_ref_group
*groups
, unsigned unroll_factor
,
1013 unsigned remaining_prefetch_slots
, n_prefetches
, prefetch_slots
;
1014 unsigned slots_per_prefetch
;
1015 struct mem_ref
*ref
;
1018 /* At most SIMULTANEOUS_PREFETCHES should be running at the same time. */
1019 remaining_prefetch_slots
= SIMULTANEOUS_PREFETCHES
;
1021 /* The prefetch will run for AHEAD iterations of the original loop, i.e.,
1022 AHEAD / UNROLL_FACTOR iterations of the unrolled loop. In each iteration,
1023 it will need a prefetch slot. */
1024 slots_per_prefetch
= (ahead
+ unroll_factor
/ 2) / unroll_factor
;
1025 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1026 fprintf (dump_file
, "Each prefetch instruction takes %u prefetch slots.\n",
1027 slots_per_prefetch
);
1029 /* For now we just take memory references one by one and issue
1030 prefetches for as many as possible. The groups are sorted
1031 starting with the largest step, since the references with
1032 large step are more likely to cause many cache misses. */
1034 for (; groups
; groups
= groups
->next
)
1035 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1037 if (!should_issue_prefetch_p (ref
))
1040 /* The loop is far from being sufficiently unrolled for this
1041 prefetch. Do not generate prefetch to avoid many redudant
1043 if (ref
->prefetch_mod
/ unroll_factor
> PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
)
1046 /* If we need to prefetch the reference each PREFETCH_MOD iterations,
1047 and we unroll the loop UNROLL_FACTOR times, we need to insert
1048 ceil (UNROLL_FACTOR / PREFETCH_MOD) instructions in each
1050 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1051 / ref
->prefetch_mod
);
1052 prefetch_slots
= n_prefetches
* slots_per_prefetch
;
1054 /* If more than half of the prefetches would be lost anyway, do not
1055 issue the prefetch. */
1056 if (2 * remaining_prefetch_slots
< prefetch_slots
)
1059 ref
->issue_prefetch_p
= true;
1061 if (remaining_prefetch_slots
<= prefetch_slots
)
1063 remaining_prefetch_slots
-= prefetch_slots
;
1070 /* Return TRUE if no prefetch is going to be generated in the given
1074 nothing_to_prefetch_p (struct mem_ref_group
*groups
)
1076 struct mem_ref
*ref
;
1078 for (; groups
; groups
= groups
->next
)
1079 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1080 if (should_issue_prefetch_p (ref
))
1086 /* Estimate the number of prefetches in the given GROUPS.
1087 UNROLL_FACTOR is the factor by which LOOP was unrolled. */
1090 estimate_prefetch_count (struct mem_ref_group
*groups
, unsigned unroll_factor
)
1092 struct mem_ref
*ref
;
1093 unsigned n_prefetches
;
1094 int prefetch_count
= 0;
1096 for (; groups
; groups
= groups
->next
)
1097 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1098 if (should_issue_prefetch_p (ref
))
1100 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1101 / ref
->prefetch_mod
);
1102 prefetch_count
+= n_prefetches
;
1105 return prefetch_count
;
1108 /* Issue prefetches for the reference REF into loop as decided before.
1109 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR
1110 is the factor by which LOOP was unrolled. */
1113 issue_prefetch_ref (struct mem_ref
*ref
, unsigned unroll_factor
, unsigned ahead
)
1115 HOST_WIDE_INT delta
;
1116 tree addr
, addr_base
, write_p
, local
, forward
;
1118 gimple_stmt_iterator bsi
;
1119 unsigned n_prefetches
, ap
;
1120 bool nontemporal
= ref
->reuse_distance
>= L2_CACHE_SIZE_BYTES
;
1122 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1123 fprintf (dump_file
, "Issued%s prefetch for %p.\n",
1124 nontemporal
? " nontemporal" : "",
1127 bsi
= gsi_for_stmt (ref
->stmt
);
1129 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1130 / ref
->prefetch_mod
);
1131 addr_base
= build_fold_addr_expr_with_type (ref
->mem
, ptr_type_node
);
1132 addr_base
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr_base
),
1133 true, NULL
, true, GSI_SAME_STMT
);
1134 write_p
= ref
->write_p
? integer_one_node
: integer_zero_node
;
1135 local
= nontemporal
? integer_zero_node
: integer_three_node
;
1137 for (ap
= 0; ap
< n_prefetches
; ap
++)
1139 if (cst_and_fits_in_hwi (ref
->group
->step
))
1141 /* Determine the address to prefetch. */
1142 delta
= (ahead
+ ap
* ref
->prefetch_mod
) *
1143 int_cst_value (ref
->group
->step
);
1144 addr
= fold_build_pointer_plus_hwi (addr_base
, delta
);
1145 addr
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr
), true, NULL
,
1146 true, GSI_SAME_STMT
);
1150 /* The step size is non-constant but loop-invariant. We use the
1151 heuristic to simply prefetch ahead iterations ahead. */
1152 forward
= fold_build2 (MULT_EXPR
, sizetype
,
1153 fold_convert (sizetype
, ref
->group
->step
),
1154 fold_convert (sizetype
, size_int (ahead
)));
1155 addr
= fold_build_pointer_plus (addr_base
, forward
);
1156 addr
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr
), true,
1157 NULL
, true, GSI_SAME_STMT
);
1159 /* Create the prefetch instruction. */
1160 prefetch
= gimple_build_call (builtin_decl_explicit (BUILT_IN_PREFETCH
),
1161 3, addr
, write_p
, local
);
1162 gsi_insert_before (&bsi
, prefetch
, GSI_SAME_STMT
);
1166 /* Issue prefetches for the references in GROUPS into loop as decided before.
1167 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR is the
1168 factor by that LOOP was unrolled. */
1171 issue_prefetches (struct mem_ref_group
*groups
,
1172 unsigned unroll_factor
, unsigned ahead
)
1174 struct mem_ref
*ref
;
1176 for (; groups
; groups
= groups
->next
)
1177 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1178 if (ref
->issue_prefetch_p
)
1179 issue_prefetch_ref (ref
, unroll_factor
, ahead
);
1182 /* Returns true if REF is a memory write for that a nontemporal store insn
1186 nontemporal_store_p (struct mem_ref
*ref
)
1188 enum machine_mode mode
;
1189 enum insn_code code
;
1191 /* REF must be a write that is not reused. We require it to be independent
1192 on all other memory references in the loop, as the nontemporal stores may
1193 be reordered with respect to other memory references. */
1195 || !ref
->independent_p
1196 || ref
->reuse_distance
< L2_CACHE_SIZE_BYTES
)
1199 /* Check that we have the storent instruction for the mode. */
1200 mode
= TYPE_MODE (TREE_TYPE (ref
->mem
));
1201 if (mode
== BLKmode
)
1204 code
= optab_handler (storent_optab
, mode
);
1205 return code
!= CODE_FOR_nothing
;
1208 /* If REF is a nontemporal store, we mark the corresponding modify statement
1209 and return true. Otherwise, we return false. */
1212 mark_nontemporal_store (struct mem_ref
*ref
)
1214 if (!nontemporal_store_p (ref
))
1217 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1218 fprintf (dump_file
, "Marked reference %p as a nontemporal store.\n",
1221 gimple_assign_set_nontemporal_move (ref
->stmt
, true);
1222 ref
->storent_p
= true;
1227 /* Issue a memory fence instruction after LOOP. */
1230 emit_mfence_after_loop (struct loop
*loop
)
1232 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
1235 gimple_stmt_iterator bsi
;
1238 FOR_EACH_VEC_ELT (edge
, exits
, i
, exit
)
1240 call
= gimple_build_call (FENCE_FOLLOWING_MOVNT
, 0);
1242 if (!single_pred_p (exit
->dest
)
1243 /* If possible, we prefer not to insert the fence on other paths
1245 && !(exit
->flags
& EDGE_ABNORMAL
))
1246 split_loop_exit_edge (exit
);
1247 bsi
= gsi_after_labels (exit
->dest
);
1249 gsi_insert_before (&bsi
, call
, GSI_NEW_STMT
);
1252 VEC_free (edge
, heap
, exits
);
1253 update_ssa (TODO_update_ssa_only_virtuals
);
1256 /* Returns true if we can use storent in loop, false otherwise. */
1259 may_use_storent_in_loop_p (struct loop
*loop
)
1263 if (loop
->inner
!= NULL
)
1266 /* If we must issue a mfence insn after using storent, check that there
1267 is a suitable place for it at each of the loop exits. */
1268 if (FENCE_FOLLOWING_MOVNT
!= NULL_TREE
)
1270 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
1274 FOR_EACH_VEC_ELT (edge
, exits
, i
, exit
)
1275 if ((exit
->flags
& EDGE_ABNORMAL
)
1276 && exit
->dest
== EXIT_BLOCK_PTR
)
1279 VEC_free (edge
, heap
, exits
);
1285 /* Marks nontemporal stores in LOOP. GROUPS contains the description of memory
1286 references in the loop. */
1289 mark_nontemporal_stores (struct loop
*loop
, struct mem_ref_group
*groups
)
1291 struct mem_ref
*ref
;
1294 if (!may_use_storent_in_loop_p (loop
))
1297 for (; groups
; groups
= groups
->next
)
1298 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1299 any
|= mark_nontemporal_store (ref
);
1301 if (any
&& FENCE_FOLLOWING_MOVNT
!= NULL_TREE
)
1302 emit_mfence_after_loop (loop
);
1305 /* Determines whether we can profitably unroll LOOP FACTOR times, and if
1306 this is the case, fill in DESC by the description of number of
1310 should_unroll_loop_p (struct loop
*loop
, struct tree_niter_desc
*desc
,
1313 if (!can_unroll_loop_p (loop
, factor
, desc
))
1316 /* We only consider loops without control flow for unrolling. This is not
1317 a hard restriction -- tree_unroll_loop works with arbitrary loops
1318 as well; but the unrolling/prefetching is usually more profitable for
1319 loops consisting of a single basic block, and we want to limit the
1321 if (loop
->num_nodes
> 2)
1327 /* Determine the coefficient by that unroll LOOP, from the information
1328 contained in the list of memory references REFS. Description of
1329 umber of iterations of LOOP is stored to DESC. NINSNS is the number of
1330 insns of the LOOP. EST_NITER is the estimated number of iterations of
1331 the loop, or -1 if no estimate is available. */
1334 determine_unroll_factor (struct loop
*loop
, struct mem_ref_group
*refs
,
1335 unsigned ninsns
, struct tree_niter_desc
*desc
,
1336 HOST_WIDE_INT est_niter
)
1338 unsigned upper_bound
;
1339 unsigned nfactor
, factor
, mod_constraint
;
1340 struct mem_ref_group
*agp
;
1341 struct mem_ref
*ref
;
1343 /* First check whether the loop is not too large to unroll. We ignore
1344 PARAM_MAX_UNROLL_TIMES, because for small loops, it prevented us
1345 from unrolling them enough to make exactly one cache line covered by each
1346 iteration. Also, the goal of PARAM_MAX_UNROLL_TIMES is to prevent
1347 us from unrolling the loops too many times in cases where we only expect
1348 gains from better scheduling and decreasing loop overhead, which is not
1350 upper_bound
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / ninsns
;
1352 /* If we unrolled the loop more times than it iterates, the unrolled version
1353 of the loop would be never entered. */
1354 if (est_niter
>= 0 && est_niter
< (HOST_WIDE_INT
) upper_bound
)
1355 upper_bound
= est_niter
;
1357 if (upper_bound
<= 1)
1360 /* Choose the factor so that we may prefetch each cache just once,
1361 but bound the unrolling by UPPER_BOUND. */
1363 for (agp
= refs
; agp
; agp
= agp
->next
)
1364 for (ref
= agp
->refs
; ref
; ref
= ref
->next
)
1365 if (should_issue_prefetch_p (ref
))
1367 mod_constraint
= ref
->prefetch_mod
;
1368 nfactor
= least_common_multiple (mod_constraint
, factor
);
1369 if (nfactor
<= upper_bound
)
1373 if (!should_unroll_loop_p (loop
, desc
, factor
))
1379 /* Returns the total volume of the memory references REFS, taking into account
1380 reuses in the innermost loop and cache line size. TODO -- we should also
1381 take into account reuses across the iterations of the loops in the loop
1385 volume_of_references (struct mem_ref_group
*refs
)
1387 unsigned volume
= 0;
1388 struct mem_ref_group
*gr
;
1389 struct mem_ref
*ref
;
1391 for (gr
= refs
; gr
; gr
= gr
->next
)
1392 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1394 /* Almost always reuses another value? */
1395 if (ref
->prefetch_before
!= PREFETCH_ALL
)
1398 /* If several iterations access the same cache line, use the size of
1399 the line divided by this number. Otherwise, a cache line is
1400 accessed in each iteration. TODO -- in the latter case, we should
1401 take the size of the reference into account, rounding it up on cache
1402 line size multiple. */
1403 volume
+= L1_CACHE_LINE_SIZE
/ ref
->prefetch_mod
;
1408 /* Returns the volume of memory references accessed across VEC iterations of
1409 loops, whose sizes are described in the LOOP_SIZES array. N is the number
1410 of the loops in the nest (length of VEC and LOOP_SIZES vectors). */
1413 volume_of_dist_vector (lambda_vector vec
, unsigned *loop_sizes
, unsigned n
)
1417 for (i
= 0; i
< n
; i
++)
1424 gcc_assert (vec
[i
] > 0);
1426 /* We ignore the parts of the distance vector in subloops, since usually
1427 the numbers of iterations are much smaller. */
1428 return loop_sizes
[i
] * vec
[i
];
1431 /* Add the steps of ACCESS_FN multiplied by STRIDE to the array STRIDE
1432 at the position corresponding to the loop of the step. N is the depth
1433 of the considered loop nest, and, LOOP is its innermost loop. */
1436 add_subscript_strides (tree access_fn
, unsigned stride
,
1437 HOST_WIDE_INT
*strides
, unsigned n
, struct loop
*loop
)
1441 HOST_WIDE_INT astep
;
1442 unsigned min_depth
= loop_depth (loop
) - n
;
1444 while (TREE_CODE (access_fn
) == POLYNOMIAL_CHREC
)
1446 aloop
= get_chrec_loop (access_fn
);
1447 step
= CHREC_RIGHT (access_fn
);
1448 access_fn
= CHREC_LEFT (access_fn
);
1450 if ((unsigned) loop_depth (aloop
) <= min_depth
)
1453 if (host_integerp (step
, 0))
1454 astep
= tree_low_cst (step
, 0);
1456 astep
= L1_CACHE_LINE_SIZE
;
1458 strides
[n
- 1 - loop_depth (loop
) + loop_depth (aloop
)] += astep
* stride
;
1463 /* Returns the volume of memory references accessed between two consecutive
1464 self-reuses of the reference DR. We consider the subscripts of DR in N
1465 loops, and LOOP_SIZES contains the volumes of accesses in each of the
1466 loops. LOOP is the innermost loop of the current loop nest. */
1469 self_reuse_distance (data_reference_p dr
, unsigned *loop_sizes
, unsigned n
,
1472 tree stride
, access_fn
;
1473 HOST_WIDE_INT
*strides
, astride
;
1474 VEC (tree
, heap
) *access_fns
;
1475 tree ref
= DR_REF (dr
);
1476 unsigned i
, ret
= ~0u;
1478 /* In the following example:
1480 for (i = 0; i < N; i++)
1481 for (j = 0; j < N; j++)
1483 the same cache line is accessed each N steps (except if the change from
1484 i to i + 1 crosses the boundary of the cache line). Thus, for self-reuse,
1485 we cannot rely purely on the results of the data dependence analysis.
1487 Instead, we compute the stride of the reference in each loop, and consider
1488 the innermost loop in that the stride is less than cache size. */
1490 strides
= XCNEWVEC (HOST_WIDE_INT
, n
);
1491 access_fns
= DR_ACCESS_FNS (dr
);
1493 FOR_EACH_VEC_ELT (tree
, access_fns
, i
, access_fn
)
1495 /* Keep track of the reference corresponding to the subscript, so that we
1497 while (handled_component_p (ref
) && TREE_CODE (ref
) != ARRAY_REF
)
1498 ref
= TREE_OPERAND (ref
, 0);
1500 if (TREE_CODE (ref
) == ARRAY_REF
)
1502 stride
= TYPE_SIZE_UNIT (TREE_TYPE (ref
));
1503 if (host_integerp (stride
, 1))
1504 astride
= tree_low_cst (stride
, 1);
1506 astride
= L1_CACHE_LINE_SIZE
;
1508 ref
= TREE_OPERAND (ref
, 0);
1513 add_subscript_strides (access_fn
, astride
, strides
, n
, loop
);
1516 for (i
= n
; i
-- > 0; )
1518 unsigned HOST_WIDE_INT s
;
1520 s
= strides
[i
] < 0 ? -strides
[i
] : strides
[i
];
1522 if (s
< (unsigned) L1_CACHE_LINE_SIZE
1524 > (unsigned) (L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)))
1526 ret
= loop_sizes
[i
];
1535 /* Determines the distance till the first reuse of each reference in REFS
1536 in the loop nest of LOOP. NO_OTHER_REFS is true if there are no other
1537 memory references in the loop. Return false if the analysis fails. */
1540 determine_loop_nest_reuse (struct loop
*loop
, struct mem_ref_group
*refs
,
1543 struct loop
*nest
, *aloop
;
1544 VEC (data_reference_p
, heap
) *datarefs
= NULL
;
1545 VEC (ddr_p
, heap
) *dependences
= NULL
;
1546 struct mem_ref_group
*gr
;
1547 struct mem_ref
*ref
, *refb
;
1548 VEC (loop_p
, heap
) *vloops
= NULL
;
1549 unsigned *loop_data_size
;
1551 unsigned volume
, dist
, adist
;
1553 data_reference_p dr
;
1559 /* Find the outermost loop of the loop nest of loop (we require that
1560 there are no sibling loops inside the nest). */
1564 aloop
= loop_outer (nest
);
1566 if (aloop
== current_loops
->tree_root
1567 || aloop
->inner
->next
)
1573 /* For each loop, determine the amount of data accessed in each iteration.
1574 We use this to estimate whether the reference is evicted from the
1575 cache before its reuse. */
1576 find_loop_nest (nest
, &vloops
);
1577 n
= VEC_length (loop_p
, vloops
);
1578 loop_data_size
= XNEWVEC (unsigned, n
);
1579 volume
= volume_of_references (refs
);
1583 loop_data_size
[i
] = volume
;
1584 /* Bound the volume by the L2 cache size, since above this bound,
1585 all dependence distances are equivalent. */
1586 if (volume
> L2_CACHE_SIZE_BYTES
)
1589 aloop
= VEC_index (loop_p
, vloops
, i
);
1590 vol
= estimated_stmt_executions_int (aloop
);
1592 vol
= expected_loop_iterations (aloop
);
1596 /* Prepare the references in the form suitable for data dependence
1597 analysis. We ignore unanalyzable data references (the results
1598 are used just as a heuristics to estimate temporality of the
1599 references, hence we do not need to worry about correctness). */
1600 for (gr
= refs
; gr
; gr
= gr
->next
)
1601 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1603 dr
= create_data_ref (nest
, loop_containing_stmt (ref
->stmt
),
1604 ref
->mem
, ref
->stmt
, !ref
->write_p
);
1608 ref
->reuse_distance
= volume
;
1610 VEC_safe_push (data_reference_p
, heap
, datarefs
, dr
);
1613 no_other_refs
= false;
1616 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
1618 dist
= self_reuse_distance (dr
, loop_data_size
, n
, loop
);
1619 ref
= (struct mem_ref
*) dr
->aux
;
1620 if (ref
->reuse_distance
> dist
)
1621 ref
->reuse_distance
= dist
;
1624 ref
->independent_p
= true;
1627 if (!compute_all_dependences (datarefs
, &dependences
, vloops
, true))
1630 FOR_EACH_VEC_ELT (ddr_p
, dependences
, i
, dep
)
1632 if (DDR_ARE_DEPENDENT (dep
) == chrec_known
)
1635 ref
= (struct mem_ref
*) DDR_A (dep
)->aux
;
1636 refb
= (struct mem_ref
*) DDR_B (dep
)->aux
;
1638 if (DDR_ARE_DEPENDENT (dep
) == chrec_dont_know
1639 || DDR_NUM_DIST_VECTS (dep
) == 0)
1641 /* If the dependence cannot be analyzed, assume that there might be
1645 ref
->independent_p
= false;
1646 refb
->independent_p
= false;
1650 /* The distance vectors are normalized to be always lexicographically
1651 positive, hence we cannot tell just from them whether DDR_A comes
1652 before DDR_B or vice versa. However, it is not important,
1653 anyway -- if DDR_A is close to DDR_B, then it is either reused in
1654 DDR_B (and it is not nontemporal), or it reuses the value of DDR_B
1655 in cache (and marking it as nontemporal would not affect
1659 for (j
= 0; j
< DDR_NUM_DIST_VECTS (dep
); j
++)
1661 adist
= volume_of_dist_vector (DDR_DIST_VECT (dep
, j
),
1664 /* If this is a dependence in the innermost loop (i.e., the
1665 distances in all superloops are zero) and it is not
1666 the trivial self-dependence with distance zero, record that
1667 the references are not completely independent. */
1668 if (lambda_vector_zerop (DDR_DIST_VECT (dep
, j
), n
- 1)
1670 || DDR_DIST_VECT (dep
, j
)[n
-1] != 0))
1672 ref
->independent_p
= false;
1673 refb
->independent_p
= false;
1676 /* Ignore accesses closer than
1677 L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
1678 so that we use nontemporal prefetches e.g. if single memory
1679 location is accessed several times in a single iteration of
1681 if (adist
< L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)
1689 if (ref
->reuse_distance
> dist
)
1690 ref
->reuse_distance
= dist
;
1691 if (refb
->reuse_distance
> dist
)
1692 refb
->reuse_distance
= dist
;
1695 free_dependence_relations (dependences
);
1696 free_data_refs (datarefs
);
1697 free (loop_data_size
);
1699 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1701 fprintf (dump_file
, "Reuse distances:\n");
1702 for (gr
= refs
; gr
; gr
= gr
->next
)
1703 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1704 fprintf (dump_file
, " ref %p distance %u\n",
1705 (void *) ref
, ref
->reuse_distance
);
1711 /* Determine whether or not the trip count to ahead ratio is too small based
1712 on prefitablility consideration.
1713 AHEAD: the iteration ahead distance,
1714 EST_NITER: the estimated trip count. */
1717 trip_count_to_ahead_ratio_too_small_p (unsigned ahead
, HOST_WIDE_INT est_niter
)
1719 /* Assume trip count to ahead ratio is big enough if the trip count could not
1720 be estimated at compile time. */
1724 if (est_niter
< (HOST_WIDE_INT
) (TRIP_COUNT_TO_AHEAD_RATIO
* ahead
))
1726 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1728 "Not prefetching -- loop estimated to roll only %d times\n",
1736 /* Determine whether or not the number of memory references in the loop is
1737 reasonable based on the profitablity and compilation time considerations.
1738 NINSNS: estimated number of instructions in the loop,
1739 MEM_REF_COUNT: total number of memory references in the loop. */
1742 mem_ref_count_reasonable_p (unsigned ninsns
, unsigned mem_ref_count
)
1744 int insn_to_mem_ratio
;
1746 if (mem_ref_count
== 0)
1749 /* Miss rate computation (is_miss_rate_acceptable) and dependence analysis
1750 (compute_all_dependences) have high costs based on quadratic complexity.
1751 To avoid huge compilation time, we give up prefetching if mem_ref_count
1753 if (mem_ref_count
> PREFETCH_MAX_MEM_REFS_PER_LOOP
)
1756 /* Prefetching improves performance by overlapping cache missing
1757 memory accesses with CPU operations. If the loop does not have
1758 enough CPU operations to overlap with memory operations, prefetching
1759 won't give a significant benefit. One approximate way of checking
1760 this is to require the ratio of instructions to memory references to
1761 be above a certain limit. This approximation works well in practice.
1762 TODO: Implement a more precise computation by estimating the time
1763 for each CPU or memory op in the loop. Time estimates for memory ops
1764 should account for cache misses. */
1765 insn_to_mem_ratio
= ninsns
/ mem_ref_count
;
1767 if (insn_to_mem_ratio
< PREFETCH_MIN_INSN_TO_MEM_RATIO
)
1769 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1771 "Not prefetching -- instruction to memory reference ratio (%d) too small\n",
1779 /* Determine whether or not the instruction to prefetch ratio in the loop is
1780 too small based on the profitablity consideration.
1781 NINSNS: estimated number of instructions in the loop,
1782 PREFETCH_COUNT: an estimate of the number of prefetches,
1783 UNROLL_FACTOR: the factor to unroll the loop if prefetching. */
1786 insn_to_prefetch_ratio_too_small_p (unsigned ninsns
, unsigned prefetch_count
,
1787 unsigned unroll_factor
)
1789 int insn_to_prefetch_ratio
;
1791 /* Prefetching most likely causes performance degradation when the instruction
1792 to prefetch ratio is too small. Too many prefetch instructions in a loop
1793 may reduce the I-cache performance.
1794 (unroll_factor * ninsns) is used to estimate the number of instructions in
1795 the unrolled loop. This implementation is a bit simplistic -- the number
1796 of issued prefetch instructions is also affected by unrolling. So,
1797 prefetch_mod and the unroll factor should be taken into account when
1798 determining prefetch_count. Also, the number of insns of the unrolled
1799 loop will usually be significantly smaller than the number of insns of the
1800 original loop * unroll_factor (at least the induction variable increases
1801 and the exit branches will get eliminated), so it might be better to use
1802 tree_estimate_loop_size + estimated_unrolled_size. */
1803 insn_to_prefetch_ratio
= (unroll_factor
* ninsns
) / prefetch_count
;
1804 if (insn_to_prefetch_ratio
< MIN_INSN_TO_PREFETCH_RATIO
)
1806 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1808 "Not prefetching -- instruction to prefetch ratio (%d) too small\n",
1809 insn_to_prefetch_ratio
);
1817 /* Issue prefetch instructions for array references in LOOP. Returns
1818 true if the LOOP was unrolled. */
1821 loop_prefetch_arrays (struct loop
*loop
)
1823 struct mem_ref_group
*refs
;
1824 unsigned ahead
, ninsns
, time
, unroll_factor
;
1825 HOST_WIDE_INT est_niter
;
1826 struct tree_niter_desc desc
;
1827 bool unrolled
= false, no_other_refs
;
1828 unsigned prefetch_count
;
1829 unsigned mem_ref_count
;
1831 if (optimize_loop_nest_for_size_p (loop
))
1833 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1834 fprintf (dump_file
, " ignored (cold area)\n");
1838 /* FIXME: the time should be weighted by the probabilities of the blocks in
1840 time
= tree_num_loop_insns (loop
, &eni_time_weights
);
1844 ahead
= (PREFETCH_LATENCY
+ time
- 1) / time
;
1845 est_niter
= estimated_stmt_executions_int (loop
);
1846 if (est_niter
== -1)
1847 est_niter
= max_stmt_executions_int (loop
);
1849 /* Prefetching is not likely to be profitable if the trip count to ahead
1850 ratio is too small. */
1851 if (trip_count_to_ahead_ratio_too_small_p (ahead
, est_niter
))
1854 ninsns
= tree_num_loop_insns (loop
, &eni_size_weights
);
1856 /* Step 1: gather the memory references. */
1857 refs
= gather_memory_references (loop
, &no_other_refs
, &mem_ref_count
);
1859 /* Give up prefetching if the number of memory references in the
1860 loop is not reasonable based on profitablity and compilation time
1862 if (!mem_ref_count_reasonable_p (ninsns
, mem_ref_count
))
1865 /* Step 2: estimate the reuse effects. */
1866 prune_by_reuse (refs
);
1868 if (nothing_to_prefetch_p (refs
))
1871 if (!determine_loop_nest_reuse (loop
, refs
, no_other_refs
))
1874 /* Step 3: determine unroll factor. */
1875 unroll_factor
= determine_unroll_factor (loop
, refs
, ninsns
, &desc
,
1878 /* Estimate prefetch count for the unrolled loop. */
1879 prefetch_count
= estimate_prefetch_count (refs
, unroll_factor
);
1880 if (prefetch_count
== 0)
1883 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1884 fprintf (dump_file
, "Ahead %d, unroll factor %d, trip count "
1885 HOST_WIDE_INT_PRINT_DEC
"\n"
1886 "insn count %d, mem ref count %d, prefetch count %d\n",
1887 ahead
, unroll_factor
, est_niter
,
1888 ninsns
, mem_ref_count
, prefetch_count
);
1890 /* Prefetching is not likely to be profitable if the instruction to prefetch
1891 ratio is too small. */
1892 if (insn_to_prefetch_ratio_too_small_p (ninsns
, prefetch_count
,
1896 mark_nontemporal_stores (loop
, refs
);
1898 /* Step 4: what to prefetch? */
1899 if (!schedule_prefetches (refs
, unroll_factor
, ahead
))
1902 /* Step 5: unroll the loop. TODO -- peeling of first and last few
1903 iterations so that we do not issue superfluous prefetches. */
1904 if (unroll_factor
!= 1)
1906 tree_unroll_loop (loop
, unroll_factor
,
1907 single_dom_exit (loop
), &desc
);
1911 /* Step 6: issue the prefetches. */
1912 issue_prefetches (refs
, unroll_factor
, ahead
);
1915 release_mem_refs (refs
);
1919 /* Issue prefetch instructions for array references in loops. */
1922 tree_ssa_prefetch_arrays (void)
1926 bool unrolled
= false;
1930 /* It is possible to ask compiler for say -mtune=i486 -march=pentium4.
1931 -mtune=i486 causes us having PREFETCH_BLOCK 0, since this is part
1932 of processor costs and i486 does not have prefetch, but
1933 -march=pentium4 causes HAVE_prefetch to be true. Ugh. */
1934 || PREFETCH_BLOCK
== 0)
1937 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1939 fprintf (dump_file
, "Prefetching parameters:\n");
1940 fprintf (dump_file
, " simultaneous prefetches: %d\n",
1941 SIMULTANEOUS_PREFETCHES
);
1942 fprintf (dump_file
, " prefetch latency: %d\n", PREFETCH_LATENCY
);
1943 fprintf (dump_file
, " prefetch block size: %d\n", PREFETCH_BLOCK
);
1944 fprintf (dump_file
, " L1 cache size: %d lines, %d kB\n",
1945 L1_CACHE_SIZE_BYTES
/ L1_CACHE_LINE_SIZE
, L1_CACHE_SIZE
);
1946 fprintf (dump_file
, " L1 cache line size: %d\n", L1_CACHE_LINE_SIZE
);
1947 fprintf (dump_file
, " L2 cache size: %d kB\n", L2_CACHE_SIZE
);
1948 fprintf (dump_file
, " min insn-to-prefetch ratio: %d \n",
1949 MIN_INSN_TO_PREFETCH_RATIO
);
1950 fprintf (dump_file
, " min insn-to-mem ratio: %d \n",
1951 PREFETCH_MIN_INSN_TO_MEM_RATIO
);
1952 fprintf (dump_file
, "\n");
1955 initialize_original_copy_tables ();
1957 if (!builtin_decl_explicit_p (BUILT_IN_PREFETCH
))
1959 tree type
= build_function_type_list (void_type_node
,
1960 const_ptr_type_node
, NULL_TREE
);
1961 tree decl
= add_builtin_function ("__builtin_prefetch", type
,
1962 BUILT_IN_PREFETCH
, BUILT_IN_NORMAL
,
1964 DECL_IS_NOVOPS (decl
) = true;
1965 set_builtin_decl (BUILT_IN_PREFETCH
, decl
, false);
1968 /* We assume that size of cache line is a power of two, so verify this
1970 gcc_assert ((PREFETCH_BLOCK
& (PREFETCH_BLOCK
- 1)) == 0);
1972 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1974 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1975 fprintf (dump_file
, "Processing loop %d:\n", loop
->num
);
1977 unrolled
|= loop_prefetch_arrays (loop
);
1979 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1980 fprintf (dump_file
, "\n\n");
1986 todo_flags
|= TODO_cleanup_cfg
;
1989 free_original_copy_tables ();