2 Copyright (C) 2005-2014 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"
25 #include "stor-layout.h"
32 #include "hard-reg-set.h"
35 #include "dominance.h"
37 #include "basic-block.h"
38 #include "tree-pretty-print.h"
39 #include "tree-ssa-alias.h"
40 #include "internal-fn.h"
41 #include "gimple-expr.h"
45 #include "gimple-iterator.h"
46 #include "gimplify-me.h"
47 #include "gimple-ssa.h"
48 #include "tree-ssa-loop-ivopts.h"
49 #include "tree-ssa-loop-manip.h"
50 #include "tree-ssa-loop-niter.h"
51 #include "tree-ssa-loop.h"
52 #include "tree-into-ssa.h"
54 #include "tree-pass.h"
55 #include "insn-config.h"
56 #include "tree-chrec.h"
57 #include "tree-scalar-evolution.h"
58 #include "diagnostic-core.h"
60 #include "langhooks.h"
61 #include "tree-inline.h"
62 #include "tree-data-ref.h"
65 /* FIXME: Needed for optabs, but this should all be moved to a TBD interface
66 between the GIMPLE and RTL worlds. */
71 /* This pass inserts prefetch instructions to optimize cache usage during
72 accesses to arrays in loops. It processes loops sequentially and:
74 1) Gathers all memory references in the single loop.
75 2) For each of the references it decides when it is profitable to prefetch
76 it. To do it, we evaluate the reuse among the accesses, and determines
77 two values: PREFETCH_BEFORE (meaning that it only makes sense to do
78 prefetching in the first PREFETCH_BEFORE iterations of the loop) and
79 PREFETCH_MOD (meaning that it only makes sense to prefetch in the
80 iterations of the loop that are zero modulo PREFETCH_MOD). For example
81 (assuming cache line size is 64 bytes, char has size 1 byte and there
82 is no hardware sequential prefetch):
85 for (i = 0; i < max; i++)
92 a[187*i + 50] = ...; (5)
95 (0) obviously has PREFETCH_BEFORE 1
96 (1) has PREFETCH_BEFORE 64, since (2) accesses the same memory
97 location 64 iterations before it, and PREFETCH_MOD 64 (since
98 it hits the same cache line otherwise).
99 (2) has PREFETCH_MOD 64
100 (3) has PREFETCH_MOD 4
101 (4) has PREFETCH_MOD 1. We do not set PREFETCH_BEFORE here, since
102 the cache line accessed by (5) is the same with probability only
104 (5) has PREFETCH_MOD 1 as well.
106 Additionally, we use data dependence analysis to determine for each
107 reference the distance till the first reuse; this information is used
108 to determine the temporality of the issued prefetch instruction.
110 3) We determine how much ahead we need to prefetch. The number of
111 iterations needed is time to fetch / time spent in one iteration of
112 the loop. The problem is that we do not know either of these values,
113 so we just make a heuristic guess based on a magic (possibly)
114 target-specific constant and size of the loop.
116 4) Determine which of the references we prefetch. We take into account
117 that there is a maximum number of simultaneous prefetches (provided
118 by machine description). We prefetch as many prefetches as possible
119 while still within this bound (starting with those with lowest
120 prefetch_mod, since they are responsible for most of the cache
123 5) We unroll and peel loops so that we are able to satisfy PREFETCH_MOD
124 and PREFETCH_BEFORE requirements (within some bounds), and to avoid
125 prefetching nonaccessed memory.
126 TODO -- actually implement peeling.
128 6) We actually emit the prefetch instructions. ??? Perhaps emit the
129 prefetch instructions with guards in cases where 5) was not sufficient
130 to satisfy the constraints?
132 A cost model is implemented to determine whether or not prefetching is
133 profitable for a given loop. The cost model has three heuristics:
135 1. Function trip_count_to_ahead_ratio_too_small_p implements a
136 heuristic that determines whether or not the loop has too few
137 iterations (compared to ahead). Prefetching is not likely to be
138 beneficial if the trip count to ahead ratio is below a certain
141 2. Function mem_ref_count_reasonable_p implements a heuristic that
142 determines whether the given loop has enough CPU ops that can be
143 overlapped with cache missing memory ops. If not, the loop
144 won't benefit from prefetching. In the implementation,
145 prefetching is not considered beneficial if the ratio between
146 the instruction count and the mem ref count is below a certain
149 3. Function insn_to_prefetch_ratio_too_small_p implements a
150 heuristic that disables prefetching in a loop if the prefetching
151 cost is above a certain limit. The relative prefetching cost is
152 estimated by taking the ratio between the prefetch count and the
153 total intruction count (this models the I-cache cost).
155 The limits used in these heuristics are defined as parameters with
156 reasonable default values. Machine-specific default values will be
160 -- write and use more general reuse analysis (that could be also used
161 in other cache aimed loop optimizations)
162 -- make it behave sanely together with the prefetches given by user
163 (now we just ignore them; at the very least we should avoid
164 optimizing loops in that user put his own prefetches)
165 -- we assume cache line size alignment of arrays; this could be
168 /* Magic constants follow. These should be replaced by machine specific
171 /* True if write can be prefetched by a read prefetch. */
173 #ifndef WRITE_CAN_USE_READ_PREFETCH
174 #define WRITE_CAN_USE_READ_PREFETCH 1
177 /* True if read can be prefetched by a write prefetch. */
179 #ifndef READ_CAN_USE_WRITE_PREFETCH
180 #define READ_CAN_USE_WRITE_PREFETCH 0
183 /* The size of the block loaded by a single prefetch. Usually, this is
184 the same as cache line size (at the moment, we only consider one level
185 of cache hierarchy). */
187 #ifndef PREFETCH_BLOCK
188 #define PREFETCH_BLOCK L1_CACHE_LINE_SIZE
191 /* Do we have a forward hardware sequential prefetching? */
193 #ifndef HAVE_FORWARD_PREFETCH
194 #define HAVE_FORWARD_PREFETCH 0
197 /* Do we have a backward hardware sequential prefetching? */
199 #ifndef HAVE_BACKWARD_PREFETCH
200 #define HAVE_BACKWARD_PREFETCH 0
203 /* In some cases we are only able to determine that there is a certain
204 probability that the two accesses hit the same cache line. In this
205 case, we issue the prefetches for both of them if this probability
206 is less then (1000 - ACCEPTABLE_MISS_RATE) per thousand. */
208 #ifndef ACCEPTABLE_MISS_RATE
209 #define ACCEPTABLE_MISS_RATE 50
212 #ifndef HAVE_prefetch
213 #define HAVE_prefetch 0
216 #define L1_CACHE_SIZE_BYTES ((unsigned) (L1_CACHE_SIZE * 1024))
217 #define L2_CACHE_SIZE_BYTES ((unsigned) (L2_CACHE_SIZE * 1024))
219 /* We consider a memory access nontemporal if it is not reused sooner than
220 after L2_CACHE_SIZE_BYTES of memory are accessed. However, we ignore
221 accesses closer than L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
222 so that we use nontemporal prefetches e.g. if single memory location
223 is accessed several times in a single iteration of the loop. */
224 #define NONTEMPORAL_FRACTION 16
226 /* In case we have to emit a memory fence instruction after the loop that
227 uses nontemporal stores, this defines the builtin to use. */
229 #ifndef FENCE_FOLLOWING_MOVNT
230 #define FENCE_FOLLOWING_MOVNT NULL_TREE
233 /* It is not profitable to prefetch when the trip count is not at
234 least TRIP_COUNT_TO_AHEAD_RATIO times the prefetch ahead distance.
235 For example, in a loop with a prefetch ahead distance of 10,
236 supposing that TRIP_COUNT_TO_AHEAD_RATIO is equal to 4, it is
237 profitable to prefetch when the trip count is greater or equal to
238 40. In that case, 30 out of the 40 iterations will benefit from
241 #ifndef TRIP_COUNT_TO_AHEAD_RATIO
242 #define TRIP_COUNT_TO_AHEAD_RATIO 4
245 /* The group of references between that reuse may occur. */
249 tree base
; /* Base of the reference. */
250 tree step
; /* Step of the reference. */
251 struct mem_ref
*refs
; /* References in the group. */
252 struct mem_ref_group
*next
; /* Next group of references. */
255 /* Assigned to PREFETCH_BEFORE when all iterations are to be prefetched. */
257 #define PREFETCH_ALL (~(unsigned HOST_WIDE_INT) 0)
259 /* Do not generate a prefetch if the unroll factor is significantly less
260 than what is required by the prefetch. This is to avoid redundant
261 prefetches. For example, when prefetch_mod is 16 and unroll_factor is
262 2, prefetching requires unrolling the loop 16 times, but
263 the loop is actually unrolled twice. In this case (ratio = 8),
264 prefetching is not likely to be beneficial. */
266 #ifndef PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
267 #define PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO 4
270 /* Some of the prefetch computations have quadratic complexity. We want to
271 avoid huge compile times and, therefore, want to limit the amount of
272 memory references per loop where we consider prefetching. */
274 #ifndef PREFETCH_MAX_MEM_REFS_PER_LOOP
275 #define PREFETCH_MAX_MEM_REFS_PER_LOOP 200
278 /* The memory reference. */
282 gimple stmt
; /* Statement in that the reference appears. */
283 tree mem
; /* The reference. */
284 HOST_WIDE_INT delta
; /* Constant offset of the reference. */
285 struct mem_ref_group
*group
; /* The group of references it belongs to. */
286 unsigned HOST_WIDE_INT prefetch_mod
;
287 /* Prefetch only each PREFETCH_MOD-th
289 unsigned HOST_WIDE_INT prefetch_before
;
290 /* Prefetch only first PREFETCH_BEFORE
292 unsigned reuse_distance
; /* The amount of data accessed before the first
293 reuse of this value. */
294 struct mem_ref
*next
; /* The next reference in the group. */
295 unsigned write_p
: 1; /* Is it a write? */
296 unsigned independent_p
: 1; /* True if the reference is independent on
297 all other references inside the loop. */
298 unsigned issue_prefetch_p
: 1; /* Should we really issue the prefetch? */
299 unsigned storent_p
: 1; /* True if we changed the store to a
303 /* Dumps information about memory reference */
305 dump_mem_details (FILE *file
, tree base
, tree step
,
306 HOST_WIDE_INT delta
, bool write_p
)
308 fprintf (file
, "(base ");
309 print_generic_expr (file
, base
, TDF_SLIM
);
310 fprintf (file
, ", step ");
311 if (cst_and_fits_in_hwi (step
))
312 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, int_cst_value (step
));
314 print_generic_expr (file
, step
, TDF_TREE
);
315 fprintf (file
, ")\n");
316 fprintf (file
, " delta ");
317 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, delta
);
318 fprintf (file
, "\n");
319 fprintf (file
, " %s\n", write_p
? "write" : "read");
320 fprintf (file
, "\n");
323 /* Dumps information about reference REF to FILE. */
326 dump_mem_ref (FILE *file
, struct mem_ref
*ref
)
328 fprintf (file
, "Reference %p:\n", (void *) ref
);
330 fprintf (file
, " group %p ", (void *) ref
->group
);
332 dump_mem_details (file
, ref
->group
->base
, ref
->group
->step
, ref
->delta
,
336 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
339 static struct mem_ref_group
*
340 find_or_create_group (struct mem_ref_group
**groups
, tree base
, tree step
)
342 struct mem_ref_group
*group
;
344 for (; *groups
; groups
= &(*groups
)->next
)
346 if (operand_equal_p ((*groups
)->step
, step
, 0)
347 && operand_equal_p ((*groups
)->base
, base
, 0))
350 /* If step is an integer constant, keep the list of groups sorted
351 by decreasing step. */
352 if (cst_and_fits_in_hwi ((*groups
)->step
) && cst_and_fits_in_hwi (step
)
353 && int_cst_value ((*groups
)->step
) < int_cst_value (step
))
357 group
= XNEW (struct mem_ref_group
);
361 group
->next
= *groups
;
367 /* Records a memory reference MEM in GROUP with offset DELTA and write status
368 WRITE_P. The reference occurs in statement STMT. */
371 record_ref (struct mem_ref_group
*group
, gimple stmt
, tree mem
,
372 HOST_WIDE_INT delta
, bool write_p
)
374 struct mem_ref
**aref
;
376 /* Do not record the same address twice. */
377 for (aref
= &group
->refs
; *aref
; aref
= &(*aref
)->next
)
379 /* It does not have to be possible for write reference to reuse the read
380 prefetch, or vice versa. */
381 if (!WRITE_CAN_USE_READ_PREFETCH
383 && !(*aref
)->write_p
)
385 if (!READ_CAN_USE_WRITE_PREFETCH
390 if ((*aref
)->delta
== delta
)
394 (*aref
) = XNEW (struct mem_ref
);
395 (*aref
)->stmt
= stmt
;
397 (*aref
)->delta
= delta
;
398 (*aref
)->write_p
= write_p
;
399 (*aref
)->prefetch_before
= PREFETCH_ALL
;
400 (*aref
)->prefetch_mod
= 1;
401 (*aref
)->reuse_distance
= 0;
402 (*aref
)->issue_prefetch_p
= false;
403 (*aref
)->group
= group
;
404 (*aref
)->next
= NULL
;
405 (*aref
)->independent_p
= false;
406 (*aref
)->storent_p
= false;
408 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
409 dump_mem_ref (dump_file
, *aref
);
412 /* Release memory references in GROUPS. */
415 release_mem_refs (struct mem_ref_group
*groups
)
417 struct mem_ref_group
*next_g
;
418 struct mem_ref
*ref
, *next_r
;
420 for (; groups
; groups
= next_g
)
422 next_g
= groups
->next
;
423 for (ref
= groups
->refs
; ref
; ref
= next_r
)
432 /* A structure used to pass arguments to idx_analyze_ref. */
436 struct loop
*loop
; /* Loop of the reference. */
437 gimple stmt
; /* Statement of the reference. */
438 tree
*step
; /* Step of the memory reference. */
439 HOST_WIDE_INT
*delta
; /* Offset of the memory reference. */
442 /* Analyzes a single INDEX of a memory reference to obtain information
443 described at analyze_ref. Callback for for_each_index. */
446 idx_analyze_ref (tree base
, tree
*index
, void *data
)
448 struct ar_data
*ar_data
= (struct ar_data
*) data
;
449 tree ibase
, step
, stepsize
;
450 HOST_WIDE_INT idelta
= 0, imult
= 1;
453 if (!simple_iv (ar_data
->loop
, loop_containing_stmt (ar_data
->stmt
),
459 if (TREE_CODE (ibase
) == POINTER_PLUS_EXPR
460 && cst_and_fits_in_hwi (TREE_OPERAND (ibase
, 1)))
462 idelta
= int_cst_value (TREE_OPERAND (ibase
, 1));
463 ibase
= TREE_OPERAND (ibase
, 0);
465 if (cst_and_fits_in_hwi (ibase
))
467 idelta
+= int_cst_value (ibase
);
468 ibase
= build_int_cst (TREE_TYPE (ibase
), 0);
471 if (TREE_CODE (base
) == ARRAY_REF
)
473 stepsize
= array_ref_element_size (base
);
474 if (!cst_and_fits_in_hwi (stepsize
))
476 imult
= int_cst_value (stepsize
);
477 step
= fold_build2 (MULT_EXPR
, sizetype
,
478 fold_convert (sizetype
, step
),
479 fold_convert (sizetype
, stepsize
));
483 if (*ar_data
->step
== NULL_TREE
)
484 *ar_data
->step
= step
;
486 *ar_data
->step
= fold_build2 (PLUS_EXPR
, sizetype
,
487 fold_convert (sizetype
, *ar_data
->step
),
488 fold_convert (sizetype
, step
));
489 *ar_data
->delta
+= idelta
;
495 /* Tries to express REF_P in shape &BASE + STEP * iter + DELTA, where DELTA and
496 STEP are integer constants and iter is number of iterations of LOOP. The
497 reference occurs in statement STMT. Strips nonaddressable component
498 references from REF_P. */
501 analyze_ref (struct loop
*loop
, tree
*ref_p
, tree
*base
,
502 tree
*step
, HOST_WIDE_INT
*delta
,
505 struct ar_data ar_data
;
507 HOST_WIDE_INT bit_offset
;
513 /* First strip off the component references. Ignore bitfields.
514 Also strip off the real and imagine parts of a complex, so that
515 they can have the same base. */
516 if (TREE_CODE (ref
) == REALPART_EXPR
517 || TREE_CODE (ref
) == IMAGPART_EXPR
518 || (TREE_CODE (ref
) == COMPONENT_REF
519 && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref
, 1))))
521 if (TREE_CODE (ref
) == IMAGPART_EXPR
)
522 *delta
+= int_size_in_bytes (TREE_TYPE (ref
));
523 ref
= TREE_OPERAND (ref
, 0);
528 for (; TREE_CODE (ref
) == COMPONENT_REF
; ref
= TREE_OPERAND (ref
, 0))
530 off
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
531 bit_offset
= TREE_INT_CST_LOW (off
);
532 gcc_assert (bit_offset
% BITS_PER_UNIT
== 0);
534 *delta
+= bit_offset
/ BITS_PER_UNIT
;
537 *base
= unshare_expr (ref
);
541 ar_data
.delta
= delta
;
542 return for_each_index (base
, idx_analyze_ref
, &ar_data
);
545 /* Record a memory reference REF to the list REFS. The reference occurs in
546 LOOP in statement STMT and it is write if WRITE_P. Returns true if the
547 reference was recorded, false otherwise. */
550 gather_memory_references_ref (struct loop
*loop
, struct mem_ref_group
**refs
,
551 tree ref
, bool write_p
, gimple stmt
)
555 struct mem_ref_group
*agrp
;
557 if (get_base_address (ref
) == NULL
)
560 if (!analyze_ref (loop
, &ref
, &base
, &step
, &delta
, stmt
))
562 /* If analyze_ref fails the default is a NULL_TREE. We can stop here. */
563 if (step
== NULL_TREE
)
566 /* Stop if the address of BASE could not be taken. */
567 if (may_be_nonaddressable_p (base
))
570 /* Limit non-constant step prefetching only to the innermost loops and
571 only when the step is loop invariant in the entire loop nest. */
572 if (!cst_and_fits_in_hwi (step
))
574 if (loop
->inner
!= NULL
)
576 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
578 fprintf (dump_file
, "Memory expression %p\n",(void *) ref
);
579 print_generic_expr (dump_file
, ref
, TDF_TREE
);
580 fprintf (dump_file
,":");
581 dump_mem_details (dump_file
, base
, step
, delta
, write_p
);
583 "Ignoring %p, non-constant step prefetching is "
584 "limited to inner most loops \n",
591 if (!expr_invariant_in_loop_p (loop_outermost (loop
), step
))
593 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
595 fprintf (dump_file
, "Memory expression %p\n",(void *) ref
);
596 print_generic_expr (dump_file
, ref
, TDF_TREE
);
597 fprintf (dump_file
,":");
598 dump_mem_details (dump_file
, base
, step
, delta
, write_p
);
600 "Not prefetching, ignoring %p due to "
601 "loop variant step\n",
609 /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
610 are integer constants. */
611 agrp
= find_or_create_group (refs
, base
, step
);
612 record_ref (agrp
, stmt
, ref
, delta
, write_p
);
617 /* Record the suitable memory references in LOOP. NO_OTHER_REFS is set to
618 true if there are no other memory references inside the loop. */
620 static struct mem_ref_group
*
621 gather_memory_references (struct loop
*loop
, bool *no_other_refs
, unsigned *ref_count
)
623 basic_block
*body
= get_loop_body_in_dom_order (loop
);
626 gimple_stmt_iterator bsi
;
629 struct mem_ref_group
*refs
= NULL
;
631 *no_other_refs
= true;
634 /* Scan the loop body in order, so that the former references precede the
636 for (i
= 0; i
< loop
->num_nodes
; i
++)
639 if (bb
->loop_father
!= loop
)
642 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
644 stmt
= gsi_stmt (bsi
);
646 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
648 if (gimple_vuse (stmt
)
649 || (is_gimple_call (stmt
)
650 && !(gimple_call_flags (stmt
) & ECF_CONST
)))
651 *no_other_refs
= false;
655 lhs
= gimple_assign_lhs (stmt
);
656 rhs
= gimple_assign_rhs1 (stmt
);
658 if (REFERENCE_CLASS_P (rhs
))
660 *no_other_refs
&= gather_memory_references_ref (loop
, &refs
,
664 if (REFERENCE_CLASS_P (lhs
))
666 *no_other_refs
&= gather_memory_references_ref (loop
, &refs
,
677 /* Prune the prefetch candidate REF using the self-reuse. */
680 prune_ref_by_self_reuse (struct mem_ref
*ref
)
685 /* If the step size is non constant, we cannot calculate prefetch_mod. */
686 if (!cst_and_fits_in_hwi (ref
->group
->step
))
689 step
= int_cst_value (ref
->group
->step
);
695 /* Prefetch references to invariant address just once. */
696 ref
->prefetch_before
= 1;
703 if (step
> PREFETCH_BLOCK
)
706 if ((backward
&& HAVE_BACKWARD_PREFETCH
)
707 || (!backward
&& HAVE_FORWARD_PREFETCH
))
709 ref
->prefetch_before
= 1;
713 ref
->prefetch_mod
= PREFETCH_BLOCK
/ step
;
716 /* Divides X by BY, rounding down. */
719 ddown (HOST_WIDE_INT x
, unsigned HOST_WIDE_INT by
)
726 return (x
+ by
- 1) / by
;
729 /* Given a CACHE_LINE_SIZE and two inductive memory references
730 with a common STEP greater than CACHE_LINE_SIZE and an address
731 difference DELTA, compute the probability that they will fall
732 in different cache lines. Return true if the computed miss rate
733 is not greater than the ACCEPTABLE_MISS_RATE. DISTINCT_ITERS is the
734 number of distinct iterations after which the pattern repeats itself.
735 ALIGN_UNIT is the unit of alignment in bytes. */
738 is_miss_rate_acceptable (unsigned HOST_WIDE_INT cache_line_size
,
739 HOST_WIDE_INT step
, HOST_WIDE_INT delta
,
740 unsigned HOST_WIDE_INT distinct_iters
,
743 unsigned align
, iter
;
744 int total_positions
, miss_positions
, max_allowed_miss_positions
;
745 int address1
, address2
, cache_line1
, cache_line2
;
747 /* It always misses if delta is greater than or equal to the cache
749 if (delta
>= (HOST_WIDE_INT
) cache_line_size
)
753 total_positions
= (cache_line_size
/ align_unit
) * distinct_iters
;
754 max_allowed_miss_positions
= (ACCEPTABLE_MISS_RATE
* total_positions
) / 1000;
756 /* Iterate through all possible alignments of the first
757 memory reference within its cache line. */
758 for (align
= 0; align
< cache_line_size
; align
+= align_unit
)
760 /* Iterate through all distinct iterations. */
761 for (iter
= 0; iter
< distinct_iters
; iter
++)
763 address1
= align
+ step
* iter
;
764 address2
= address1
+ delta
;
765 cache_line1
= address1
/ cache_line_size
;
766 cache_line2
= address2
/ cache_line_size
;
767 if (cache_line1
!= cache_line2
)
770 if (miss_positions
> max_allowed_miss_positions
)
777 /* Prune the prefetch candidate REF using the reuse with BY.
778 If BY_IS_BEFORE is true, BY is before REF in the loop. */
781 prune_ref_by_group_reuse (struct mem_ref
*ref
, struct mem_ref
*by
,
786 HOST_WIDE_INT delta_r
= ref
->delta
, delta_b
= by
->delta
;
787 HOST_WIDE_INT delta
= delta_b
- delta_r
;
788 HOST_WIDE_INT hit_from
;
789 unsigned HOST_WIDE_INT prefetch_before
, prefetch_block
;
790 HOST_WIDE_INT reduced_step
;
791 unsigned HOST_WIDE_INT reduced_prefetch_block
;
795 /* If the step is non constant we cannot calculate prefetch_before. */
796 if (!cst_and_fits_in_hwi (ref
->group
->step
)) {
800 step
= int_cst_value (ref
->group
->step
);
807 /* If the references has the same address, only prefetch the
810 ref
->prefetch_before
= 0;
817 /* If the reference addresses are invariant and fall into the
818 same cache line, prefetch just the first one. */
822 if (ddown (ref
->delta
, PREFETCH_BLOCK
)
823 != ddown (by
->delta
, PREFETCH_BLOCK
))
826 ref
->prefetch_before
= 0;
830 /* Only prune the reference that is behind in the array. */
836 /* Transform the data so that we may assume that the accesses
840 delta_r
= PREFETCH_BLOCK
- 1 - delta_r
;
841 delta_b
= PREFETCH_BLOCK
- 1 - delta_b
;
849 /* Check whether the two references are likely to hit the same cache
850 line, and how distant the iterations in that it occurs are from
853 if (step
<= PREFETCH_BLOCK
)
855 /* The accesses are sure to meet. Let us check when. */
856 hit_from
= ddown (delta_b
, PREFETCH_BLOCK
) * PREFETCH_BLOCK
;
857 prefetch_before
= (hit_from
- delta_r
+ step
- 1) / step
;
859 /* Do not reduce prefetch_before if we meet beyond cache size. */
860 if (prefetch_before
> absu_hwi (L2_CACHE_SIZE_BYTES
/ step
))
861 prefetch_before
= PREFETCH_ALL
;
862 if (prefetch_before
< ref
->prefetch_before
)
863 ref
->prefetch_before
= prefetch_before
;
868 /* A more complicated case with step > prefetch_block. First reduce
869 the ratio between the step and the cache line size to its simplest
870 terms. The resulting denominator will then represent the number of
871 distinct iterations after which each address will go back to its
872 initial location within the cache line. This computation assumes
873 that PREFETCH_BLOCK is a power of two. */
874 prefetch_block
= PREFETCH_BLOCK
;
875 reduced_prefetch_block
= prefetch_block
;
877 while ((reduced_step
& 1) == 0
878 && reduced_prefetch_block
> 1)
881 reduced_prefetch_block
>>= 1;
884 prefetch_before
= delta
/ step
;
886 ref_type
= TREE_TYPE (ref
->mem
);
887 align_unit
= TYPE_ALIGN (ref_type
) / 8;
888 if (is_miss_rate_acceptable (prefetch_block
, step
, delta
,
889 reduced_prefetch_block
, align_unit
))
891 /* Do not reduce prefetch_before if we meet beyond cache size. */
892 if (prefetch_before
> L2_CACHE_SIZE_BYTES
/ PREFETCH_BLOCK
)
893 prefetch_before
= PREFETCH_ALL
;
894 if (prefetch_before
< ref
->prefetch_before
)
895 ref
->prefetch_before
= prefetch_before
;
900 /* Try also the following iteration. */
902 delta
= step
- delta
;
903 if (is_miss_rate_acceptable (prefetch_block
, step
, delta
,
904 reduced_prefetch_block
, align_unit
))
906 if (prefetch_before
< ref
->prefetch_before
)
907 ref
->prefetch_before
= prefetch_before
;
912 /* The ref probably does not reuse by. */
916 /* Prune the prefetch candidate REF using the reuses with other references
920 prune_ref_by_reuse (struct mem_ref
*ref
, struct mem_ref
*refs
)
922 struct mem_ref
*prune_by
;
925 prune_ref_by_self_reuse (ref
);
927 for (prune_by
= refs
; prune_by
; prune_by
= prune_by
->next
)
935 if (!WRITE_CAN_USE_READ_PREFETCH
937 && !prune_by
->write_p
)
939 if (!READ_CAN_USE_WRITE_PREFETCH
941 && prune_by
->write_p
)
944 prune_ref_by_group_reuse (ref
, prune_by
, before
);
948 /* Prune the prefetch candidates in GROUP using the reuse analysis. */
951 prune_group_by_reuse (struct mem_ref_group
*group
)
953 struct mem_ref
*ref_pruned
;
955 for (ref_pruned
= group
->refs
; ref_pruned
; ref_pruned
= ref_pruned
->next
)
957 prune_ref_by_reuse (ref_pruned
, group
->refs
);
959 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
961 fprintf (dump_file
, "Reference %p:", (void *) ref_pruned
);
963 if (ref_pruned
->prefetch_before
== PREFETCH_ALL
964 && ref_pruned
->prefetch_mod
== 1)
965 fprintf (dump_file
, " no restrictions");
966 else if (ref_pruned
->prefetch_before
== 0)
967 fprintf (dump_file
, " do not prefetch");
968 else if (ref_pruned
->prefetch_before
<= ref_pruned
->prefetch_mod
)
969 fprintf (dump_file
, " prefetch once");
972 if (ref_pruned
->prefetch_before
!= PREFETCH_ALL
)
974 fprintf (dump_file
, " prefetch before ");
975 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
976 ref_pruned
->prefetch_before
);
978 if (ref_pruned
->prefetch_mod
!= 1)
980 fprintf (dump_file
, " prefetch mod ");
981 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
982 ref_pruned
->prefetch_mod
);
985 fprintf (dump_file
, "\n");
990 /* Prune the list of prefetch candidates GROUPS using the reuse analysis. */
993 prune_by_reuse (struct mem_ref_group
*groups
)
995 for (; groups
; groups
= groups
->next
)
996 prune_group_by_reuse (groups
);
999 /* Returns true if we should issue prefetch for REF. */
1002 should_issue_prefetch_p (struct mem_ref
*ref
)
1004 /* For now do not issue prefetches for only first few of the
1006 if (ref
->prefetch_before
!= PREFETCH_ALL
)
1008 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1009 fprintf (dump_file
, "Ignoring %p due to prefetch_before\n",
1014 /* Do not prefetch nontemporal stores. */
1017 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1018 fprintf (dump_file
, "Ignoring nontemporal store %p\n", (void *) ref
);
1025 /* Decide which of the prefetch candidates in GROUPS to prefetch.
1026 AHEAD is the number of iterations to prefetch ahead (which corresponds
1027 to the number of simultaneous instances of one prefetch running at a
1028 time). UNROLL_FACTOR is the factor by that the loop is going to be
1029 unrolled. Returns true if there is anything to prefetch. */
1032 schedule_prefetches (struct mem_ref_group
*groups
, unsigned unroll_factor
,
1035 unsigned remaining_prefetch_slots
, n_prefetches
, prefetch_slots
;
1036 unsigned slots_per_prefetch
;
1037 struct mem_ref
*ref
;
1040 /* At most SIMULTANEOUS_PREFETCHES should be running at the same time. */
1041 remaining_prefetch_slots
= SIMULTANEOUS_PREFETCHES
;
1043 /* The prefetch will run for AHEAD iterations of the original loop, i.e.,
1044 AHEAD / UNROLL_FACTOR iterations of the unrolled loop. In each iteration,
1045 it will need a prefetch slot. */
1046 slots_per_prefetch
= (ahead
+ unroll_factor
/ 2) / unroll_factor
;
1047 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1048 fprintf (dump_file
, "Each prefetch instruction takes %u prefetch slots.\n",
1049 slots_per_prefetch
);
1051 /* For now we just take memory references one by one and issue
1052 prefetches for as many as possible. The groups are sorted
1053 starting with the largest step, since the references with
1054 large step are more likely to cause many cache misses. */
1056 for (; groups
; groups
= groups
->next
)
1057 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1059 if (!should_issue_prefetch_p (ref
))
1062 /* The loop is far from being sufficiently unrolled for this
1063 prefetch. Do not generate prefetch to avoid many redudant
1065 if (ref
->prefetch_mod
/ unroll_factor
> PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
)
1068 /* If we need to prefetch the reference each PREFETCH_MOD iterations,
1069 and we unroll the loop UNROLL_FACTOR times, we need to insert
1070 ceil (UNROLL_FACTOR / PREFETCH_MOD) instructions in each
1072 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1073 / ref
->prefetch_mod
);
1074 prefetch_slots
= n_prefetches
* slots_per_prefetch
;
1076 /* If more than half of the prefetches would be lost anyway, do not
1077 issue the prefetch. */
1078 if (2 * remaining_prefetch_slots
< prefetch_slots
)
1081 ref
->issue_prefetch_p
= true;
1083 if (remaining_prefetch_slots
<= prefetch_slots
)
1085 remaining_prefetch_slots
-= prefetch_slots
;
1092 /* Return TRUE if no prefetch is going to be generated in the given
1096 nothing_to_prefetch_p (struct mem_ref_group
*groups
)
1098 struct mem_ref
*ref
;
1100 for (; groups
; groups
= groups
->next
)
1101 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1102 if (should_issue_prefetch_p (ref
))
1108 /* Estimate the number of prefetches in the given GROUPS.
1109 UNROLL_FACTOR is the factor by which LOOP was unrolled. */
1112 estimate_prefetch_count (struct mem_ref_group
*groups
, unsigned unroll_factor
)
1114 struct mem_ref
*ref
;
1115 unsigned n_prefetches
;
1116 int prefetch_count
= 0;
1118 for (; groups
; groups
= groups
->next
)
1119 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1120 if (should_issue_prefetch_p (ref
))
1122 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1123 / ref
->prefetch_mod
);
1124 prefetch_count
+= n_prefetches
;
1127 return prefetch_count
;
1130 /* Issue prefetches for the reference REF into loop as decided before.
1131 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR
1132 is the factor by which LOOP was unrolled. */
1135 issue_prefetch_ref (struct mem_ref
*ref
, unsigned unroll_factor
, unsigned ahead
)
1137 HOST_WIDE_INT delta
;
1138 tree addr
, addr_base
, write_p
, local
, forward
;
1140 gimple_stmt_iterator bsi
;
1141 unsigned n_prefetches
, ap
;
1142 bool nontemporal
= ref
->reuse_distance
>= L2_CACHE_SIZE_BYTES
;
1144 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1145 fprintf (dump_file
, "Issued%s prefetch for %p.\n",
1146 nontemporal
? " nontemporal" : "",
1149 bsi
= gsi_for_stmt (ref
->stmt
);
1151 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1152 / ref
->prefetch_mod
);
1153 addr_base
= build_fold_addr_expr_with_type (ref
->mem
, ptr_type_node
);
1154 addr_base
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr_base
),
1155 true, NULL
, true, GSI_SAME_STMT
);
1156 write_p
= ref
->write_p
? integer_one_node
: integer_zero_node
;
1157 local
= nontemporal
? integer_zero_node
: integer_three_node
;
1159 for (ap
= 0; ap
< n_prefetches
; ap
++)
1161 if (cst_and_fits_in_hwi (ref
->group
->step
))
1163 /* Determine the address to prefetch. */
1164 delta
= (ahead
+ ap
* ref
->prefetch_mod
) *
1165 int_cst_value (ref
->group
->step
);
1166 addr
= fold_build_pointer_plus_hwi (addr_base
, delta
);
1167 addr
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr
), true, NULL
,
1168 true, GSI_SAME_STMT
);
1172 /* The step size is non-constant but loop-invariant. We use the
1173 heuristic to simply prefetch ahead iterations ahead. */
1174 forward
= fold_build2 (MULT_EXPR
, sizetype
,
1175 fold_convert (sizetype
, ref
->group
->step
),
1176 fold_convert (sizetype
, size_int (ahead
)));
1177 addr
= fold_build_pointer_plus (addr_base
, forward
);
1178 addr
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr
), true,
1179 NULL
, true, GSI_SAME_STMT
);
1181 /* Create the prefetch instruction. */
1182 prefetch
= gimple_build_call (builtin_decl_explicit (BUILT_IN_PREFETCH
),
1183 3, addr
, write_p
, local
);
1184 gsi_insert_before (&bsi
, prefetch
, GSI_SAME_STMT
);
1188 /* Issue prefetches for the references in GROUPS into loop as decided before.
1189 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR is the
1190 factor by that LOOP was unrolled. */
1193 issue_prefetches (struct mem_ref_group
*groups
,
1194 unsigned unroll_factor
, unsigned ahead
)
1196 struct mem_ref
*ref
;
1198 for (; groups
; groups
= groups
->next
)
1199 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1200 if (ref
->issue_prefetch_p
)
1201 issue_prefetch_ref (ref
, unroll_factor
, ahead
);
1204 /* Returns true if REF is a memory write for that a nontemporal store insn
1208 nontemporal_store_p (struct mem_ref
*ref
)
1210 enum machine_mode mode
;
1211 enum insn_code code
;
1213 /* REF must be a write that is not reused. We require it to be independent
1214 on all other memory references in the loop, as the nontemporal stores may
1215 be reordered with respect to other memory references. */
1217 || !ref
->independent_p
1218 || ref
->reuse_distance
< L2_CACHE_SIZE_BYTES
)
1221 /* Check that we have the storent instruction for the mode. */
1222 mode
= TYPE_MODE (TREE_TYPE (ref
->mem
));
1223 if (mode
== BLKmode
)
1226 code
= optab_handler (storent_optab
, mode
);
1227 return code
!= CODE_FOR_nothing
;
1230 /* If REF is a nontemporal store, we mark the corresponding modify statement
1231 and return true. Otherwise, we return false. */
1234 mark_nontemporal_store (struct mem_ref
*ref
)
1236 if (!nontemporal_store_p (ref
))
1239 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1240 fprintf (dump_file
, "Marked reference %p as a nontemporal store.\n",
1243 gimple_assign_set_nontemporal_move (ref
->stmt
, true);
1244 ref
->storent_p
= true;
1249 /* Issue a memory fence instruction after LOOP. */
1252 emit_mfence_after_loop (struct loop
*loop
)
1254 vec
<edge
> exits
= get_loop_exit_edges (loop
);
1257 gimple_stmt_iterator bsi
;
1260 FOR_EACH_VEC_ELT (exits
, i
, exit
)
1262 call
= gimple_build_call (FENCE_FOLLOWING_MOVNT
, 0);
1264 if (!single_pred_p (exit
->dest
)
1265 /* If possible, we prefer not to insert the fence on other paths
1267 && !(exit
->flags
& EDGE_ABNORMAL
))
1268 split_loop_exit_edge (exit
);
1269 bsi
= gsi_after_labels (exit
->dest
);
1271 gsi_insert_before (&bsi
, call
, GSI_NEW_STMT
);
1275 update_ssa (TODO_update_ssa_only_virtuals
);
1278 /* Returns true if we can use storent in loop, false otherwise. */
1281 may_use_storent_in_loop_p (struct loop
*loop
)
1285 if (loop
->inner
!= NULL
)
1288 /* If we must issue a mfence insn after using storent, check that there
1289 is a suitable place for it at each of the loop exits. */
1290 if (FENCE_FOLLOWING_MOVNT
!= NULL_TREE
)
1292 vec
<edge
> exits
= get_loop_exit_edges (loop
);
1296 FOR_EACH_VEC_ELT (exits
, i
, exit
)
1297 if ((exit
->flags
& EDGE_ABNORMAL
)
1298 && exit
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1307 /* Marks nontemporal stores in LOOP. GROUPS contains the description of memory
1308 references in the loop. */
1311 mark_nontemporal_stores (struct loop
*loop
, struct mem_ref_group
*groups
)
1313 struct mem_ref
*ref
;
1316 if (!may_use_storent_in_loop_p (loop
))
1319 for (; groups
; groups
= groups
->next
)
1320 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1321 any
|= mark_nontemporal_store (ref
);
1323 if (any
&& FENCE_FOLLOWING_MOVNT
!= NULL_TREE
)
1324 emit_mfence_after_loop (loop
);
1327 /* Determines whether we can profitably unroll LOOP FACTOR times, and if
1328 this is the case, fill in DESC by the description of number of
1332 should_unroll_loop_p (struct loop
*loop
, struct tree_niter_desc
*desc
,
1335 if (!can_unroll_loop_p (loop
, factor
, desc
))
1338 /* We only consider loops without control flow for unrolling. This is not
1339 a hard restriction -- tree_unroll_loop works with arbitrary loops
1340 as well; but the unrolling/prefetching is usually more profitable for
1341 loops consisting of a single basic block, and we want to limit the
1343 if (loop
->num_nodes
> 2)
1349 /* Determine the coefficient by that unroll LOOP, from the information
1350 contained in the list of memory references REFS. Description of
1351 umber of iterations of LOOP is stored to DESC. NINSNS is the number of
1352 insns of the LOOP. EST_NITER is the estimated number of iterations of
1353 the loop, or -1 if no estimate is available. */
1356 determine_unroll_factor (struct loop
*loop
, struct mem_ref_group
*refs
,
1357 unsigned ninsns
, struct tree_niter_desc
*desc
,
1358 HOST_WIDE_INT est_niter
)
1360 unsigned upper_bound
;
1361 unsigned nfactor
, factor
, mod_constraint
;
1362 struct mem_ref_group
*agp
;
1363 struct mem_ref
*ref
;
1365 /* First check whether the loop is not too large to unroll. We ignore
1366 PARAM_MAX_UNROLL_TIMES, because for small loops, it prevented us
1367 from unrolling them enough to make exactly one cache line covered by each
1368 iteration. Also, the goal of PARAM_MAX_UNROLL_TIMES is to prevent
1369 us from unrolling the loops too many times in cases where we only expect
1370 gains from better scheduling and decreasing loop overhead, which is not
1372 upper_bound
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / ninsns
;
1374 /* If we unrolled the loop more times than it iterates, the unrolled version
1375 of the loop would be never entered. */
1376 if (est_niter
>= 0 && est_niter
< (HOST_WIDE_INT
) upper_bound
)
1377 upper_bound
= est_niter
;
1379 if (upper_bound
<= 1)
1382 /* Choose the factor so that we may prefetch each cache just once,
1383 but bound the unrolling by UPPER_BOUND. */
1385 for (agp
= refs
; agp
; agp
= agp
->next
)
1386 for (ref
= agp
->refs
; ref
; ref
= ref
->next
)
1387 if (should_issue_prefetch_p (ref
))
1389 mod_constraint
= ref
->prefetch_mod
;
1390 nfactor
= least_common_multiple (mod_constraint
, factor
);
1391 if (nfactor
<= upper_bound
)
1395 if (!should_unroll_loop_p (loop
, desc
, factor
))
1401 /* Returns the total volume of the memory references REFS, taking into account
1402 reuses in the innermost loop and cache line size. TODO -- we should also
1403 take into account reuses across the iterations of the loops in the loop
1407 volume_of_references (struct mem_ref_group
*refs
)
1409 unsigned volume
= 0;
1410 struct mem_ref_group
*gr
;
1411 struct mem_ref
*ref
;
1413 for (gr
= refs
; gr
; gr
= gr
->next
)
1414 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1416 /* Almost always reuses another value? */
1417 if (ref
->prefetch_before
!= PREFETCH_ALL
)
1420 /* If several iterations access the same cache line, use the size of
1421 the line divided by this number. Otherwise, a cache line is
1422 accessed in each iteration. TODO -- in the latter case, we should
1423 take the size of the reference into account, rounding it up on cache
1424 line size multiple. */
1425 volume
+= L1_CACHE_LINE_SIZE
/ ref
->prefetch_mod
;
1430 /* Returns the volume of memory references accessed across VEC iterations of
1431 loops, whose sizes are described in the LOOP_SIZES array. N is the number
1432 of the loops in the nest (length of VEC and LOOP_SIZES vectors). */
1435 volume_of_dist_vector (lambda_vector vec
, unsigned *loop_sizes
, unsigned n
)
1439 for (i
= 0; i
< n
; i
++)
1446 gcc_assert (vec
[i
] > 0);
1448 /* We ignore the parts of the distance vector in subloops, since usually
1449 the numbers of iterations are much smaller. */
1450 return loop_sizes
[i
] * vec
[i
];
1453 /* Add the steps of ACCESS_FN multiplied by STRIDE to the array STRIDE
1454 at the position corresponding to the loop of the step. N is the depth
1455 of the considered loop nest, and, LOOP is its innermost loop. */
1458 add_subscript_strides (tree access_fn
, unsigned stride
,
1459 HOST_WIDE_INT
*strides
, unsigned n
, struct loop
*loop
)
1463 HOST_WIDE_INT astep
;
1464 unsigned min_depth
= loop_depth (loop
) - n
;
1466 while (TREE_CODE (access_fn
) == POLYNOMIAL_CHREC
)
1468 aloop
= get_chrec_loop (access_fn
);
1469 step
= CHREC_RIGHT (access_fn
);
1470 access_fn
= CHREC_LEFT (access_fn
);
1472 if ((unsigned) loop_depth (aloop
) <= min_depth
)
1475 if (tree_fits_shwi_p (step
))
1476 astep
= tree_to_shwi (step
);
1478 astep
= L1_CACHE_LINE_SIZE
;
1480 strides
[n
- 1 - loop_depth (loop
) + loop_depth (aloop
)] += astep
* stride
;
1485 /* Returns the volume of memory references accessed between two consecutive
1486 self-reuses of the reference DR. We consider the subscripts of DR in N
1487 loops, and LOOP_SIZES contains the volumes of accesses in each of the
1488 loops. LOOP is the innermost loop of the current loop nest. */
1491 self_reuse_distance (data_reference_p dr
, unsigned *loop_sizes
, unsigned n
,
1494 tree stride
, access_fn
;
1495 HOST_WIDE_INT
*strides
, astride
;
1496 vec
<tree
> access_fns
;
1497 tree ref
= DR_REF (dr
);
1498 unsigned i
, ret
= ~0u;
1500 /* In the following example:
1502 for (i = 0; i < N; i++)
1503 for (j = 0; j < N; j++)
1505 the same cache line is accessed each N steps (except if the change from
1506 i to i + 1 crosses the boundary of the cache line). Thus, for self-reuse,
1507 we cannot rely purely on the results of the data dependence analysis.
1509 Instead, we compute the stride of the reference in each loop, and consider
1510 the innermost loop in that the stride is less than cache size. */
1512 strides
= XCNEWVEC (HOST_WIDE_INT
, n
);
1513 access_fns
= DR_ACCESS_FNS (dr
);
1515 FOR_EACH_VEC_ELT (access_fns
, i
, access_fn
)
1517 /* Keep track of the reference corresponding to the subscript, so that we
1519 while (handled_component_p (ref
) && TREE_CODE (ref
) != ARRAY_REF
)
1520 ref
= TREE_OPERAND (ref
, 0);
1522 if (TREE_CODE (ref
) == ARRAY_REF
)
1524 stride
= TYPE_SIZE_UNIT (TREE_TYPE (ref
));
1525 if (tree_fits_uhwi_p (stride
))
1526 astride
= tree_to_uhwi (stride
);
1528 astride
= L1_CACHE_LINE_SIZE
;
1530 ref
= TREE_OPERAND (ref
, 0);
1535 add_subscript_strides (access_fn
, astride
, strides
, n
, loop
);
1538 for (i
= n
; i
-- > 0; )
1540 unsigned HOST_WIDE_INT s
;
1542 s
= strides
[i
] < 0 ? -strides
[i
] : strides
[i
];
1544 if (s
< (unsigned) L1_CACHE_LINE_SIZE
1546 > (unsigned) (L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)))
1548 ret
= loop_sizes
[i
];
1557 /* Determines the distance till the first reuse of each reference in REFS
1558 in the loop nest of LOOP. NO_OTHER_REFS is true if there are no other
1559 memory references in the loop. Return false if the analysis fails. */
1562 determine_loop_nest_reuse (struct loop
*loop
, struct mem_ref_group
*refs
,
1565 struct loop
*nest
, *aloop
;
1566 vec
<data_reference_p
> datarefs
= vNULL
;
1567 vec
<ddr_p
> dependences
= vNULL
;
1568 struct mem_ref_group
*gr
;
1569 struct mem_ref
*ref
, *refb
;
1570 vec
<loop_p
> vloops
= vNULL
;
1571 unsigned *loop_data_size
;
1573 unsigned volume
, dist
, adist
;
1575 data_reference_p dr
;
1581 /* Find the outermost loop of the loop nest of loop (we require that
1582 there are no sibling loops inside the nest). */
1586 aloop
= loop_outer (nest
);
1588 if (aloop
== current_loops
->tree_root
1589 || aloop
->inner
->next
)
1595 /* For each loop, determine the amount of data accessed in each iteration.
1596 We use this to estimate whether the reference is evicted from the
1597 cache before its reuse. */
1598 find_loop_nest (nest
, &vloops
);
1599 n
= vloops
.length ();
1600 loop_data_size
= XNEWVEC (unsigned, n
);
1601 volume
= volume_of_references (refs
);
1605 loop_data_size
[i
] = volume
;
1606 /* Bound the volume by the L2 cache size, since above this bound,
1607 all dependence distances are equivalent. */
1608 if (volume
> L2_CACHE_SIZE_BYTES
)
1612 vol
= estimated_stmt_executions_int (aloop
);
1614 vol
= expected_loop_iterations (aloop
);
1618 /* Prepare the references in the form suitable for data dependence
1619 analysis. We ignore unanalyzable data references (the results
1620 are used just as a heuristics to estimate temporality of the
1621 references, hence we do not need to worry about correctness). */
1622 for (gr
= refs
; gr
; gr
= gr
->next
)
1623 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1625 dr
= create_data_ref (nest
, loop_containing_stmt (ref
->stmt
),
1626 ref
->mem
, ref
->stmt
, !ref
->write_p
);
1630 ref
->reuse_distance
= volume
;
1632 datarefs
.safe_push (dr
);
1635 no_other_refs
= false;
1638 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
1640 dist
= self_reuse_distance (dr
, loop_data_size
, n
, loop
);
1641 ref
= (struct mem_ref
*) dr
->aux
;
1642 if (ref
->reuse_distance
> dist
)
1643 ref
->reuse_distance
= dist
;
1646 ref
->independent_p
= true;
1649 if (!compute_all_dependences (datarefs
, &dependences
, vloops
, true))
1652 FOR_EACH_VEC_ELT (dependences
, i
, dep
)
1654 if (DDR_ARE_DEPENDENT (dep
) == chrec_known
)
1657 ref
= (struct mem_ref
*) DDR_A (dep
)->aux
;
1658 refb
= (struct mem_ref
*) DDR_B (dep
)->aux
;
1660 if (DDR_ARE_DEPENDENT (dep
) == chrec_dont_know
1661 || DDR_NUM_DIST_VECTS (dep
) == 0)
1663 /* If the dependence cannot be analyzed, assume that there might be
1667 ref
->independent_p
= false;
1668 refb
->independent_p
= false;
1672 /* The distance vectors are normalized to be always lexicographically
1673 positive, hence we cannot tell just from them whether DDR_A comes
1674 before DDR_B or vice versa. However, it is not important,
1675 anyway -- if DDR_A is close to DDR_B, then it is either reused in
1676 DDR_B (and it is not nontemporal), or it reuses the value of DDR_B
1677 in cache (and marking it as nontemporal would not affect
1681 for (j
= 0; j
< DDR_NUM_DIST_VECTS (dep
); j
++)
1683 adist
= volume_of_dist_vector (DDR_DIST_VECT (dep
, j
),
1686 /* If this is a dependence in the innermost loop (i.e., the
1687 distances in all superloops are zero) and it is not
1688 the trivial self-dependence with distance zero, record that
1689 the references are not completely independent. */
1690 if (lambda_vector_zerop (DDR_DIST_VECT (dep
, j
), n
- 1)
1692 || DDR_DIST_VECT (dep
, j
)[n
-1] != 0))
1694 ref
->independent_p
= false;
1695 refb
->independent_p
= false;
1698 /* Ignore accesses closer than
1699 L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
1700 so that we use nontemporal prefetches e.g. if single memory
1701 location is accessed several times in a single iteration of
1703 if (adist
< L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)
1711 if (ref
->reuse_distance
> dist
)
1712 ref
->reuse_distance
= dist
;
1713 if (refb
->reuse_distance
> dist
)
1714 refb
->reuse_distance
= dist
;
1717 free_dependence_relations (dependences
);
1718 free_data_refs (datarefs
);
1719 free (loop_data_size
);
1721 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1723 fprintf (dump_file
, "Reuse distances:\n");
1724 for (gr
= refs
; gr
; gr
= gr
->next
)
1725 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1726 fprintf (dump_file
, " ref %p distance %u\n",
1727 (void *) ref
, ref
->reuse_distance
);
1733 /* Determine whether or not the trip count to ahead ratio is too small based
1734 on prefitablility consideration.
1735 AHEAD: the iteration ahead distance,
1736 EST_NITER: the estimated trip count. */
1739 trip_count_to_ahead_ratio_too_small_p (unsigned ahead
, HOST_WIDE_INT est_niter
)
1741 /* Assume trip count to ahead ratio is big enough if the trip count could not
1742 be estimated at compile time. */
1746 if (est_niter
< (HOST_WIDE_INT
) (TRIP_COUNT_TO_AHEAD_RATIO
* ahead
))
1748 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1750 "Not prefetching -- loop estimated to roll only %d times\n",
1758 /* Determine whether or not the number of memory references in the loop is
1759 reasonable based on the profitablity and compilation time considerations.
1760 NINSNS: estimated number of instructions in the loop,
1761 MEM_REF_COUNT: total number of memory references in the loop. */
1764 mem_ref_count_reasonable_p (unsigned ninsns
, unsigned mem_ref_count
)
1766 int insn_to_mem_ratio
;
1768 if (mem_ref_count
== 0)
1771 /* Miss rate computation (is_miss_rate_acceptable) and dependence analysis
1772 (compute_all_dependences) have high costs based on quadratic complexity.
1773 To avoid huge compilation time, we give up prefetching if mem_ref_count
1775 if (mem_ref_count
> PREFETCH_MAX_MEM_REFS_PER_LOOP
)
1778 /* Prefetching improves performance by overlapping cache missing
1779 memory accesses with CPU operations. If the loop does not have
1780 enough CPU operations to overlap with memory operations, prefetching
1781 won't give a significant benefit. One approximate way of checking
1782 this is to require the ratio of instructions to memory references to
1783 be above a certain limit. This approximation works well in practice.
1784 TODO: Implement a more precise computation by estimating the time
1785 for each CPU or memory op in the loop. Time estimates for memory ops
1786 should account for cache misses. */
1787 insn_to_mem_ratio
= ninsns
/ mem_ref_count
;
1789 if (insn_to_mem_ratio
< PREFETCH_MIN_INSN_TO_MEM_RATIO
)
1791 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1793 "Not prefetching -- instruction to memory reference ratio (%d) too small\n",
1801 /* Determine whether or not the instruction to prefetch ratio in the loop is
1802 too small based on the profitablity consideration.
1803 NINSNS: estimated number of instructions in the loop,
1804 PREFETCH_COUNT: an estimate of the number of prefetches,
1805 UNROLL_FACTOR: the factor to unroll the loop if prefetching. */
1808 insn_to_prefetch_ratio_too_small_p (unsigned ninsns
, unsigned prefetch_count
,
1809 unsigned unroll_factor
)
1811 int insn_to_prefetch_ratio
;
1813 /* Prefetching most likely causes performance degradation when the instruction
1814 to prefetch ratio is too small. Too many prefetch instructions in a loop
1815 may reduce the I-cache performance.
1816 (unroll_factor * ninsns) is used to estimate the number of instructions in
1817 the unrolled loop. This implementation is a bit simplistic -- the number
1818 of issued prefetch instructions is also affected by unrolling. So,
1819 prefetch_mod and the unroll factor should be taken into account when
1820 determining prefetch_count. Also, the number of insns of the unrolled
1821 loop will usually be significantly smaller than the number of insns of the
1822 original loop * unroll_factor (at least the induction variable increases
1823 and the exit branches will get eliminated), so it might be better to use
1824 tree_estimate_loop_size + estimated_unrolled_size. */
1825 insn_to_prefetch_ratio
= (unroll_factor
* ninsns
) / prefetch_count
;
1826 if (insn_to_prefetch_ratio
< MIN_INSN_TO_PREFETCH_RATIO
)
1828 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1830 "Not prefetching -- instruction to prefetch ratio (%d) too small\n",
1831 insn_to_prefetch_ratio
);
1839 /* Issue prefetch instructions for array references in LOOP. Returns
1840 true if the LOOP was unrolled. */
1843 loop_prefetch_arrays (struct loop
*loop
)
1845 struct mem_ref_group
*refs
;
1846 unsigned ahead
, ninsns
, time
, unroll_factor
;
1847 HOST_WIDE_INT est_niter
;
1848 struct tree_niter_desc desc
;
1849 bool unrolled
= false, no_other_refs
;
1850 unsigned prefetch_count
;
1851 unsigned mem_ref_count
;
1853 if (optimize_loop_nest_for_size_p (loop
))
1855 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1856 fprintf (dump_file
, " ignored (cold area)\n");
1860 /* FIXME: the time should be weighted by the probabilities of the blocks in
1862 time
= tree_num_loop_insns (loop
, &eni_time_weights
);
1866 ahead
= (PREFETCH_LATENCY
+ time
- 1) / time
;
1867 est_niter
= estimated_stmt_executions_int (loop
);
1868 if (est_niter
== -1)
1869 est_niter
= max_stmt_executions_int (loop
);
1871 /* Prefetching is not likely to be profitable if the trip count to ahead
1872 ratio is too small. */
1873 if (trip_count_to_ahead_ratio_too_small_p (ahead
, est_niter
))
1876 ninsns
= tree_num_loop_insns (loop
, &eni_size_weights
);
1878 /* Step 1: gather the memory references. */
1879 refs
= gather_memory_references (loop
, &no_other_refs
, &mem_ref_count
);
1881 /* Give up prefetching if the number of memory references in the
1882 loop is not reasonable based on profitablity and compilation time
1884 if (!mem_ref_count_reasonable_p (ninsns
, mem_ref_count
))
1887 /* Step 2: estimate the reuse effects. */
1888 prune_by_reuse (refs
);
1890 if (nothing_to_prefetch_p (refs
))
1893 if (!determine_loop_nest_reuse (loop
, refs
, no_other_refs
))
1896 /* Step 3: determine unroll factor. */
1897 unroll_factor
= determine_unroll_factor (loop
, refs
, ninsns
, &desc
,
1900 /* Estimate prefetch count for the unrolled loop. */
1901 prefetch_count
= estimate_prefetch_count (refs
, unroll_factor
);
1902 if (prefetch_count
== 0)
1905 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1906 fprintf (dump_file
, "Ahead %d, unroll factor %d, trip count "
1907 HOST_WIDE_INT_PRINT_DEC
"\n"
1908 "insn count %d, mem ref count %d, prefetch count %d\n",
1909 ahead
, unroll_factor
, est_niter
,
1910 ninsns
, mem_ref_count
, prefetch_count
);
1912 /* Prefetching is not likely to be profitable if the instruction to prefetch
1913 ratio is too small. */
1914 if (insn_to_prefetch_ratio_too_small_p (ninsns
, prefetch_count
,
1918 mark_nontemporal_stores (loop
, refs
);
1920 /* Step 4: what to prefetch? */
1921 if (!schedule_prefetches (refs
, unroll_factor
, ahead
))
1924 /* Step 5: unroll the loop. TODO -- peeling of first and last few
1925 iterations so that we do not issue superfluous prefetches. */
1926 if (unroll_factor
!= 1)
1928 tree_unroll_loop (loop
, unroll_factor
,
1929 single_dom_exit (loop
), &desc
);
1933 /* Step 6: issue the prefetches. */
1934 issue_prefetches (refs
, unroll_factor
, ahead
);
1937 release_mem_refs (refs
);
1941 /* Issue prefetch instructions for array references in loops. */
1944 tree_ssa_prefetch_arrays (void)
1947 bool unrolled
= false;
1951 /* It is possible to ask compiler for say -mtune=i486 -march=pentium4.
1952 -mtune=i486 causes us having PREFETCH_BLOCK 0, since this is part
1953 of processor costs and i486 does not have prefetch, but
1954 -march=pentium4 causes HAVE_prefetch to be true. Ugh. */
1955 || PREFETCH_BLOCK
== 0)
1958 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1960 fprintf (dump_file
, "Prefetching parameters:\n");
1961 fprintf (dump_file
, " simultaneous prefetches: %d\n",
1962 SIMULTANEOUS_PREFETCHES
);
1963 fprintf (dump_file
, " prefetch latency: %d\n", PREFETCH_LATENCY
);
1964 fprintf (dump_file
, " prefetch block size: %d\n", PREFETCH_BLOCK
);
1965 fprintf (dump_file
, " L1 cache size: %d lines, %d kB\n",
1966 L1_CACHE_SIZE_BYTES
/ L1_CACHE_LINE_SIZE
, L1_CACHE_SIZE
);
1967 fprintf (dump_file
, " L1 cache line size: %d\n", L1_CACHE_LINE_SIZE
);
1968 fprintf (dump_file
, " L2 cache size: %d kB\n", L2_CACHE_SIZE
);
1969 fprintf (dump_file
, " min insn-to-prefetch ratio: %d \n",
1970 MIN_INSN_TO_PREFETCH_RATIO
);
1971 fprintf (dump_file
, " min insn-to-mem ratio: %d \n",
1972 PREFETCH_MIN_INSN_TO_MEM_RATIO
);
1973 fprintf (dump_file
, "\n");
1976 initialize_original_copy_tables ();
1978 if (!builtin_decl_explicit_p (BUILT_IN_PREFETCH
))
1980 tree type
= build_function_type_list (void_type_node
,
1981 const_ptr_type_node
, NULL_TREE
);
1982 tree decl
= add_builtin_function ("__builtin_prefetch", type
,
1983 BUILT_IN_PREFETCH
, BUILT_IN_NORMAL
,
1985 DECL_IS_NOVOPS (decl
) = true;
1986 set_builtin_decl (BUILT_IN_PREFETCH
, decl
, false);
1989 /* We assume that size of cache line is a power of two, so verify this
1991 gcc_assert ((PREFETCH_BLOCK
& (PREFETCH_BLOCK
- 1)) == 0);
1993 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1995 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1996 fprintf (dump_file
, "Processing loop %d:\n", loop
->num
);
1998 unrolled
|= loop_prefetch_arrays (loop
);
2000 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2001 fprintf (dump_file
, "\n\n");
2007 todo_flags
|= TODO_cleanup_cfg
;
2010 free_original_copy_tables ();
2018 const pass_data pass_data_loop_prefetch
=
2020 GIMPLE_PASS
, /* type */
2021 "aprefetch", /* name */
2022 OPTGROUP_LOOP
, /* optinfo_flags */
2023 TV_TREE_PREFETCH
, /* tv_id */
2024 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2025 0, /* properties_provided */
2026 0, /* properties_destroyed */
2027 0, /* todo_flags_start */
2028 0, /* todo_flags_finish */
2031 class pass_loop_prefetch
: public gimple_opt_pass
2034 pass_loop_prefetch (gcc::context
*ctxt
)
2035 : gimple_opt_pass (pass_data_loop_prefetch
, ctxt
)
2038 /* opt_pass methods: */
2039 virtual bool gate (function
*) { return flag_prefetch_loop_arrays
> 0; }
2040 virtual unsigned int execute (function
*);
2042 }; // class pass_loop_prefetch
2045 pass_loop_prefetch::execute (function
*fun
)
2047 if (number_of_loops (fun
) <= 1)
2050 return tree_ssa_prefetch_arrays ();
2056 make_pass_loop_prefetch (gcc::context
*ctxt
)
2058 return new pass_loop_prefetch (ctxt
);