2 Copyright (C) 2005-2016 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"
29 #include "tree-pass.h"
30 #include "gimple-ssa.h"
31 #include "optabs-query.h"
32 #include "tree-pretty-print.h"
33 #include "fold-const.h"
34 #include "stor-layout.h"
36 #include "gimple-iterator.h"
37 #include "gimplify-me.h"
38 #include "tree-ssa-loop-ivopts.h"
39 #include "tree-ssa-loop-manip.h"
40 #include "tree-ssa-loop-niter.h"
41 #include "tree-ssa-loop.h"
42 #include "tree-into-ssa.h"
44 #include "tree-scalar-evolution.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. */
54 /* This pass inserts prefetch instructions to optimize cache usage during
55 accesses to arrays in loops. It processes loops sequentially and:
57 1) Gathers all memory references in the single loop.
58 2) For each of the references it decides when it is profitable to prefetch
59 it. To do it, we evaluate the reuse among the accesses, and determines
60 two values: PREFETCH_BEFORE (meaning that it only makes sense to do
61 prefetching in the first PREFETCH_BEFORE iterations of the loop) and
62 PREFETCH_MOD (meaning that it only makes sense to prefetch in the
63 iterations of the loop that are zero modulo PREFETCH_MOD). For example
64 (assuming cache line size is 64 bytes, char has size 1 byte and there
65 is no hardware sequential prefetch):
68 for (i = 0; i < max; i++)
75 a[187*i + 50] = ...; (5)
78 (0) obviously has PREFETCH_BEFORE 1
79 (1) has PREFETCH_BEFORE 64, since (2) accesses the same memory
80 location 64 iterations before it, and PREFETCH_MOD 64 (since
81 it hits the same cache line otherwise).
82 (2) has PREFETCH_MOD 64
83 (3) has PREFETCH_MOD 4
84 (4) has PREFETCH_MOD 1. We do not set PREFETCH_BEFORE here, since
85 the cache line accessed by (5) is the same with probability only
87 (5) has PREFETCH_MOD 1 as well.
89 Additionally, we use data dependence analysis to determine for each
90 reference the distance till the first reuse; this information is used
91 to determine the temporality of the issued prefetch instruction.
93 3) We determine how much ahead we need to prefetch. The number of
94 iterations needed is time to fetch / time spent in one iteration of
95 the loop. The problem is that we do not know either of these values,
96 so we just make a heuristic guess based on a magic (possibly)
97 target-specific constant and size of the loop.
99 4) Determine which of the references we prefetch. We take into account
100 that there is a maximum number of simultaneous prefetches (provided
101 by machine description). We prefetch as many prefetches as possible
102 while still within this bound (starting with those with lowest
103 prefetch_mod, since they are responsible for most of the cache
106 5) We unroll and peel loops so that we are able to satisfy PREFETCH_MOD
107 and PREFETCH_BEFORE requirements (within some bounds), and to avoid
108 prefetching nonaccessed memory.
109 TODO -- actually implement peeling.
111 6) We actually emit the prefetch instructions. ??? Perhaps emit the
112 prefetch instructions with guards in cases where 5) was not sufficient
113 to satisfy the constraints?
115 A cost model is implemented to determine whether or not prefetching is
116 profitable for a given loop. The cost model has three heuristics:
118 1. Function trip_count_to_ahead_ratio_too_small_p implements a
119 heuristic that determines whether or not the loop has too few
120 iterations (compared to ahead). Prefetching is not likely to be
121 beneficial if the trip count to ahead ratio is below a certain
124 2. Function mem_ref_count_reasonable_p implements a heuristic that
125 determines whether the given loop has enough CPU ops that can be
126 overlapped with cache missing memory ops. If not, the loop
127 won't benefit from prefetching. In the implementation,
128 prefetching is not considered beneficial if the ratio between
129 the instruction count and the mem ref count is below a certain
132 3. Function insn_to_prefetch_ratio_too_small_p implements a
133 heuristic that disables prefetching in a loop if the prefetching
134 cost is above a certain limit. The relative prefetching cost is
135 estimated by taking the ratio between the prefetch count and the
136 total intruction count (this models the I-cache cost).
138 The limits used in these heuristics are defined as parameters with
139 reasonable default values. Machine-specific default values will be
143 -- write and use more general reuse analysis (that could be also used
144 in other cache aimed loop optimizations)
145 -- make it behave sanely together with the prefetches given by user
146 (now we just ignore them; at the very least we should avoid
147 optimizing loops in that user put his own prefetches)
148 -- we assume cache line size alignment of arrays; this could be
151 /* Magic constants follow. These should be replaced by machine specific
154 /* True if write can be prefetched by a read prefetch. */
156 #ifndef WRITE_CAN_USE_READ_PREFETCH
157 #define WRITE_CAN_USE_READ_PREFETCH 1
160 /* True if read can be prefetched by a write prefetch. */
162 #ifndef READ_CAN_USE_WRITE_PREFETCH
163 #define READ_CAN_USE_WRITE_PREFETCH 0
166 /* The size of the block loaded by a single prefetch. Usually, this is
167 the same as cache line size (at the moment, we only consider one level
168 of cache hierarchy). */
170 #ifndef PREFETCH_BLOCK
171 #define PREFETCH_BLOCK L1_CACHE_LINE_SIZE
174 /* Do we have a forward hardware sequential prefetching? */
176 #ifndef HAVE_FORWARD_PREFETCH
177 #define HAVE_FORWARD_PREFETCH 0
180 /* Do we have a backward hardware sequential prefetching? */
182 #ifndef HAVE_BACKWARD_PREFETCH
183 #define HAVE_BACKWARD_PREFETCH 0
186 /* In some cases we are only able to determine that there is a certain
187 probability that the two accesses hit the same cache line. In this
188 case, we issue the prefetches for both of them if this probability
189 is less then (1000 - ACCEPTABLE_MISS_RATE) per thousand. */
191 #ifndef ACCEPTABLE_MISS_RATE
192 #define ACCEPTABLE_MISS_RATE 50
195 #define L1_CACHE_SIZE_BYTES ((unsigned) (L1_CACHE_SIZE * 1024))
196 #define L2_CACHE_SIZE_BYTES ((unsigned) (L2_CACHE_SIZE * 1024))
198 /* We consider a memory access nontemporal if it is not reused sooner than
199 after L2_CACHE_SIZE_BYTES of memory are accessed. However, we ignore
200 accesses closer than L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
201 so that we use nontemporal prefetches e.g. if single memory location
202 is accessed several times in a single iteration of the loop. */
203 #define NONTEMPORAL_FRACTION 16
205 /* In case we have to emit a memory fence instruction after the loop that
206 uses nontemporal stores, this defines the builtin to use. */
208 #ifndef FENCE_FOLLOWING_MOVNT
209 #define FENCE_FOLLOWING_MOVNT NULL_TREE
212 /* It is not profitable to prefetch when the trip count is not at
213 least TRIP_COUNT_TO_AHEAD_RATIO times the prefetch ahead distance.
214 For example, in a loop with a prefetch ahead distance of 10,
215 supposing that TRIP_COUNT_TO_AHEAD_RATIO is equal to 4, it is
216 profitable to prefetch when the trip count is greater or equal to
217 40. In that case, 30 out of the 40 iterations will benefit from
220 #ifndef TRIP_COUNT_TO_AHEAD_RATIO
221 #define TRIP_COUNT_TO_AHEAD_RATIO 4
224 /* The group of references between that reuse may occur. */
228 tree base
; /* Base of the reference. */
229 tree step
; /* Step of the reference. */
230 struct mem_ref
*refs
; /* References in the group. */
231 struct mem_ref_group
*next
; /* Next group of references. */
234 /* Assigned to PREFETCH_BEFORE when all iterations are to be prefetched. */
236 #define PREFETCH_ALL (~(unsigned HOST_WIDE_INT) 0)
238 /* Do not generate a prefetch if the unroll factor is significantly less
239 than what is required by the prefetch. This is to avoid redundant
240 prefetches. For example, when prefetch_mod is 16 and unroll_factor is
241 2, prefetching requires unrolling the loop 16 times, but
242 the loop is actually unrolled twice. In this case (ratio = 8),
243 prefetching is not likely to be beneficial. */
245 #ifndef PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
246 #define PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO 4
249 /* Some of the prefetch computations have quadratic complexity. We want to
250 avoid huge compile times and, therefore, want to limit the amount of
251 memory references per loop where we consider prefetching. */
253 #ifndef PREFETCH_MAX_MEM_REFS_PER_LOOP
254 #define PREFETCH_MAX_MEM_REFS_PER_LOOP 200
257 /* The memory reference. */
261 gimple
*stmt
; /* Statement in that the reference appears. */
262 tree mem
; /* The reference. */
263 HOST_WIDE_INT delta
; /* Constant offset of the reference. */
264 struct mem_ref_group
*group
; /* The group of references it belongs to. */
265 unsigned HOST_WIDE_INT prefetch_mod
;
266 /* Prefetch only each PREFETCH_MOD-th
268 unsigned HOST_WIDE_INT prefetch_before
;
269 /* Prefetch only first PREFETCH_BEFORE
271 unsigned reuse_distance
; /* The amount of data accessed before the first
272 reuse of this value. */
273 struct mem_ref
*next
; /* The next reference in the group. */
274 unsigned write_p
: 1; /* Is it a write? */
275 unsigned independent_p
: 1; /* True if the reference is independent on
276 all other references inside the loop. */
277 unsigned issue_prefetch_p
: 1; /* Should we really issue the prefetch? */
278 unsigned storent_p
: 1; /* True if we changed the store to a
282 /* Dumps information about memory reference */
284 dump_mem_details (FILE *file
, tree base
, tree step
,
285 HOST_WIDE_INT delta
, bool write_p
)
287 fprintf (file
, "(base ");
288 print_generic_expr (file
, base
, TDF_SLIM
);
289 fprintf (file
, ", step ");
290 if (cst_and_fits_in_hwi (step
))
291 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, int_cst_value (step
));
293 print_generic_expr (file
, step
, TDF_TREE
);
294 fprintf (file
, ")\n");
295 fprintf (file
, " delta ");
296 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, delta
);
297 fprintf (file
, "\n");
298 fprintf (file
, " %s\n", write_p
? "write" : "read");
299 fprintf (file
, "\n");
302 /* Dumps information about reference REF to FILE. */
305 dump_mem_ref (FILE *file
, struct mem_ref
*ref
)
307 fprintf (file
, "Reference %p:\n", (void *) ref
);
309 fprintf (file
, " group %p ", (void *) ref
->group
);
311 dump_mem_details (file
, ref
->group
->base
, ref
->group
->step
, ref
->delta
,
315 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
318 static struct mem_ref_group
*
319 find_or_create_group (struct mem_ref_group
**groups
, tree base
, tree step
)
321 struct mem_ref_group
*group
;
323 for (; *groups
; groups
= &(*groups
)->next
)
325 if (operand_equal_p ((*groups
)->step
, step
, 0)
326 && operand_equal_p ((*groups
)->base
, base
, 0))
329 /* If step is an integer constant, keep the list of groups sorted
330 by decreasing step. */
331 if (cst_and_fits_in_hwi ((*groups
)->step
) && cst_and_fits_in_hwi (step
)
332 && int_cst_value ((*groups
)->step
) < int_cst_value (step
))
336 group
= XNEW (struct mem_ref_group
);
340 group
->next
= *groups
;
346 /* Records a memory reference MEM in GROUP with offset DELTA and write status
347 WRITE_P. The reference occurs in statement STMT. */
350 record_ref (struct mem_ref_group
*group
, gimple
*stmt
, tree mem
,
351 HOST_WIDE_INT delta
, bool write_p
)
353 struct mem_ref
**aref
;
355 /* Do not record the same address twice. */
356 for (aref
= &group
->refs
; *aref
; aref
= &(*aref
)->next
)
358 /* It does not have to be possible for write reference to reuse the read
359 prefetch, or vice versa. */
360 if (!WRITE_CAN_USE_READ_PREFETCH
362 && !(*aref
)->write_p
)
364 if (!READ_CAN_USE_WRITE_PREFETCH
369 if ((*aref
)->delta
== delta
)
373 (*aref
) = XNEW (struct mem_ref
);
374 (*aref
)->stmt
= stmt
;
376 (*aref
)->delta
= delta
;
377 (*aref
)->write_p
= write_p
;
378 (*aref
)->prefetch_before
= PREFETCH_ALL
;
379 (*aref
)->prefetch_mod
= 1;
380 (*aref
)->reuse_distance
= 0;
381 (*aref
)->issue_prefetch_p
= false;
382 (*aref
)->group
= group
;
383 (*aref
)->next
= NULL
;
384 (*aref
)->independent_p
= false;
385 (*aref
)->storent_p
= false;
387 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
388 dump_mem_ref (dump_file
, *aref
);
391 /* Release memory references in GROUPS. */
394 release_mem_refs (struct mem_ref_group
*groups
)
396 struct mem_ref_group
*next_g
;
397 struct mem_ref
*ref
, *next_r
;
399 for (; groups
; groups
= next_g
)
401 next_g
= groups
->next
;
402 for (ref
= groups
->refs
; ref
; ref
= next_r
)
411 /* A structure used to pass arguments to idx_analyze_ref. */
415 struct loop
*loop
; /* Loop of the reference. */
416 gimple
*stmt
; /* Statement of the reference. */
417 tree
*step
; /* Step of the memory reference. */
418 HOST_WIDE_INT
*delta
; /* Offset of the memory reference. */
421 /* Analyzes a single INDEX of a memory reference to obtain information
422 described at analyze_ref. Callback for for_each_index. */
425 idx_analyze_ref (tree base
, tree
*index
, void *data
)
427 struct ar_data
*ar_data
= (struct ar_data
*) data
;
428 tree ibase
, step
, stepsize
;
429 HOST_WIDE_INT idelta
= 0, imult
= 1;
432 if (!simple_iv (ar_data
->loop
, loop_containing_stmt (ar_data
->stmt
),
438 if (TREE_CODE (ibase
) == POINTER_PLUS_EXPR
439 && cst_and_fits_in_hwi (TREE_OPERAND (ibase
, 1)))
441 idelta
= int_cst_value (TREE_OPERAND (ibase
, 1));
442 ibase
= TREE_OPERAND (ibase
, 0);
444 if (cst_and_fits_in_hwi (ibase
))
446 idelta
+= int_cst_value (ibase
);
447 ibase
= build_int_cst (TREE_TYPE (ibase
), 0);
450 if (TREE_CODE (base
) == ARRAY_REF
)
452 stepsize
= array_ref_element_size (base
);
453 if (!cst_and_fits_in_hwi (stepsize
))
455 imult
= int_cst_value (stepsize
);
456 step
= fold_build2 (MULT_EXPR
, sizetype
,
457 fold_convert (sizetype
, step
),
458 fold_convert (sizetype
, stepsize
));
462 if (*ar_data
->step
== NULL_TREE
)
463 *ar_data
->step
= step
;
465 *ar_data
->step
= fold_build2 (PLUS_EXPR
, sizetype
,
466 fold_convert (sizetype
, *ar_data
->step
),
467 fold_convert (sizetype
, step
));
468 *ar_data
->delta
+= idelta
;
474 /* Tries to express REF_P in shape &BASE + STEP * iter + DELTA, where DELTA and
475 STEP are integer constants and iter is number of iterations of LOOP. The
476 reference occurs in statement STMT. Strips nonaddressable component
477 references from REF_P. */
480 analyze_ref (struct loop
*loop
, tree
*ref_p
, tree
*base
,
481 tree
*step
, HOST_WIDE_INT
*delta
,
484 struct ar_data ar_data
;
486 HOST_WIDE_INT bit_offset
;
492 /* First strip off the component references. Ignore bitfields.
493 Also strip off the real and imagine parts of a complex, so that
494 they can have the same base. */
495 if (TREE_CODE (ref
) == REALPART_EXPR
496 || TREE_CODE (ref
) == IMAGPART_EXPR
497 || (TREE_CODE (ref
) == COMPONENT_REF
498 && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref
, 1))))
500 if (TREE_CODE (ref
) == IMAGPART_EXPR
)
501 *delta
+= int_size_in_bytes (TREE_TYPE (ref
));
502 ref
= TREE_OPERAND (ref
, 0);
507 for (; TREE_CODE (ref
) == COMPONENT_REF
; ref
= TREE_OPERAND (ref
, 0))
509 off
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
510 bit_offset
= TREE_INT_CST_LOW (off
);
511 gcc_assert (bit_offset
% BITS_PER_UNIT
== 0);
513 *delta
+= bit_offset
/ BITS_PER_UNIT
;
516 *base
= unshare_expr (ref
);
520 ar_data
.delta
= delta
;
521 return for_each_index (base
, idx_analyze_ref
, &ar_data
);
524 /* Record a memory reference REF to the list REFS. The reference occurs in
525 LOOP in statement STMT and it is write if WRITE_P. Returns true if the
526 reference was recorded, false otherwise. */
529 gather_memory_references_ref (struct loop
*loop
, struct mem_ref_group
**refs
,
530 tree ref
, bool write_p
, gimple
*stmt
)
534 struct mem_ref_group
*agrp
;
536 if (get_base_address (ref
) == NULL
)
539 if (!analyze_ref (loop
, &ref
, &base
, &step
, &delta
, stmt
))
541 /* If analyze_ref fails the default is a NULL_TREE. We can stop here. */
542 if (step
== NULL_TREE
)
545 /* Stop if the address of BASE could not be taken. */
546 if (may_be_nonaddressable_p (base
))
549 /* Limit non-constant step prefetching only to the innermost loops and
550 only when the step is loop invariant in the entire loop nest. */
551 if (!cst_and_fits_in_hwi (step
))
553 if (loop
->inner
!= NULL
)
555 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
557 fprintf (dump_file
, "Memory expression %p\n",(void *) ref
);
558 print_generic_expr (dump_file
, ref
, TDF_TREE
);
559 fprintf (dump_file
,":");
560 dump_mem_details (dump_file
, base
, step
, delta
, write_p
);
562 "Ignoring %p, non-constant step prefetching is "
563 "limited to inner most loops \n",
570 if (!expr_invariant_in_loop_p (loop_outermost (loop
), step
))
572 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
574 fprintf (dump_file
, "Memory expression %p\n",(void *) ref
);
575 print_generic_expr (dump_file
, ref
, TDF_TREE
);
576 fprintf (dump_file
,":");
577 dump_mem_details (dump_file
, base
, step
, delta
, write_p
);
579 "Not prefetching, ignoring %p due to "
580 "loop variant step\n",
588 /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
589 are integer constants. */
590 agrp
= find_or_create_group (refs
, base
, step
);
591 record_ref (agrp
, stmt
, ref
, delta
, write_p
);
596 /* Record the suitable memory references in LOOP. NO_OTHER_REFS is set to
597 true if there are no other memory references inside the loop. */
599 static struct mem_ref_group
*
600 gather_memory_references (struct loop
*loop
, bool *no_other_refs
, unsigned *ref_count
)
602 basic_block
*body
= get_loop_body_in_dom_order (loop
);
605 gimple_stmt_iterator bsi
;
608 struct mem_ref_group
*refs
= NULL
;
610 *no_other_refs
= true;
613 /* Scan the loop body in order, so that the former references precede the
615 for (i
= 0; i
< loop
->num_nodes
; i
++)
618 if (bb
->loop_father
!= loop
)
621 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
623 stmt
= gsi_stmt (bsi
);
625 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
627 if (gimple_vuse (stmt
)
628 || (is_gimple_call (stmt
)
629 && !(gimple_call_flags (stmt
) & ECF_CONST
)))
630 *no_other_refs
= false;
634 if (! gimple_vuse (stmt
))
637 lhs
= gimple_assign_lhs (stmt
);
638 rhs
= gimple_assign_rhs1 (stmt
);
640 if (REFERENCE_CLASS_P (rhs
))
642 *no_other_refs
&= gather_memory_references_ref (loop
, &refs
,
646 if (REFERENCE_CLASS_P (lhs
))
648 *no_other_refs
&= gather_memory_references_ref (loop
, &refs
,
659 /* Prune the prefetch candidate REF using the self-reuse. */
662 prune_ref_by_self_reuse (struct mem_ref
*ref
)
667 /* If the step size is non constant, we cannot calculate prefetch_mod. */
668 if (!cst_and_fits_in_hwi (ref
->group
->step
))
671 step
= int_cst_value (ref
->group
->step
);
677 /* Prefetch references to invariant address just once. */
678 ref
->prefetch_before
= 1;
685 if (step
> PREFETCH_BLOCK
)
688 if ((backward
&& HAVE_BACKWARD_PREFETCH
)
689 || (!backward
&& HAVE_FORWARD_PREFETCH
))
691 ref
->prefetch_before
= 1;
695 ref
->prefetch_mod
= PREFETCH_BLOCK
/ step
;
698 /* Divides X by BY, rounding down. */
701 ddown (HOST_WIDE_INT x
, unsigned HOST_WIDE_INT by
)
708 return (x
+ by
- 1) / by
;
711 /* Given a CACHE_LINE_SIZE and two inductive memory references
712 with a common STEP greater than CACHE_LINE_SIZE and an address
713 difference DELTA, compute the probability that they will fall
714 in different cache lines. Return true if the computed miss rate
715 is not greater than the ACCEPTABLE_MISS_RATE. DISTINCT_ITERS is the
716 number of distinct iterations after which the pattern repeats itself.
717 ALIGN_UNIT is the unit of alignment in bytes. */
720 is_miss_rate_acceptable (unsigned HOST_WIDE_INT cache_line_size
,
721 HOST_WIDE_INT step
, HOST_WIDE_INT delta
,
722 unsigned HOST_WIDE_INT distinct_iters
,
725 unsigned align
, iter
;
726 int total_positions
, miss_positions
, max_allowed_miss_positions
;
727 int address1
, address2
, cache_line1
, cache_line2
;
729 /* It always misses if delta is greater than or equal to the cache
731 if (delta
>= (HOST_WIDE_INT
) cache_line_size
)
735 total_positions
= (cache_line_size
/ align_unit
) * distinct_iters
;
736 max_allowed_miss_positions
= (ACCEPTABLE_MISS_RATE
* total_positions
) / 1000;
738 /* Iterate through all possible alignments of the first
739 memory reference within its cache line. */
740 for (align
= 0; align
< cache_line_size
; align
+= align_unit
)
742 /* Iterate through all distinct iterations. */
743 for (iter
= 0; iter
< distinct_iters
; iter
++)
745 address1
= align
+ step
* iter
;
746 address2
= address1
+ delta
;
747 cache_line1
= address1
/ cache_line_size
;
748 cache_line2
= address2
/ cache_line_size
;
749 if (cache_line1
!= cache_line2
)
752 if (miss_positions
> max_allowed_miss_positions
)
759 /* Prune the prefetch candidate REF using the reuse with BY.
760 If BY_IS_BEFORE is true, BY is before REF in the loop. */
763 prune_ref_by_group_reuse (struct mem_ref
*ref
, struct mem_ref
*by
,
768 HOST_WIDE_INT delta_r
= ref
->delta
, delta_b
= by
->delta
;
769 HOST_WIDE_INT delta
= delta_b
- delta_r
;
770 HOST_WIDE_INT hit_from
;
771 unsigned HOST_WIDE_INT prefetch_before
, prefetch_block
;
772 HOST_WIDE_INT reduced_step
;
773 unsigned HOST_WIDE_INT reduced_prefetch_block
;
777 /* If the step is non constant we cannot calculate prefetch_before. */
778 if (!cst_and_fits_in_hwi (ref
->group
->step
)) {
782 step
= int_cst_value (ref
->group
->step
);
789 /* If the references has the same address, only prefetch the
792 ref
->prefetch_before
= 0;
799 /* If the reference addresses are invariant and fall into the
800 same cache line, prefetch just the first one. */
804 if (ddown (ref
->delta
, PREFETCH_BLOCK
)
805 != ddown (by
->delta
, PREFETCH_BLOCK
))
808 ref
->prefetch_before
= 0;
812 /* Only prune the reference that is behind in the array. */
818 /* Transform the data so that we may assume that the accesses
822 delta_r
= PREFETCH_BLOCK
- 1 - delta_r
;
823 delta_b
= PREFETCH_BLOCK
- 1 - delta_b
;
831 /* Check whether the two references are likely to hit the same cache
832 line, and how distant the iterations in that it occurs are from
835 if (step
<= PREFETCH_BLOCK
)
837 /* The accesses are sure to meet. Let us check when. */
838 hit_from
= ddown (delta_b
, PREFETCH_BLOCK
) * PREFETCH_BLOCK
;
839 prefetch_before
= (hit_from
- delta_r
+ step
- 1) / step
;
841 /* Do not reduce prefetch_before if we meet beyond cache size. */
842 if (prefetch_before
> absu_hwi (L2_CACHE_SIZE_BYTES
/ step
))
843 prefetch_before
= PREFETCH_ALL
;
844 if (prefetch_before
< ref
->prefetch_before
)
845 ref
->prefetch_before
= prefetch_before
;
850 /* A more complicated case with step > prefetch_block. First reduce
851 the ratio between the step and the cache line size to its simplest
852 terms. The resulting denominator will then represent the number of
853 distinct iterations after which each address will go back to its
854 initial location within the cache line. This computation assumes
855 that PREFETCH_BLOCK is a power of two. */
856 prefetch_block
= PREFETCH_BLOCK
;
857 reduced_prefetch_block
= prefetch_block
;
859 while ((reduced_step
& 1) == 0
860 && reduced_prefetch_block
> 1)
863 reduced_prefetch_block
>>= 1;
866 prefetch_before
= delta
/ step
;
868 ref_type
= TREE_TYPE (ref
->mem
);
869 align_unit
= TYPE_ALIGN (ref_type
) / 8;
870 if (is_miss_rate_acceptable (prefetch_block
, step
, delta
,
871 reduced_prefetch_block
, align_unit
))
873 /* Do not reduce prefetch_before if we meet beyond cache size. */
874 if (prefetch_before
> L2_CACHE_SIZE_BYTES
/ PREFETCH_BLOCK
)
875 prefetch_before
= PREFETCH_ALL
;
876 if (prefetch_before
< ref
->prefetch_before
)
877 ref
->prefetch_before
= prefetch_before
;
882 /* Try also the following iteration. */
884 delta
= step
- delta
;
885 if (is_miss_rate_acceptable (prefetch_block
, step
, delta
,
886 reduced_prefetch_block
, align_unit
))
888 if (prefetch_before
< ref
->prefetch_before
)
889 ref
->prefetch_before
= prefetch_before
;
894 /* The ref probably does not reuse by. */
898 /* Prune the prefetch candidate REF using the reuses with other references
902 prune_ref_by_reuse (struct mem_ref
*ref
, struct mem_ref
*refs
)
904 struct mem_ref
*prune_by
;
907 prune_ref_by_self_reuse (ref
);
909 for (prune_by
= refs
; prune_by
; prune_by
= prune_by
->next
)
917 if (!WRITE_CAN_USE_READ_PREFETCH
919 && !prune_by
->write_p
)
921 if (!READ_CAN_USE_WRITE_PREFETCH
923 && prune_by
->write_p
)
926 prune_ref_by_group_reuse (ref
, prune_by
, before
);
930 /* Prune the prefetch candidates in GROUP using the reuse analysis. */
933 prune_group_by_reuse (struct mem_ref_group
*group
)
935 struct mem_ref
*ref_pruned
;
937 for (ref_pruned
= group
->refs
; ref_pruned
; ref_pruned
= ref_pruned
->next
)
939 prune_ref_by_reuse (ref_pruned
, group
->refs
);
941 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
943 fprintf (dump_file
, "Reference %p:", (void *) ref_pruned
);
945 if (ref_pruned
->prefetch_before
== PREFETCH_ALL
946 && ref_pruned
->prefetch_mod
== 1)
947 fprintf (dump_file
, " no restrictions");
948 else if (ref_pruned
->prefetch_before
== 0)
949 fprintf (dump_file
, " do not prefetch");
950 else if (ref_pruned
->prefetch_before
<= ref_pruned
->prefetch_mod
)
951 fprintf (dump_file
, " prefetch once");
954 if (ref_pruned
->prefetch_before
!= PREFETCH_ALL
)
956 fprintf (dump_file
, " prefetch before ");
957 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
958 ref_pruned
->prefetch_before
);
960 if (ref_pruned
->prefetch_mod
!= 1)
962 fprintf (dump_file
, " prefetch mod ");
963 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
964 ref_pruned
->prefetch_mod
);
967 fprintf (dump_file
, "\n");
972 /* Prune the list of prefetch candidates GROUPS using the reuse analysis. */
975 prune_by_reuse (struct mem_ref_group
*groups
)
977 for (; groups
; groups
= groups
->next
)
978 prune_group_by_reuse (groups
);
981 /* Returns true if we should issue prefetch for REF. */
984 should_issue_prefetch_p (struct mem_ref
*ref
)
986 /* For now do not issue prefetches for only first few of the
988 if (ref
->prefetch_before
!= PREFETCH_ALL
)
990 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
991 fprintf (dump_file
, "Ignoring %p due to prefetch_before\n",
996 /* Do not prefetch nontemporal stores. */
999 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1000 fprintf (dump_file
, "Ignoring nontemporal store %p\n", (void *) ref
);
1007 /* Decide which of the prefetch candidates in GROUPS to prefetch.
1008 AHEAD is the number of iterations to prefetch ahead (which corresponds
1009 to the number of simultaneous instances of one prefetch running at a
1010 time). UNROLL_FACTOR is the factor by that the loop is going to be
1011 unrolled. Returns true if there is anything to prefetch. */
1014 schedule_prefetches (struct mem_ref_group
*groups
, unsigned unroll_factor
,
1017 unsigned remaining_prefetch_slots
, n_prefetches
, prefetch_slots
;
1018 unsigned slots_per_prefetch
;
1019 struct mem_ref
*ref
;
1022 /* At most SIMULTANEOUS_PREFETCHES should be running at the same time. */
1023 remaining_prefetch_slots
= SIMULTANEOUS_PREFETCHES
;
1025 /* The prefetch will run for AHEAD iterations of the original loop, i.e.,
1026 AHEAD / UNROLL_FACTOR iterations of the unrolled loop. In each iteration,
1027 it will need a prefetch slot. */
1028 slots_per_prefetch
= (ahead
+ unroll_factor
/ 2) / unroll_factor
;
1029 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1030 fprintf (dump_file
, "Each prefetch instruction takes %u prefetch slots.\n",
1031 slots_per_prefetch
);
1033 /* For now we just take memory references one by one and issue
1034 prefetches for as many as possible. The groups are sorted
1035 starting with the largest step, since the references with
1036 large step are more likely to cause many cache misses. */
1038 for (; groups
; groups
= groups
->next
)
1039 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1041 if (!should_issue_prefetch_p (ref
))
1044 /* The loop is far from being sufficiently unrolled for this
1045 prefetch. Do not generate prefetch to avoid many redudant
1047 if (ref
->prefetch_mod
/ unroll_factor
> PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
)
1050 /* If we need to prefetch the reference each PREFETCH_MOD iterations,
1051 and we unroll the loop UNROLL_FACTOR times, we need to insert
1052 ceil (UNROLL_FACTOR / PREFETCH_MOD) instructions in each
1054 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1055 / ref
->prefetch_mod
);
1056 prefetch_slots
= n_prefetches
* slots_per_prefetch
;
1058 /* If more than half of the prefetches would be lost anyway, do not
1059 issue the prefetch. */
1060 if (2 * remaining_prefetch_slots
< prefetch_slots
)
1063 ref
->issue_prefetch_p
= true;
1065 if (remaining_prefetch_slots
<= prefetch_slots
)
1067 remaining_prefetch_slots
-= prefetch_slots
;
1074 /* Return TRUE if no prefetch is going to be generated in the given
1078 nothing_to_prefetch_p (struct mem_ref_group
*groups
)
1080 struct mem_ref
*ref
;
1082 for (; groups
; groups
= groups
->next
)
1083 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1084 if (should_issue_prefetch_p (ref
))
1090 /* Estimate the number of prefetches in the given GROUPS.
1091 UNROLL_FACTOR is the factor by which LOOP was unrolled. */
1094 estimate_prefetch_count (struct mem_ref_group
*groups
, unsigned unroll_factor
)
1096 struct mem_ref
*ref
;
1097 unsigned n_prefetches
;
1098 int prefetch_count
= 0;
1100 for (; groups
; groups
= groups
->next
)
1101 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1102 if (should_issue_prefetch_p (ref
))
1104 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1105 / ref
->prefetch_mod
);
1106 prefetch_count
+= n_prefetches
;
1109 return prefetch_count
;
1112 /* Issue prefetches for the reference REF into loop as decided before.
1113 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR
1114 is the factor by which LOOP was unrolled. */
1117 issue_prefetch_ref (struct mem_ref
*ref
, unsigned unroll_factor
, unsigned ahead
)
1119 HOST_WIDE_INT delta
;
1120 tree addr
, addr_base
, write_p
, local
, forward
;
1122 gimple_stmt_iterator bsi
;
1123 unsigned n_prefetches
, ap
;
1124 bool nontemporal
= ref
->reuse_distance
>= L2_CACHE_SIZE_BYTES
;
1126 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1127 fprintf (dump_file
, "Issued%s prefetch for %p.\n",
1128 nontemporal
? " nontemporal" : "",
1131 bsi
= gsi_for_stmt (ref
->stmt
);
1133 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1134 / ref
->prefetch_mod
);
1135 addr_base
= build_fold_addr_expr_with_type (ref
->mem
, ptr_type_node
);
1136 addr_base
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr_base
),
1137 true, NULL
, true, GSI_SAME_STMT
);
1138 write_p
= ref
->write_p
? integer_one_node
: integer_zero_node
;
1139 local
= nontemporal
? integer_zero_node
: integer_three_node
;
1141 for (ap
= 0; ap
< n_prefetches
; ap
++)
1143 if (cst_and_fits_in_hwi (ref
->group
->step
))
1145 /* Determine the address to prefetch. */
1146 delta
= (ahead
+ ap
* ref
->prefetch_mod
) *
1147 int_cst_value (ref
->group
->step
);
1148 addr
= fold_build_pointer_plus_hwi (addr_base
, delta
);
1149 addr
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr
), true, NULL
,
1150 true, GSI_SAME_STMT
);
1154 /* The step size is non-constant but loop-invariant. We use the
1155 heuristic to simply prefetch ahead iterations ahead. */
1156 forward
= fold_build2 (MULT_EXPR
, sizetype
,
1157 fold_convert (sizetype
, ref
->group
->step
),
1158 fold_convert (sizetype
, size_int (ahead
)));
1159 addr
= fold_build_pointer_plus (addr_base
, forward
);
1160 addr
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr
), true,
1161 NULL
, true, GSI_SAME_STMT
);
1163 /* Create the prefetch instruction. */
1164 prefetch
= gimple_build_call (builtin_decl_explicit (BUILT_IN_PREFETCH
),
1165 3, addr
, write_p
, local
);
1166 gsi_insert_before (&bsi
, prefetch
, GSI_SAME_STMT
);
1170 /* Issue prefetches for the references in GROUPS into loop as decided before.
1171 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR is the
1172 factor by that LOOP was unrolled. */
1175 issue_prefetches (struct mem_ref_group
*groups
,
1176 unsigned unroll_factor
, unsigned ahead
)
1178 struct mem_ref
*ref
;
1180 for (; groups
; groups
= groups
->next
)
1181 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1182 if (ref
->issue_prefetch_p
)
1183 issue_prefetch_ref (ref
, unroll_factor
, ahead
);
1186 /* Returns true if REF is a memory write for that a nontemporal store insn
1190 nontemporal_store_p (struct mem_ref
*ref
)
1193 enum insn_code code
;
1195 /* REF must be a write that is not reused. We require it to be independent
1196 on all other memory references in the loop, as the nontemporal stores may
1197 be reordered with respect to other memory references. */
1199 || !ref
->independent_p
1200 || ref
->reuse_distance
< L2_CACHE_SIZE_BYTES
)
1203 /* Check that we have the storent instruction for the mode. */
1204 mode
= TYPE_MODE (TREE_TYPE (ref
->mem
));
1205 if (mode
== BLKmode
)
1208 code
= optab_handler (storent_optab
, mode
);
1209 return code
!= CODE_FOR_nothing
;
1212 /* If REF is a nontemporal store, we mark the corresponding modify statement
1213 and return true. Otherwise, we return false. */
1216 mark_nontemporal_store (struct mem_ref
*ref
)
1218 if (!nontemporal_store_p (ref
))
1221 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1222 fprintf (dump_file
, "Marked reference %p as a nontemporal store.\n",
1225 gimple_assign_set_nontemporal_move (ref
->stmt
, true);
1226 ref
->storent_p
= true;
1231 /* Issue a memory fence instruction after LOOP. */
1234 emit_mfence_after_loop (struct loop
*loop
)
1236 vec
<edge
> exits
= get_loop_exit_edges (loop
);
1239 gimple_stmt_iterator bsi
;
1242 FOR_EACH_VEC_ELT (exits
, i
, exit
)
1244 call
= gimple_build_call (FENCE_FOLLOWING_MOVNT
, 0);
1246 if (!single_pred_p (exit
->dest
)
1247 /* If possible, we prefer not to insert the fence on other paths
1249 && !(exit
->flags
& EDGE_ABNORMAL
))
1250 split_loop_exit_edge (exit
);
1251 bsi
= gsi_after_labels (exit
->dest
);
1253 gsi_insert_before (&bsi
, call
, GSI_NEW_STMT
);
1257 update_ssa (TODO_update_ssa_only_virtuals
);
1260 /* Returns true if we can use storent in loop, false otherwise. */
1263 may_use_storent_in_loop_p (struct loop
*loop
)
1267 if (loop
->inner
!= NULL
)
1270 /* If we must issue a mfence insn after using storent, check that there
1271 is a suitable place for it at each of the loop exits. */
1272 if (FENCE_FOLLOWING_MOVNT
!= NULL_TREE
)
1274 vec
<edge
> exits
= get_loop_exit_edges (loop
);
1278 FOR_EACH_VEC_ELT (exits
, i
, exit
)
1279 if ((exit
->flags
& EDGE_ABNORMAL
)
1280 && exit
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1289 /* Marks nontemporal stores in LOOP. GROUPS contains the description of memory
1290 references in the loop. */
1293 mark_nontemporal_stores (struct loop
*loop
, struct mem_ref_group
*groups
)
1295 struct mem_ref
*ref
;
1298 if (!may_use_storent_in_loop_p (loop
))
1301 for (; groups
; groups
= groups
->next
)
1302 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1303 any
|= mark_nontemporal_store (ref
);
1305 if (any
&& FENCE_FOLLOWING_MOVNT
!= NULL_TREE
)
1306 emit_mfence_after_loop (loop
);
1309 /* Determines whether we can profitably unroll LOOP FACTOR times, and if
1310 this is the case, fill in DESC by the description of number of
1314 should_unroll_loop_p (struct loop
*loop
, struct tree_niter_desc
*desc
,
1317 if (!can_unroll_loop_p (loop
, factor
, desc
))
1320 /* We only consider loops without control flow for unrolling. This is not
1321 a hard restriction -- tree_unroll_loop works with arbitrary loops
1322 as well; but the unrolling/prefetching is usually more profitable for
1323 loops consisting of a single basic block, and we want to limit the
1325 if (loop
->num_nodes
> 2)
1331 /* Determine the coefficient by that unroll LOOP, from the information
1332 contained in the list of memory references REFS. Description of
1333 umber of iterations of LOOP is stored to DESC. NINSNS is the number of
1334 insns of the LOOP. EST_NITER is the estimated number of iterations of
1335 the loop, or -1 if no estimate is available. */
1338 determine_unroll_factor (struct loop
*loop
, struct mem_ref_group
*refs
,
1339 unsigned ninsns
, struct tree_niter_desc
*desc
,
1340 HOST_WIDE_INT est_niter
)
1342 unsigned upper_bound
;
1343 unsigned nfactor
, factor
, mod_constraint
;
1344 struct mem_ref_group
*agp
;
1345 struct mem_ref
*ref
;
1347 /* First check whether the loop is not too large to unroll. We ignore
1348 PARAM_MAX_UNROLL_TIMES, because for small loops, it prevented us
1349 from unrolling them enough to make exactly one cache line covered by each
1350 iteration. Also, the goal of PARAM_MAX_UNROLL_TIMES is to prevent
1351 us from unrolling the loops too many times in cases where we only expect
1352 gains from better scheduling and decreasing loop overhead, which is not
1354 upper_bound
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / ninsns
;
1356 /* If we unrolled the loop more times than it iterates, the unrolled version
1357 of the loop would be never entered. */
1358 if (est_niter
>= 0 && est_niter
< (HOST_WIDE_INT
) upper_bound
)
1359 upper_bound
= est_niter
;
1361 if (upper_bound
<= 1)
1364 /* Choose the factor so that we may prefetch each cache just once,
1365 but bound the unrolling by UPPER_BOUND. */
1367 for (agp
= refs
; agp
; agp
= agp
->next
)
1368 for (ref
= agp
->refs
; ref
; ref
= ref
->next
)
1369 if (should_issue_prefetch_p (ref
))
1371 mod_constraint
= ref
->prefetch_mod
;
1372 nfactor
= least_common_multiple (mod_constraint
, factor
);
1373 if (nfactor
<= upper_bound
)
1377 if (!should_unroll_loop_p (loop
, desc
, factor
))
1383 /* Returns the total volume of the memory references REFS, taking into account
1384 reuses in the innermost loop and cache line size. TODO -- we should also
1385 take into account reuses across the iterations of the loops in the loop
1389 volume_of_references (struct mem_ref_group
*refs
)
1391 unsigned volume
= 0;
1392 struct mem_ref_group
*gr
;
1393 struct mem_ref
*ref
;
1395 for (gr
= refs
; gr
; gr
= gr
->next
)
1396 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1398 /* Almost always reuses another value? */
1399 if (ref
->prefetch_before
!= PREFETCH_ALL
)
1402 /* If several iterations access the same cache line, use the size of
1403 the line divided by this number. Otherwise, a cache line is
1404 accessed in each iteration. TODO -- in the latter case, we should
1405 take the size of the reference into account, rounding it up on cache
1406 line size multiple. */
1407 volume
+= L1_CACHE_LINE_SIZE
/ ref
->prefetch_mod
;
1412 /* Returns the volume of memory references accessed across VEC iterations of
1413 loops, whose sizes are described in the LOOP_SIZES array. N is the number
1414 of the loops in the nest (length of VEC and LOOP_SIZES vectors). */
1417 volume_of_dist_vector (lambda_vector vec
, unsigned *loop_sizes
, unsigned n
)
1421 for (i
= 0; i
< n
; i
++)
1428 gcc_assert (vec
[i
] > 0);
1430 /* We ignore the parts of the distance vector in subloops, since usually
1431 the numbers of iterations are much smaller. */
1432 return loop_sizes
[i
] * vec
[i
];
1435 /* Add the steps of ACCESS_FN multiplied by STRIDE to the array STRIDE
1436 at the position corresponding to the loop of the step. N is the depth
1437 of the considered loop nest, and, LOOP is its innermost loop. */
1440 add_subscript_strides (tree access_fn
, unsigned stride
,
1441 HOST_WIDE_INT
*strides
, unsigned n
, struct loop
*loop
)
1445 HOST_WIDE_INT astep
;
1446 unsigned min_depth
= loop_depth (loop
) - n
;
1448 while (TREE_CODE (access_fn
) == POLYNOMIAL_CHREC
)
1450 aloop
= get_chrec_loop (access_fn
);
1451 step
= CHREC_RIGHT (access_fn
);
1452 access_fn
= CHREC_LEFT (access_fn
);
1454 if ((unsigned) loop_depth (aloop
) <= min_depth
)
1457 if (tree_fits_shwi_p (step
))
1458 astep
= tree_to_shwi (step
);
1460 astep
= L1_CACHE_LINE_SIZE
;
1462 strides
[n
- 1 - loop_depth (loop
) + loop_depth (aloop
)] += astep
* stride
;
1467 /* Returns the volume of memory references accessed between two consecutive
1468 self-reuses of the reference DR. We consider the subscripts of DR in N
1469 loops, and LOOP_SIZES contains the volumes of accesses in each of the
1470 loops. LOOP is the innermost loop of the current loop nest. */
1473 self_reuse_distance (data_reference_p dr
, unsigned *loop_sizes
, unsigned n
,
1476 tree stride
, access_fn
;
1477 HOST_WIDE_INT
*strides
, astride
;
1478 vec
<tree
> access_fns
;
1479 tree ref
= DR_REF (dr
);
1480 unsigned i
, ret
= ~0u;
1482 /* In the following example:
1484 for (i = 0; i < N; i++)
1485 for (j = 0; j < N; j++)
1487 the same cache line is accessed each N steps (except if the change from
1488 i to i + 1 crosses the boundary of the cache line). Thus, for self-reuse,
1489 we cannot rely purely on the results of the data dependence analysis.
1491 Instead, we compute the stride of the reference in each loop, and consider
1492 the innermost loop in that the stride is less than cache size. */
1494 strides
= XCNEWVEC (HOST_WIDE_INT
, n
);
1495 access_fns
= DR_ACCESS_FNS (dr
);
1497 FOR_EACH_VEC_ELT (access_fns
, i
, access_fn
)
1499 /* Keep track of the reference corresponding to the subscript, so that we
1501 while (handled_component_p (ref
) && TREE_CODE (ref
) != ARRAY_REF
)
1502 ref
= TREE_OPERAND (ref
, 0);
1504 if (TREE_CODE (ref
) == ARRAY_REF
)
1506 stride
= TYPE_SIZE_UNIT (TREE_TYPE (ref
));
1507 if (tree_fits_uhwi_p (stride
))
1508 astride
= tree_to_uhwi (stride
);
1510 astride
= L1_CACHE_LINE_SIZE
;
1512 ref
= TREE_OPERAND (ref
, 0);
1517 add_subscript_strides (access_fn
, astride
, strides
, n
, loop
);
1520 for (i
= n
; i
-- > 0; )
1522 unsigned HOST_WIDE_INT s
;
1524 s
= strides
[i
] < 0 ? -strides
[i
] : strides
[i
];
1526 if (s
< (unsigned) L1_CACHE_LINE_SIZE
1528 > (unsigned) (L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)))
1530 ret
= loop_sizes
[i
];
1539 /* Determines the distance till the first reuse of each reference in REFS
1540 in the loop nest of LOOP. NO_OTHER_REFS is true if there are no other
1541 memory references in the loop. Return false if the analysis fails. */
1544 determine_loop_nest_reuse (struct loop
*loop
, struct mem_ref_group
*refs
,
1547 struct loop
*nest
, *aloop
;
1548 vec
<data_reference_p
> datarefs
= vNULL
;
1549 vec
<ddr_p
> dependences
= vNULL
;
1550 struct mem_ref_group
*gr
;
1551 struct mem_ref
*ref
, *refb
;
1552 auto_vec
<loop_p
> vloops
;
1553 unsigned *loop_data_size
;
1555 unsigned volume
, dist
, adist
;
1557 data_reference_p dr
;
1563 /* Find the outermost loop of the loop nest of loop (we require that
1564 there are no sibling loops inside the nest). */
1568 aloop
= loop_outer (nest
);
1570 if (aloop
== current_loops
->tree_root
1571 || aloop
->inner
->next
)
1577 /* For each loop, determine the amount of data accessed in each iteration.
1578 We use this to estimate whether the reference is evicted from the
1579 cache before its reuse. */
1580 find_loop_nest (nest
, &vloops
);
1581 n
= vloops
.length ();
1582 loop_data_size
= XNEWVEC (unsigned, n
);
1583 volume
= volume_of_references (refs
);
1587 loop_data_size
[i
] = volume
;
1588 /* Bound the volume by the L2 cache size, since above this bound,
1589 all dependence distances are equivalent. */
1590 if (volume
> L2_CACHE_SIZE_BYTES
)
1594 vol
= estimated_stmt_executions_int (aloop
);
1596 vol
= expected_loop_iterations (aloop
);
1600 /* Prepare the references in the form suitable for data dependence
1601 analysis. We ignore unanalyzable data references (the results
1602 are used just as a heuristics to estimate temporality of the
1603 references, hence we do not need to worry about correctness). */
1604 for (gr
= refs
; gr
; gr
= gr
->next
)
1605 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1607 dr
= create_data_ref (nest
, loop_containing_stmt (ref
->stmt
),
1608 ref
->mem
, ref
->stmt
, !ref
->write_p
);
1612 ref
->reuse_distance
= volume
;
1614 datarefs
.safe_push (dr
);
1617 no_other_refs
= false;
1620 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
1622 dist
= self_reuse_distance (dr
, loop_data_size
, n
, loop
);
1623 ref
= (struct mem_ref
*) dr
->aux
;
1624 if (ref
->reuse_distance
> dist
)
1625 ref
->reuse_distance
= dist
;
1628 ref
->independent_p
= true;
1631 if (!compute_all_dependences (datarefs
, &dependences
, vloops
, true))
1634 FOR_EACH_VEC_ELT (dependences
, i
, dep
)
1636 if (DDR_ARE_DEPENDENT (dep
) == chrec_known
)
1639 ref
= (struct mem_ref
*) DDR_A (dep
)->aux
;
1640 refb
= (struct mem_ref
*) DDR_B (dep
)->aux
;
1642 if (DDR_ARE_DEPENDENT (dep
) == chrec_dont_know
1643 || DDR_NUM_DIST_VECTS (dep
) == 0)
1645 /* If the dependence cannot be analyzed, assume that there might be
1649 ref
->independent_p
= false;
1650 refb
->independent_p
= false;
1654 /* The distance vectors are normalized to be always lexicographically
1655 positive, hence we cannot tell just from them whether DDR_A comes
1656 before DDR_B or vice versa. However, it is not important,
1657 anyway -- if DDR_A is close to DDR_B, then it is either reused in
1658 DDR_B (and it is not nontemporal), or it reuses the value of DDR_B
1659 in cache (and marking it as nontemporal would not affect
1663 for (j
= 0; j
< DDR_NUM_DIST_VECTS (dep
); j
++)
1665 adist
= volume_of_dist_vector (DDR_DIST_VECT (dep
, j
),
1668 /* If this is a dependence in the innermost loop (i.e., the
1669 distances in all superloops are zero) and it is not
1670 the trivial self-dependence with distance zero, record that
1671 the references are not completely independent. */
1672 if (lambda_vector_zerop (DDR_DIST_VECT (dep
, j
), n
- 1)
1674 || DDR_DIST_VECT (dep
, j
)[n
-1] != 0))
1676 ref
->independent_p
= false;
1677 refb
->independent_p
= false;
1680 /* Ignore accesses closer than
1681 L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
1682 so that we use nontemporal prefetches e.g. if single memory
1683 location is accessed several times in a single iteration of
1685 if (adist
< L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)
1693 if (ref
->reuse_distance
> dist
)
1694 ref
->reuse_distance
= dist
;
1695 if (refb
->reuse_distance
> dist
)
1696 refb
->reuse_distance
= dist
;
1699 free_dependence_relations (dependences
);
1700 free_data_refs (datarefs
);
1701 free (loop_data_size
);
1703 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1705 fprintf (dump_file
, "Reuse distances:\n");
1706 for (gr
= refs
; gr
; gr
= gr
->next
)
1707 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1708 fprintf (dump_file
, " ref %p distance %u\n",
1709 (void *) ref
, ref
->reuse_distance
);
1715 /* Determine whether or not the trip count to ahead ratio is too small based
1716 on prefitablility consideration.
1717 AHEAD: the iteration ahead distance,
1718 EST_NITER: the estimated trip count. */
1721 trip_count_to_ahead_ratio_too_small_p (unsigned ahead
, HOST_WIDE_INT est_niter
)
1723 /* Assume trip count to ahead ratio is big enough if the trip count could not
1724 be estimated at compile time. */
1728 if (est_niter
< (HOST_WIDE_INT
) (TRIP_COUNT_TO_AHEAD_RATIO
* ahead
))
1730 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1732 "Not prefetching -- loop estimated to roll only %d times\n",
1740 /* Determine whether or not the number of memory references in the loop is
1741 reasonable based on the profitablity and compilation time considerations.
1742 NINSNS: estimated number of instructions in the loop,
1743 MEM_REF_COUNT: total number of memory references in the loop. */
1746 mem_ref_count_reasonable_p (unsigned ninsns
, unsigned mem_ref_count
)
1748 int insn_to_mem_ratio
;
1750 if (mem_ref_count
== 0)
1753 /* Miss rate computation (is_miss_rate_acceptable) and dependence analysis
1754 (compute_all_dependences) have high costs based on quadratic complexity.
1755 To avoid huge compilation time, we give up prefetching if mem_ref_count
1757 if (mem_ref_count
> PREFETCH_MAX_MEM_REFS_PER_LOOP
)
1760 /* Prefetching improves performance by overlapping cache missing
1761 memory accesses with CPU operations. If the loop does not have
1762 enough CPU operations to overlap with memory operations, prefetching
1763 won't give a significant benefit. One approximate way of checking
1764 this is to require the ratio of instructions to memory references to
1765 be above a certain limit. This approximation works well in practice.
1766 TODO: Implement a more precise computation by estimating the time
1767 for each CPU or memory op in the loop. Time estimates for memory ops
1768 should account for cache misses. */
1769 insn_to_mem_ratio
= ninsns
/ mem_ref_count
;
1771 if (insn_to_mem_ratio
< PREFETCH_MIN_INSN_TO_MEM_RATIO
)
1773 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1775 "Not prefetching -- instruction to memory reference ratio (%d) too small\n",
1783 /* Determine whether or not the instruction to prefetch ratio in the loop is
1784 too small based on the profitablity consideration.
1785 NINSNS: estimated number of instructions in the loop,
1786 PREFETCH_COUNT: an estimate of the number of prefetches,
1787 UNROLL_FACTOR: the factor to unroll the loop if prefetching. */
1790 insn_to_prefetch_ratio_too_small_p (unsigned ninsns
, unsigned prefetch_count
,
1791 unsigned unroll_factor
)
1793 int insn_to_prefetch_ratio
;
1795 /* Prefetching most likely causes performance degradation when the instruction
1796 to prefetch ratio is too small. Too many prefetch instructions in a loop
1797 may reduce the I-cache performance.
1798 (unroll_factor * ninsns) is used to estimate the number of instructions in
1799 the unrolled loop. This implementation is a bit simplistic -- the number
1800 of issued prefetch instructions is also affected by unrolling. So,
1801 prefetch_mod and the unroll factor should be taken into account when
1802 determining prefetch_count. Also, the number of insns of the unrolled
1803 loop will usually be significantly smaller than the number of insns of the
1804 original loop * unroll_factor (at least the induction variable increases
1805 and the exit branches will get eliminated), so it might be better to use
1806 tree_estimate_loop_size + estimated_unrolled_size. */
1807 insn_to_prefetch_ratio
= (unroll_factor
* ninsns
) / prefetch_count
;
1808 if (insn_to_prefetch_ratio
< MIN_INSN_TO_PREFETCH_RATIO
)
1810 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1812 "Not prefetching -- instruction to prefetch ratio (%d) too small\n",
1813 insn_to_prefetch_ratio
);
1821 /* Issue prefetch instructions for array references in LOOP. Returns
1822 true if the LOOP was unrolled. */
1825 loop_prefetch_arrays (struct loop
*loop
)
1827 struct mem_ref_group
*refs
;
1828 unsigned ahead
, ninsns
, time
, unroll_factor
;
1829 HOST_WIDE_INT est_niter
;
1830 struct tree_niter_desc desc
;
1831 bool unrolled
= false, no_other_refs
;
1832 unsigned prefetch_count
;
1833 unsigned mem_ref_count
;
1835 if (optimize_loop_nest_for_size_p (loop
))
1837 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1838 fprintf (dump_file
, " ignored (cold area)\n");
1842 /* FIXME: the time should be weighted by the probabilities of the blocks in
1844 time
= tree_num_loop_insns (loop
, &eni_time_weights
);
1848 ahead
= (PREFETCH_LATENCY
+ time
- 1) / time
;
1849 est_niter
= estimated_stmt_executions_int (loop
);
1850 if (est_niter
== -1)
1851 est_niter
= max_stmt_executions_int (loop
);
1853 /* Prefetching is not likely to be profitable if the trip count to ahead
1854 ratio is too small. */
1855 if (trip_count_to_ahead_ratio_too_small_p (ahead
, est_niter
))
1858 ninsns
= tree_num_loop_insns (loop
, &eni_size_weights
);
1860 /* Step 1: gather the memory references. */
1861 refs
= gather_memory_references (loop
, &no_other_refs
, &mem_ref_count
);
1863 /* Give up prefetching if the number of memory references in the
1864 loop is not reasonable based on profitablity and compilation time
1866 if (!mem_ref_count_reasonable_p (ninsns
, mem_ref_count
))
1869 /* Step 2: estimate the reuse effects. */
1870 prune_by_reuse (refs
);
1872 if (nothing_to_prefetch_p (refs
))
1875 if (!determine_loop_nest_reuse (loop
, refs
, no_other_refs
))
1878 /* Step 3: determine unroll factor. */
1879 unroll_factor
= determine_unroll_factor (loop
, refs
, ninsns
, &desc
,
1882 /* Estimate prefetch count for the unrolled loop. */
1883 prefetch_count
= estimate_prefetch_count (refs
, unroll_factor
);
1884 if (prefetch_count
== 0)
1887 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1888 fprintf (dump_file
, "Ahead %d, unroll factor %d, trip count "
1889 HOST_WIDE_INT_PRINT_DEC
"\n"
1890 "insn count %d, mem ref count %d, prefetch count %d\n",
1891 ahead
, unroll_factor
, est_niter
,
1892 ninsns
, mem_ref_count
, prefetch_count
);
1894 /* Prefetching is not likely to be profitable if the instruction to prefetch
1895 ratio is too small. */
1896 if (insn_to_prefetch_ratio_too_small_p (ninsns
, prefetch_count
,
1900 mark_nontemporal_stores (loop
, refs
);
1902 /* Step 4: what to prefetch? */
1903 if (!schedule_prefetches (refs
, unroll_factor
, ahead
))
1906 /* Step 5: unroll the loop. TODO -- peeling of first and last few
1907 iterations so that we do not issue superfluous prefetches. */
1908 if (unroll_factor
!= 1)
1910 tree_unroll_loop (loop
, unroll_factor
,
1911 single_dom_exit (loop
), &desc
);
1915 /* Step 6: issue the prefetches. */
1916 issue_prefetches (refs
, unroll_factor
, ahead
);
1919 release_mem_refs (refs
);
1923 /* Issue prefetch instructions for array references in loops. */
1926 tree_ssa_prefetch_arrays (void)
1929 bool unrolled
= false;
1932 if (!targetm
.have_prefetch ()
1933 /* It is possible to ask compiler for say -mtune=i486 -march=pentium4.
1934 -mtune=i486 causes us having PREFETCH_BLOCK 0, since this is part
1935 of processor costs and i486 does not have prefetch, but
1936 -march=pentium4 causes targetm.have_prefetch to be true. Ugh. */
1937 || PREFETCH_BLOCK
== 0)
1940 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1942 fprintf (dump_file
, "Prefetching parameters:\n");
1943 fprintf (dump_file
, " simultaneous prefetches: %d\n",
1944 SIMULTANEOUS_PREFETCHES
);
1945 fprintf (dump_file
, " prefetch latency: %d\n", PREFETCH_LATENCY
);
1946 fprintf (dump_file
, " prefetch block size: %d\n", PREFETCH_BLOCK
);
1947 fprintf (dump_file
, " L1 cache size: %d lines, %d kB\n",
1948 L1_CACHE_SIZE_BYTES
/ L1_CACHE_LINE_SIZE
, L1_CACHE_SIZE
);
1949 fprintf (dump_file
, " L1 cache line size: %d\n", L1_CACHE_LINE_SIZE
);
1950 fprintf (dump_file
, " L2 cache size: %d kB\n", L2_CACHE_SIZE
);
1951 fprintf (dump_file
, " min insn-to-prefetch ratio: %d \n",
1952 MIN_INSN_TO_PREFETCH_RATIO
);
1953 fprintf (dump_file
, " min insn-to-mem ratio: %d \n",
1954 PREFETCH_MIN_INSN_TO_MEM_RATIO
);
1955 fprintf (dump_file
, "\n");
1958 initialize_original_copy_tables ();
1960 if (!builtin_decl_explicit_p (BUILT_IN_PREFETCH
))
1962 tree type
= build_function_type_list (void_type_node
,
1963 const_ptr_type_node
, NULL_TREE
);
1964 tree decl
= add_builtin_function ("__builtin_prefetch", type
,
1965 BUILT_IN_PREFETCH
, BUILT_IN_NORMAL
,
1967 DECL_IS_NOVOPS (decl
) = true;
1968 set_builtin_decl (BUILT_IN_PREFETCH
, decl
, false);
1971 /* We assume that size of cache line is a power of two, so verify this
1973 gcc_assert ((PREFETCH_BLOCK
& (PREFETCH_BLOCK
- 1)) == 0);
1975 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1977 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1978 fprintf (dump_file
, "Processing loop %d:\n", loop
->num
);
1980 unrolled
|= loop_prefetch_arrays (loop
);
1982 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1983 fprintf (dump_file
, "\n\n");
1989 todo_flags
|= TODO_cleanup_cfg
;
1992 free_original_copy_tables ();
2000 const pass_data pass_data_loop_prefetch
=
2002 GIMPLE_PASS
, /* type */
2003 "aprefetch", /* name */
2004 OPTGROUP_LOOP
, /* optinfo_flags */
2005 TV_TREE_PREFETCH
, /* tv_id */
2006 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2007 0, /* properties_provided */
2008 0, /* properties_destroyed */
2009 0, /* todo_flags_start */
2010 0, /* todo_flags_finish */
2013 class pass_loop_prefetch
: public gimple_opt_pass
2016 pass_loop_prefetch (gcc::context
*ctxt
)
2017 : gimple_opt_pass (pass_data_loop_prefetch
, ctxt
)
2020 /* opt_pass methods: */
2021 virtual bool gate (function
*) { return flag_prefetch_loop_arrays
> 0; }
2022 virtual unsigned int execute (function
*);
2024 }; // class pass_loop_prefetch
2027 pass_loop_prefetch::execute (function
*fun
)
2029 if (number_of_loops (fun
) <= 1)
2032 return tree_ssa_prefetch_arrays ();
2038 make_pass_loop_prefetch (gcc::context
*ctxt
)
2040 return new pass_loop_prefetch (ctxt
);