2 Copyright (C) 2005-2015 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"
31 #include "fold-const.h"
32 #include "stor-layout.h"
35 #include "hard-reg-set.h"
37 #include "dominance.h"
39 #include "basic-block.h"
40 #include "tree-pretty-print.h"
41 #include "tree-ssa-alias.h"
42 #include "internal-fn.h"
43 #include "gimple-expr.h"
47 #include "gimple-iterator.h"
48 #include "gimplify-me.h"
49 #include "gimple-ssa.h"
50 #include "tree-ssa-loop-ivopts.h"
51 #include "tree-ssa-loop-manip.h"
52 #include "tree-ssa-loop-niter.h"
53 #include "tree-ssa-loop.h"
54 #include "tree-into-ssa.h"
56 #include "tree-pass.h"
57 #include "insn-config.h"
58 #include "tree-chrec.h"
59 #include "tree-scalar-evolution.h"
60 #include "diagnostic-core.h"
62 #include "langhooks.h"
63 #include "tree-inline.h"
64 #include "tree-data-ref.h"
67 /* FIXME: Needed for optabs, but this should all be moved to a TBD interface
68 between the GIMPLE and RTL worlds. */
72 #include "statistics.h"
81 #include "insn-codes.h"
85 /* This pass inserts prefetch instructions to optimize cache usage during
86 accesses to arrays in loops. It processes loops sequentially and:
88 1) Gathers all memory references in the single loop.
89 2) For each of the references it decides when it is profitable to prefetch
90 it. To do it, we evaluate the reuse among the accesses, and determines
91 two values: PREFETCH_BEFORE (meaning that it only makes sense to do
92 prefetching in the first PREFETCH_BEFORE iterations of the loop) and
93 PREFETCH_MOD (meaning that it only makes sense to prefetch in the
94 iterations of the loop that are zero modulo PREFETCH_MOD). For example
95 (assuming cache line size is 64 bytes, char has size 1 byte and there
96 is no hardware sequential prefetch):
99 for (i = 0; i < max; i++)
106 a[187*i + 50] = ...; (5)
109 (0) obviously has PREFETCH_BEFORE 1
110 (1) has PREFETCH_BEFORE 64, since (2) accesses the same memory
111 location 64 iterations before it, and PREFETCH_MOD 64 (since
112 it hits the same cache line otherwise).
113 (2) has PREFETCH_MOD 64
114 (3) has PREFETCH_MOD 4
115 (4) has PREFETCH_MOD 1. We do not set PREFETCH_BEFORE here, since
116 the cache line accessed by (5) is the same with probability only
118 (5) has PREFETCH_MOD 1 as well.
120 Additionally, we use data dependence analysis to determine for each
121 reference the distance till the first reuse; this information is used
122 to determine the temporality of the issued prefetch instruction.
124 3) We determine how much ahead we need to prefetch. The number of
125 iterations needed is time to fetch / time spent in one iteration of
126 the loop. The problem is that we do not know either of these values,
127 so we just make a heuristic guess based on a magic (possibly)
128 target-specific constant and size of the loop.
130 4) Determine which of the references we prefetch. We take into account
131 that there is a maximum number of simultaneous prefetches (provided
132 by machine description). We prefetch as many prefetches as possible
133 while still within this bound (starting with those with lowest
134 prefetch_mod, since they are responsible for most of the cache
137 5) We unroll and peel loops so that we are able to satisfy PREFETCH_MOD
138 and PREFETCH_BEFORE requirements (within some bounds), and to avoid
139 prefetching nonaccessed memory.
140 TODO -- actually implement peeling.
142 6) We actually emit the prefetch instructions. ??? Perhaps emit the
143 prefetch instructions with guards in cases where 5) was not sufficient
144 to satisfy the constraints?
146 A cost model is implemented to determine whether or not prefetching is
147 profitable for a given loop. The cost model has three heuristics:
149 1. Function trip_count_to_ahead_ratio_too_small_p implements a
150 heuristic that determines whether or not the loop has too few
151 iterations (compared to ahead). Prefetching is not likely to be
152 beneficial if the trip count to ahead ratio is below a certain
155 2. Function mem_ref_count_reasonable_p implements a heuristic that
156 determines whether the given loop has enough CPU ops that can be
157 overlapped with cache missing memory ops. If not, the loop
158 won't benefit from prefetching. In the implementation,
159 prefetching is not considered beneficial if the ratio between
160 the instruction count and the mem ref count is below a certain
163 3. Function insn_to_prefetch_ratio_too_small_p implements a
164 heuristic that disables prefetching in a loop if the prefetching
165 cost is above a certain limit. The relative prefetching cost is
166 estimated by taking the ratio between the prefetch count and the
167 total intruction count (this models the I-cache cost).
169 The limits used in these heuristics are defined as parameters with
170 reasonable default values. Machine-specific default values will be
174 -- write and use more general reuse analysis (that could be also used
175 in other cache aimed loop optimizations)
176 -- make it behave sanely together with the prefetches given by user
177 (now we just ignore them; at the very least we should avoid
178 optimizing loops in that user put his own prefetches)
179 -- we assume cache line size alignment of arrays; this could be
182 /* Magic constants follow. These should be replaced by machine specific
185 /* True if write can be prefetched by a read prefetch. */
187 #ifndef WRITE_CAN_USE_READ_PREFETCH
188 #define WRITE_CAN_USE_READ_PREFETCH 1
191 /* True if read can be prefetched by a write prefetch. */
193 #ifndef READ_CAN_USE_WRITE_PREFETCH
194 #define READ_CAN_USE_WRITE_PREFETCH 0
197 /* The size of the block loaded by a single prefetch. Usually, this is
198 the same as cache line size (at the moment, we only consider one level
199 of cache hierarchy). */
201 #ifndef PREFETCH_BLOCK
202 #define PREFETCH_BLOCK L1_CACHE_LINE_SIZE
205 /* Do we have a forward hardware sequential prefetching? */
207 #ifndef HAVE_FORWARD_PREFETCH
208 #define HAVE_FORWARD_PREFETCH 0
211 /* Do we have a backward hardware sequential prefetching? */
213 #ifndef HAVE_BACKWARD_PREFETCH
214 #define HAVE_BACKWARD_PREFETCH 0
217 /* In some cases we are only able to determine that there is a certain
218 probability that the two accesses hit the same cache line. In this
219 case, we issue the prefetches for both of them if this probability
220 is less then (1000 - ACCEPTABLE_MISS_RATE) per thousand. */
222 #ifndef ACCEPTABLE_MISS_RATE
223 #define ACCEPTABLE_MISS_RATE 50
226 #ifndef HAVE_prefetch
227 #define HAVE_prefetch 0
230 #define L1_CACHE_SIZE_BYTES ((unsigned) (L1_CACHE_SIZE * 1024))
231 #define L2_CACHE_SIZE_BYTES ((unsigned) (L2_CACHE_SIZE * 1024))
233 /* We consider a memory access nontemporal if it is not reused sooner than
234 after L2_CACHE_SIZE_BYTES of memory are accessed. However, we ignore
235 accesses closer than L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
236 so that we use nontemporal prefetches e.g. if single memory location
237 is accessed several times in a single iteration of the loop. */
238 #define NONTEMPORAL_FRACTION 16
240 /* In case we have to emit a memory fence instruction after the loop that
241 uses nontemporal stores, this defines the builtin to use. */
243 #ifndef FENCE_FOLLOWING_MOVNT
244 #define FENCE_FOLLOWING_MOVNT NULL_TREE
247 /* It is not profitable to prefetch when the trip count is not at
248 least TRIP_COUNT_TO_AHEAD_RATIO times the prefetch ahead distance.
249 For example, in a loop with a prefetch ahead distance of 10,
250 supposing that TRIP_COUNT_TO_AHEAD_RATIO is equal to 4, it is
251 profitable to prefetch when the trip count is greater or equal to
252 40. In that case, 30 out of the 40 iterations will benefit from
255 #ifndef TRIP_COUNT_TO_AHEAD_RATIO
256 #define TRIP_COUNT_TO_AHEAD_RATIO 4
259 /* The group of references between that reuse may occur. */
263 tree base
; /* Base of the reference. */
264 tree step
; /* Step of the reference. */
265 struct mem_ref
*refs
; /* References in the group. */
266 struct mem_ref_group
*next
; /* Next group of references. */
269 /* Assigned to PREFETCH_BEFORE when all iterations are to be prefetched. */
271 #define PREFETCH_ALL (~(unsigned HOST_WIDE_INT) 0)
273 /* Do not generate a prefetch if the unroll factor is significantly less
274 than what is required by the prefetch. This is to avoid redundant
275 prefetches. For example, when prefetch_mod is 16 and unroll_factor is
276 2, prefetching requires unrolling the loop 16 times, but
277 the loop is actually unrolled twice. In this case (ratio = 8),
278 prefetching is not likely to be beneficial. */
280 #ifndef PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
281 #define PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO 4
284 /* Some of the prefetch computations have quadratic complexity. We want to
285 avoid huge compile times and, therefore, want to limit the amount of
286 memory references per loop where we consider prefetching. */
288 #ifndef PREFETCH_MAX_MEM_REFS_PER_LOOP
289 #define PREFETCH_MAX_MEM_REFS_PER_LOOP 200
292 /* The memory reference. */
296 gimple stmt
; /* Statement in that the reference appears. */
297 tree mem
; /* The reference. */
298 HOST_WIDE_INT delta
; /* Constant offset of the reference. */
299 struct mem_ref_group
*group
; /* The group of references it belongs to. */
300 unsigned HOST_WIDE_INT prefetch_mod
;
301 /* Prefetch only each PREFETCH_MOD-th
303 unsigned HOST_WIDE_INT prefetch_before
;
304 /* Prefetch only first PREFETCH_BEFORE
306 unsigned reuse_distance
; /* The amount of data accessed before the first
307 reuse of this value. */
308 struct mem_ref
*next
; /* The next reference in the group. */
309 unsigned write_p
: 1; /* Is it a write? */
310 unsigned independent_p
: 1; /* True if the reference is independent on
311 all other references inside the loop. */
312 unsigned issue_prefetch_p
: 1; /* Should we really issue the prefetch? */
313 unsigned storent_p
: 1; /* True if we changed the store to a
317 /* Dumps information about memory reference */
319 dump_mem_details (FILE *file
, tree base
, tree step
,
320 HOST_WIDE_INT delta
, bool write_p
)
322 fprintf (file
, "(base ");
323 print_generic_expr (file
, base
, TDF_SLIM
);
324 fprintf (file
, ", step ");
325 if (cst_and_fits_in_hwi (step
))
326 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, int_cst_value (step
));
328 print_generic_expr (file
, step
, TDF_TREE
);
329 fprintf (file
, ")\n");
330 fprintf (file
, " delta ");
331 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, delta
);
332 fprintf (file
, "\n");
333 fprintf (file
, " %s\n", write_p
? "write" : "read");
334 fprintf (file
, "\n");
337 /* Dumps information about reference REF to FILE. */
340 dump_mem_ref (FILE *file
, struct mem_ref
*ref
)
342 fprintf (file
, "Reference %p:\n", (void *) ref
);
344 fprintf (file
, " group %p ", (void *) ref
->group
);
346 dump_mem_details (file
, ref
->group
->base
, ref
->group
->step
, ref
->delta
,
350 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
353 static struct mem_ref_group
*
354 find_or_create_group (struct mem_ref_group
**groups
, tree base
, tree step
)
356 struct mem_ref_group
*group
;
358 for (; *groups
; groups
= &(*groups
)->next
)
360 if (operand_equal_p ((*groups
)->step
, step
, 0)
361 && operand_equal_p ((*groups
)->base
, base
, 0))
364 /* If step is an integer constant, keep the list of groups sorted
365 by decreasing step. */
366 if (cst_and_fits_in_hwi ((*groups
)->step
) && cst_and_fits_in_hwi (step
)
367 && int_cst_value ((*groups
)->step
) < int_cst_value (step
))
371 group
= XNEW (struct mem_ref_group
);
375 group
->next
= *groups
;
381 /* Records a memory reference MEM in GROUP with offset DELTA and write status
382 WRITE_P. The reference occurs in statement STMT. */
385 record_ref (struct mem_ref_group
*group
, gimple stmt
, tree mem
,
386 HOST_WIDE_INT delta
, bool write_p
)
388 struct mem_ref
**aref
;
390 /* Do not record the same address twice. */
391 for (aref
= &group
->refs
; *aref
; aref
= &(*aref
)->next
)
393 /* It does not have to be possible for write reference to reuse the read
394 prefetch, or vice versa. */
395 if (!WRITE_CAN_USE_READ_PREFETCH
397 && !(*aref
)->write_p
)
399 if (!READ_CAN_USE_WRITE_PREFETCH
404 if ((*aref
)->delta
== delta
)
408 (*aref
) = XNEW (struct mem_ref
);
409 (*aref
)->stmt
= stmt
;
411 (*aref
)->delta
= delta
;
412 (*aref
)->write_p
= write_p
;
413 (*aref
)->prefetch_before
= PREFETCH_ALL
;
414 (*aref
)->prefetch_mod
= 1;
415 (*aref
)->reuse_distance
= 0;
416 (*aref
)->issue_prefetch_p
= false;
417 (*aref
)->group
= group
;
418 (*aref
)->next
= NULL
;
419 (*aref
)->independent_p
= false;
420 (*aref
)->storent_p
= false;
422 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
423 dump_mem_ref (dump_file
, *aref
);
426 /* Release memory references in GROUPS. */
429 release_mem_refs (struct mem_ref_group
*groups
)
431 struct mem_ref_group
*next_g
;
432 struct mem_ref
*ref
, *next_r
;
434 for (; groups
; groups
= next_g
)
436 next_g
= groups
->next
;
437 for (ref
= groups
->refs
; ref
; ref
= next_r
)
446 /* A structure used to pass arguments to idx_analyze_ref. */
450 struct loop
*loop
; /* Loop of the reference. */
451 gimple stmt
; /* Statement of the reference. */
452 tree
*step
; /* Step of the memory reference. */
453 HOST_WIDE_INT
*delta
; /* Offset of the memory reference. */
456 /* Analyzes a single INDEX of a memory reference to obtain information
457 described at analyze_ref. Callback for for_each_index. */
460 idx_analyze_ref (tree base
, tree
*index
, void *data
)
462 struct ar_data
*ar_data
= (struct ar_data
*) data
;
463 tree ibase
, step
, stepsize
;
464 HOST_WIDE_INT idelta
= 0, imult
= 1;
467 if (!simple_iv (ar_data
->loop
, loop_containing_stmt (ar_data
->stmt
),
473 if (TREE_CODE (ibase
) == POINTER_PLUS_EXPR
474 && cst_and_fits_in_hwi (TREE_OPERAND (ibase
, 1)))
476 idelta
= int_cst_value (TREE_OPERAND (ibase
, 1));
477 ibase
= TREE_OPERAND (ibase
, 0);
479 if (cst_and_fits_in_hwi (ibase
))
481 idelta
+= int_cst_value (ibase
);
482 ibase
= build_int_cst (TREE_TYPE (ibase
), 0);
485 if (TREE_CODE (base
) == ARRAY_REF
)
487 stepsize
= array_ref_element_size (base
);
488 if (!cst_and_fits_in_hwi (stepsize
))
490 imult
= int_cst_value (stepsize
);
491 step
= fold_build2 (MULT_EXPR
, sizetype
,
492 fold_convert (sizetype
, step
),
493 fold_convert (sizetype
, stepsize
));
497 if (*ar_data
->step
== NULL_TREE
)
498 *ar_data
->step
= step
;
500 *ar_data
->step
= fold_build2 (PLUS_EXPR
, sizetype
,
501 fold_convert (sizetype
, *ar_data
->step
),
502 fold_convert (sizetype
, step
));
503 *ar_data
->delta
+= idelta
;
509 /* Tries to express REF_P in shape &BASE + STEP * iter + DELTA, where DELTA and
510 STEP are integer constants and iter is number of iterations of LOOP. The
511 reference occurs in statement STMT. Strips nonaddressable component
512 references from REF_P. */
515 analyze_ref (struct loop
*loop
, tree
*ref_p
, tree
*base
,
516 tree
*step
, HOST_WIDE_INT
*delta
,
519 struct ar_data ar_data
;
521 HOST_WIDE_INT bit_offset
;
527 /* First strip off the component references. Ignore bitfields.
528 Also strip off the real and imagine parts of a complex, so that
529 they can have the same base. */
530 if (TREE_CODE (ref
) == REALPART_EXPR
531 || TREE_CODE (ref
) == IMAGPART_EXPR
532 || (TREE_CODE (ref
) == COMPONENT_REF
533 && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref
, 1))))
535 if (TREE_CODE (ref
) == IMAGPART_EXPR
)
536 *delta
+= int_size_in_bytes (TREE_TYPE (ref
));
537 ref
= TREE_OPERAND (ref
, 0);
542 for (; TREE_CODE (ref
) == COMPONENT_REF
; ref
= TREE_OPERAND (ref
, 0))
544 off
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
545 bit_offset
= TREE_INT_CST_LOW (off
);
546 gcc_assert (bit_offset
% BITS_PER_UNIT
== 0);
548 *delta
+= bit_offset
/ BITS_PER_UNIT
;
551 *base
= unshare_expr (ref
);
555 ar_data
.delta
= delta
;
556 return for_each_index (base
, idx_analyze_ref
, &ar_data
);
559 /* Record a memory reference REF to the list REFS. The reference occurs in
560 LOOP in statement STMT and it is write if WRITE_P. Returns true if the
561 reference was recorded, false otherwise. */
564 gather_memory_references_ref (struct loop
*loop
, struct mem_ref_group
**refs
,
565 tree ref
, bool write_p
, gimple stmt
)
569 struct mem_ref_group
*agrp
;
571 if (get_base_address (ref
) == NULL
)
574 if (!analyze_ref (loop
, &ref
, &base
, &step
, &delta
, stmt
))
576 /* If analyze_ref fails the default is a NULL_TREE. We can stop here. */
577 if (step
== NULL_TREE
)
580 /* Stop if the address of BASE could not be taken. */
581 if (may_be_nonaddressable_p (base
))
584 /* Limit non-constant step prefetching only to the innermost loops and
585 only when the step is loop invariant in the entire loop nest. */
586 if (!cst_and_fits_in_hwi (step
))
588 if (loop
->inner
!= NULL
)
590 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
592 fprintf (dump_file
, "Memory expression %p\n",(void *) ref
);
593 print_generic_expr (dump_file
, ref
, TDF_TREE
);
594 fprintf (dump_file
,":");
595 dump_mem_details (dump_file
, base
, step
, delta
, write_p
);
597 "Ignoring %p, non-constant step prefetching is "
598 "limited to inner most loops \n",
605 if (!expr_invariant_in_loop_p (loop_outermost (loop
), step
))
607 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
609 fprintf (dump_file
, "Memory expression %p\n",(void *) ref
);
610 print_generic_expr (dump_file
, ref
, TDF_TREE
);
611 fprintf (dump_file
,":");
612 dump_mem_details (dump_file
, base
, step
, delta
, write_p
);
614 "Not prefetching, ignoring %p due to "
615 "loop variant step\n",
623 /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
624 are integer constants. */
625 agrp
= find_or_create_group (refs
, base
, step
);
626 record_ref (agrp
, stmt
, ref
, delta
, write_p
);
631 /* Record the suitable memory references in LOOP. NO_OTHER_REFS is set to
632 true if there are no other memory references inside the loop. */
634 static struct mem_ref_group
*
635 gather_memory_references (struct loop
*loop
, bool *no_other_refs
, unsigned *ref_count
)
637 basic_block
*body
= get_loop_body_in_dom_order (loop
);
640 gimple_stmt_iterator bsi
;
643 struct mem_ref_group
*refs
= NULL
;
645 *no_other_refs
= true;
648 /* Scan the loop body in order, so that the former references precede the
650 for (i
= 0; i
< loop
->num_nodes
; i
++)
653 if (bb
->loop_father
!= loop
)
656 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
658 stmt
= gsi_stmt (bsi
);
660 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
662 if (gimple_vuse (stmt
)
663 || (is_gimple_call (stmt
)
664 && !(gimple_call_flags (stmt
) & ECF_CONST
)))
665 *no_other_refs
= false;
669 lhs
= gimple_assign_lhs (stmt
);
670 rhs
= gimple_assign_rhs1 (stmt
);
672 if (REFERENCE_CLASS_P (rhs
))
674 *no_other_refs
&= gather_memory_references_ref (loop
, &refs
,
678 if (REFERENCE_CLASS_P (lhs
))
680 *no_other_refs
&= gather_memory_references_ref (loop
, &refs
,
691 /* Prune the prefetch candidate REF using the self-reuse. */
694 prune_ref_by_self_reuse (struct mem_ref
*ref
)
699 /* If the step size is non constant, we cannot calculate prefetch_mod. */
700 if (!cst_and_fits_in_hwi (ref
->group
->step
))
703 step
= int_cst_value (ref
->group
->step
);
709 /* Prefetch references to invariant address just once. */
710 ref
->prefetch_before
= 1;
717 if (step
> PREFETCH_BLOCK
)
720 if ((backward
&& HAVE_BACKWARD_PREFETCH
)
721 || (!backward
&& HAVE_FORWARD_PREFETCH
))
723 ref
->prefetch_before
= 1;
727 ref
->prefetch_mod
= PREFETCH_BLOCK
/ step
;
730 /* Divides X by BY, rounding down. */
733 ddown (HOST_WIDE_INT x
, unsigned HOST_WIDE_INT by
)
740 return (x
+ by
- 1) / by
;
743 /* Given a CACHE_LINE_SIZE and two inductive memory references
744 with a common STEP greater than CACHE_LINE_SIZE and an address
745 difference DELTA, compute the probability that they will fall
746 in different cache lines. Return true if the computed miss rate
747 is not greater than the ACCEPTABLE_MISS_RATE. DISTINCT_ITERS is the
748 number of distinct iterations after which the pattern repeats itself.
749 ALIGN_UNIT is the unit of alignment in bytes. */
752 is_miss_rate_acceptable (unsigned HOST_WIDE_INT cache_line_size
,
753 HOST_WIDE_INT step
, HOST_WIDE_INT delta
,
754 unsigned HOST_WIDE_INT distinct_iters
,
757 unsigned align
, iter
;
758 int total_positions
, miss_positions
, max_allowed_miss_positions
;
759 int address1
, address2
, cache_line1
, cache_line2
;
761 /* It always misses if delta is greater than or equal to the cache
763 if (delta
>= (HOST_WIDE_INT
) cache_line_size
)
767 total_positions
= (cache_line_size
/ align_unit
) * distinct_iters
;
768 max_allowed_miss_positions
= (ACCEPTABLE_MISS_RATE
* total_positions
) / 1000;
770 /* Iterate through all possible alignments of the first
771 memory reference within its cache line. */
772 for (align
= 0; align
< cache_line_size
; align
+= align_unit
)
774 /* Iterate through all distinct iterations. */
775 for (iter
= 0; iter
< distinct_iters
; iter
++)
777 address1
= align
+ step
* iter
;
778 address2
= address1
+ delta
;
779 cache_line1
= address1
/ cache_line_size
;
780 cache_line2
= address2
/ cache_line_size
;
781 if (cache_line1
!= cache_line2
)
784 if (miss_positions
> max_allowed_miss_positions
)
791 /* Prune the prefetch candidate REF using the reuse with BY.
792 If BY_IS_BEFORE is true, BY is before REF in the loop. */
795 prune_ref_by_group_reuse (struct mem_ref
*ref
, struct mem_ref
*by
,
800 HOST_WIDE_INT delta_r
= ref
->delta
, delta_b
= by
->delta
;
801 HOST_WIDE_INT delta
= delta_b
- delta_r
;
802 HOST_WIDE_INT hit_from
;
803 unsigned HOST_WIDE_INT prefetch_before
, prefetch_block
;
804 HOST_WIDE_INT reduced_step
;
805 unsigned HOST_WIDE_INT reduced_prefetch_block
;
809 /* If the step is non constant we cannot calculate prefetch_before. */
810 if (!cst_and_fits_in_hwi (ref
->group
->step
)) {
814 step
= int_cst_value (ref
->group
->step
);
821 /* If the references has the same address, only prefetch the
824 ref
->prefetch_before
= 0;
831 /* If the reference addresses are invariant and fall into the
832 same cache line, prefetch just the first one. */
836 if (ddown (ref
->delta
, PREFETCH_BLOCK
)
837 != ddown (by
->delta
, PREFETCH_BLOCK
))
840 ref
->prefetch_before
= 0;
844 /* Only prune the reference that is behind in the array. */
850 /* Transform the data so that we may assume that the accesses
854 delta_r
= PREFETCH_BLOCK
- 1 - delta_r
;
855 delta_b
= PREFETCH_BLOCK
- 1 - delta_b
;
863 /* Check whether the two references are likely to hit the same cache
864 line, and how distant the iterations in that it occurs are from
867 if (step
<= PREFETCH_BLOCK
)
869 /* The accesses are sure to meet. Let us check when. */
870 hit_from
= ddown (delta_b
, PREFETCH_BLOCK
) * PREFETCH_BLOCK
;
871 prefetch_before
= (hit_from
- delta_r
+ step
- 1) / step
;
873 /* Do not reduce prefetch_before if we meet beyond cache size. */
874 if (prefetch_before
> absu_hwi (L2_CACHE_SIZE_BYTES
/ step
))
875 prefetch_before
= PREFETCH_ALL
;
876 if (prefetch_before
< ref
->prefetch_before
)
877 ref
->prefetch_before
= prefetch_before
;
882 /* A more complicated case with step > prefetch_block. First reduce
883 the ratio between the step and the cache line size to its simplest
884 terms. The resulting denominator will then represent the number of
885 distinct iterations after which each address will go back to its
886 initial location within the cache line. This computation assumes
887 that PREFETCH_BLOCK is a power of two. */
888 prefetch_block
= PREFETCH_BLOCK
;
889 reduced_prefetch_block
= prefetch_block
;
891 while ((reduced_step
& 1) == 0
892 && reduced_prefetch_block
> 1)
895 reduced_prefetch_block
>>= 1;
898 prefetch_before
= delta
/ step
;
900 ref_type
= TREE_TYPE (ref
->mem
);
901 align_unit
= TYPE_ALIGN (ref_type
) / 8;
902 if (is_miss_rate_acceptable (prefetch_block
, step
, delta
,
903 reduced_prefetch_block
, align_unit
))
905 /* Do not reduce prefetch_before if we meet beyond cache size. */
906 if (prefetch_before
> L2_CACHE_SIZE_BYTES
/ PREFETCH_BLOCK
)
907 prefetch_before
= PREFETCH_ALL
;
908 if (prefetch_before
< ref
->prefetch_before
)
909 ref
->prefetch_before
= prefetch_before
;
914 /* Try also the following iteration. */
916 delta
= step
- delta
;
917 if (is_miss_rate_acceptable (prefetch_block
, step
, delta
,
918 reduced_prefetch_block
, align_unit
))
920 if (prefetch_before
< ref
->prefetch_before
)
921 ref
->prefetch_before
= prefetch_before
;
926 /* The ref probably does not reuse by. */
930 /* Prune the prefetch candidate REF using the reuses with other references
934 prune_ref_by_reuse (struct mem_ref
*ref
, struct mem_ref
*refs
)
936 struct mem_ref
*prune_by
;
939 prune_ref_by_self_reuse (ref
);
941 for (prune_by
= refs
; prune_by
; prune_by
= prune_by
->next
)
949 if (!WRITE_CAN_USE_READ_PREFETCH
951 && !prune_by
->write_p
)
953 if (!READ_CAN_USE_WRITE_PREFETCH
955 && prune_by
->write_p
)
958 prune_ref_by_group_reuse (ref
, prune_by
, before
);
962 /* Prune the prefetch candidates in GROUP using the reuse analysis. */
965 prune_group_by_reuse (struct mem_ref_group
*group
)
967 struct mem_ref
*ref_pruned
;
969 for (ref_pruned
= group
->refs
; ref_pruned
; ref_pruned
= ref_pruned
->next
)
971 prune_ref_by_reuse (ref_pruned
, group
->refs
);
973 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
975 fprintf (dump_file
, "Reference %p:", (void *) ref_pruned
);
977 if (ref_pruned
->prefetch_before
== PREFETCH_ALL
978 && ref_pruned
->prefetch_mod
== 1)
979 fprintf (dump_file
, " no restrictions");
980 else if (ref_pruned
->prefetch_before
== 0)
981 fprintf (dump_file
, " do not prefetch");
982 else if (ref_pruned
->prefetch_before
<= ref_pruned
->prefetch_mod
)
983 fprintf (dump_file
, " prefetch once");
986 if (ref_pruned
->prefetch_before
!= PREFETCH_ALL
)
988 fprintf (dump_file
, " prefetch before ");
989 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
990 ref_pruned
->prefetch_before
);
992 if (ref_pruned
->prefetch_mod
!= 1)
994 fprintf (dump_file
, " prefetch mod ");
995 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
996 ref_pruned
->prefetch_mod
);
999 fprintf (dump_file
, "\n");
1004 /* Prune the list of prefetch candidates GROUPS using the reuse analysis. */
1007 prune_by_reuse (struct mem_ref_group
*groups
)
1009 for (; groups
; groups
= groups
->next
)
1010 prune_group_by_reuse (groups
);
1013 /* Returns true if we should issue prefetch for REF. */
1016 should_issue_prefetch_p (struct mem_ref
*ref
)
1018 /* For now do not issue prefetches for only first few of the
1020 if (ref
->prefetch_before
!= PREFETCH_ALL
)
1022 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1023 fprintf (dump_file
, "Ignoring %p due to prefetch_before\n",
1028 /* Do not prefetch nontemporal stores. */
1031 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1032 fprintf (dump_file
, "Ignoring nontemporal store %p\n", (void *) ref
);
1039 /* Decide which of the prefetch candidates in GROUPS to prefetch.
1040 AHEAD is the number of iterations to prefetch ahead (which corresponds
1041 to the number of simultaneous instances of one prefetch running at a
1042 time). UNROLL_FACTOR is the factor by that the loop is going to be
1043 unrolled. Returns true if there is anything to prefetch. */
1046 schedule_prefetches (struct mem_ref_group
*groups
, unsigned unroll_factor
,
1049 unsigned remaining_prefetch_slots
, n_prefetches
, prefetch_slots
;
1050 unsigned slots_per_prefetch
;
1051 struct mem_ref
*ref
;
1054 /* At most SIMULTANEOUS_PREFETCHES should be running at the same time. */
1055 remaining_prefetch_slots
= SIMULTANEOUS_PREFETCHES
;
1057 /* The prefetch will run for AHEAD iterations of the original loop, i.e.,
1058 AHEAD / UNROLL_FACTOR iterations of the unrolled loop. In each iteration,
1059 it will need a prefetch slot. */
1060 slots_per_prefetch
= (ahead
+ unroll_factor
/ 2) / unroll_factor
;
1061 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1062 fprintf (dump_file
, "Each prefetch instruction takes %u prefetch slots.\n",
1063 slots_per_prefetch
);
1065 /* For now we just take memory references one by one and issue
1066 prefetches for as many as possible. The groups are sorted
1067 starting with the largest step, since the references with
1068 large step are more likely to cause many cache misses. */
1070 for (; groups
; groups
= groups
->next
)
1071 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1073 if (!should_issue_prefetch_p (ref
))
1076 /* The loop is far from being sufficiently unrolled for this
1077 prefetch. Do not generate prefetch to avoid many redudant
1079 if (ref
->prefetch_mod
/ unroll_factor
> PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
)
1082 /* If we need to prefetch the reference each PREFETCH_MOD iterations,
1083 and we unroll the loop UNROLL_FACTOR times, we need to insert
1084 ceil (UNROLL_FACTOR / PREFETCH_MOD) instructions in each
1086 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1087 / ref
->prefetch_mod
);
1088 prefetch_slots
= n_prefetches
* slots_per_prefetch
;
1090 /* If more than half of the prefetches would be lost anyway, do not
1091 issue the prefetch. */
1092 if (2 * remaining_prefetch_slots
< prefetch_slots
)
1095 ref
->issue_prefetch_p
= true;
1097 if (remaining_prefetch_slots
<= prefetch_slots
)
1099 remaining_prefetch_slots
-= prefetch_slots
;
1106 /* Return TRUE if no prefetch is going to be generated in the given
1110 nothing_to_prefetch_p (struct mem_ref_group
*groups
)
1112 struct mem_ref
*ref
;
1114 for (; groups
; groups
= groups
->next
)
1115 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1116 if (should_issue_prefetch_p (ref
))
1122 /* Estimate the number of prefetches in the given GROUPS.
1123 UNROLL_FACTOR is the factor by which LOOP was unrolled. */
1126 estimate_prefetch_count (struct mem_ref_group
*groups
, unsigned unroll_factor
)
1128 struct mem_ref
*ref
;
1129 unsigned n_prefetches
;
1130 int prefetch_count
= 0;
1132 for (; groups
; groups
= groups
->next
)
1133 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1134 if (should_issue_prefetch_p (ref
))
1136 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1137 / ref
->prefetch_mod
);
1138 prefetch_count
+= n_prefetches
;
1141 return prefetch_count
;
1144 /* Issue prefetches for the reference REF into loop as decided before.
1145 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR
1146 is the factor by which LOOP was unrolled. */
1149 issue_prefetch_ref (struct mem_ref
*ref
, unsigned unroll_factor
, unsigned ahead
)
1151 HOST_WIDE_INT delta
;
1152 tree addr
, addr_base
, write_p
, local
, forward
;
1154 gimple_stmt_iterator bsi
;
1155 unsigned n_prefetches
, ap
;
1156 bool nontemporal
= ref
->reuse_distance
>= L2_CACHE_SIZE_BYTES
;
1158 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1159 fprintf (dump_file
, "Issued%s prefetch for %p.\n",
1160 nontemporal
? " nontemporal" : "",
1163 bsi
= gsi_for_stmt (ref
->stmt
);
1165 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1166 / ref
->prefetch_mod
);
1167 addr_base
= build_fold_addr_expr_with_type (ref
->mem
, ptr_type_node
);
1168 addr_base
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr_base
),
1169 true, NULL
, true, GSI_SAME_STMT
);
1170 write_p
= ref
->write_p
? integer_one_node
: integer_zero_node
;
1171 local
= nontemporal
? integer_zero_node
: integer_three_node
;
1173 for (ap
= 0; ap
< n_prefetches
; ap
++)
1175 if (cst_and_fits_in_hwi (ref
->group
->step
))
1177 /* Determine the address to prefetch. */
1178 delta
= (ahead
+ ap
* ref
->prefetch_mod
) *
1179 int_cst_value (ref
->group
->step
);
1180 addr
= fold_build_pointer_plus_hwi (addr_base
, delta
);
1181 addr
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr
), true, NULL
,
1182 true, GSI_SAME_STMT
);
1186 /* The step size is non-constant but loop-invariant. We use the
1187 heuristic to simply prefetch ahead iterations ahead. */
1188 forward
= fold_build2 (MULT_EXPR
, sizetype
,
1189 fold_convert (sizetype
, ref
->group
->step
),
1190 fold_convert (sizetype
, size_int (ahead
)));
1191 addr
= fold_build_pointer_plus (addr_base
, forward
);
1192 addr
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr
), true,
1193 NULL
, true, GSI_SAME_STMT
);
1195 /* Create the prefetch instruction. */
1196 prefetch
= gimple_build_call (builtin_decl_explicit (BUILT_IN_PREFETCH
),
1197 3, addr
, write_p
, local
);
1198 gsi_insert_before (&bsi
, prefetch
, GSI_SAME_STMT
);
1202 /* Issue prefetches for the references in GROUPS into loop as decided before.
1203 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR is the
1204 factor by that LOOP was unrolled. */
1207 issue_prefetches (struct mem_ref_group
*groups
,
1208 unsigned unroll_factor
, unsigned ahead
)
1210 struct mem_ref
*ref
;
1212 for (; groups
; groups
= groups
->next
)
1213 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1214 if (ref
->issue_prefetch_p
)
1215 issue_prefetch_ref (ref
, unroll_factor
, ahead
);
1218 /* Returns true if REF is a memory write for that a nontemporal store insn
1222 nontemporal_store_p (struct mem_ref
*ref
)
1225 enum insn_code code
;
1227 /* REF must be a write that is not reused. We require it to be independent
1228 on all other memory references in the loop, as the nontemporal stores may
1229 be reordered with respect to other memory references. */
1231 || !ref
->independent_p
1232 || ref
->reuse_distance
< L2_CACHE_SIZE_BYTES
)
1235 /* Check that we have the storent instruction for the mode. */
1236 mode
= TYPE_MODE (TREE_TYPE (ref
->mem
));
1237 if (mode
== BLKmode
)
1240 code
= optab_handler (storent_optab
, mode
);
1241 return code
!= CODE_FOR_nothing
;
1244 /* If REF is a nontemporal store, we mark the corresponding modify statement
1245 and return true. Otherwise, we return false. */
1248 mark_nontemporal_store (struct mem_ref
*ref
)
1250 if (!nontemporal_store_p (ref
))
1253 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1254 fprintf (dump_file
, "Marked reference %p as a nontemporal store.\n",
1257 gimple_assign_set_nontemporal_move (ref
->stmt
, true);
1258 ref
->storent_p
= true;
1263 /* Issue a memory fence instruction after LOOP. */
1266 emit_mfence_after_loop (struct loop
*loop
)
1268 vec
<edge
> exits
= get_loop_exit_edges (loop
);
1271 gimple_stmt_iterator bsi
;
1274 FOR_EACH_VEC_ELT (exits
, i
, exit
)
1276 call
= gimple_build_call (FENCE_FOLLOWING_MOVNT
, 0);
1278 if (!single_pred_p (exit
->dest
)
1279 /* If possible, we prefer not to insert the fence on other paths
1281 && !(exit
->flags
& EDGE_ABNORMAL
))
1282 split_loop_exit_edge (exit
);
1283 bsi
= gsi_after_labels (exit
->dest
);
1285 gsi_insert_before (&bsi
, call
, GSI_NEW_STMT
);
1289 update_ssa (TODO_update_ssa_only_virtuals
);
1292 /* Returns true if we can use storent in loop, false otherwise. */
1295 may_use_storent_in_loop_p (struct loop
*loop
)
1299 if (loop
->inner
!= NULL
)
1302 /* If we must issue a mfence insn after using storent, check that there
1303 is a suitable place for it at each of the loop exits. */
1304 if (FENCE_FOLLOWING_MOVNT
!= NULL_TREE
)
1306 vec
<edge
> exits
= get_loop_exit_edges (loop
);
1310 FOR_EACH_VEC_ELT (exits
, i
, exit
)
1311 if ((exit
->flags
& EDGE_ABNORMAL
)
1312 && exit
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1321 /* Marks nontemporal stores in LOOP. GROUPS contains the description of memory
1322 references in the loop. */
1325 mark_nontemporal_stores (struct loop
*loop
, struct mem_ref_group
*groups
)
1327 struct mem_ref
*ref
;
1330 if (!may_use_storent_in_loop_p (loop
))
1333 for (; groups
; groups
= groups
->next
)
1334 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1335 any
|= mark_nontemporal_store (ref
);
1337 if (any
&& FENCE_FOLLOWING_MOVNT
!= NULL_TREE
)
1338 emit_mfence_after_loop (loop
);
1341 /* Determines whether we can profitably unroll LOOP FACTOR times, and if
1342 this is the case, fill in DESC by the description of number of
1346 should_unroll_loop_p (struct loop
*loop
, struct tree_niter_desc
*desc
,
1349 if (!can_unroll_loop_p (loop
, factor
, desc
))
1352 /* We only consider loops without control flow for unrolling. This is not
1353 a hard restriction -- tree_unroll_loop works with arbitrary loops
1354 as well; but the unrolling/prefetching is usually more profitable for
1355 loops consisting of a single basic block, and we want to limit the
1357 if (loop
->num_nodes
> 2)
1363 /* Determine the coefficient by that unroll LOOP, from the information
1364 contained in the list of memory references REFS. Description of
1365 umber of iterations of LOOP is stored to DESC. NINSNS is the number of
1366 insns of the LOOP. EST_NITER is the estimated number of iterations of
1367 the loop, or -1 if no estimate is available. */
1370 determine_unroll_factor (struct loop
*loop
, struct mem_ref_group
*refs
,
1371 unsigned ninsns
, struct tree_niter_desc
*desc
,
1372 HOST_WIDE_INT est_niter
)
1374 unsigned upper_bound
;
1375 unsigned nfactor
, factor
, mod_constraint
;
1376 struct mem_ref_group
*agp
;
1377 struct mem_ref
*ref
;
1379 /* First check whether the loop is not too large to unroll. We ignore
1380 PARAM_MAX_UNROLL_TIMES, because for small loops, it prevented us
1381 from unrolling them enough to make exactly one cache line covered by each
1382 iteration. Also, the goal of PARAM_MAX_UNROLL_TIMES is to prevent
1383 us from unrolling the loops too many times in cases where we only expect
1384 gains from better scheduling and decreasing loop overhead, which is not
1386 upper_bound
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / ninsns
;
1388 /* If we unrolled the loop more times than it iterates, the unrolled version
1389 of the loop would be never entered. */
1390 if (est_niter
>= 0 && est_niter
< (HOST_WIDE_INT
) upper_bound
)
1391 upper_bound
= est_niter
;
1393 if (upper_bound
<= 1)
1396 /* Choose the factor so that we may prefetch each cache just once,
1397 but bound the unrolling by UPPER_BOUND. */
1399 for (agp
= refs
; agp
; agp
= agp
->next
)
1400 for (ref
= agp
->refs
; ref
; ref
= ref
->next
)
1401 if (should_issue_prefetch_p (ref
))
1403 mod_constraint
= ref
->prefetch_mod
;
1404 nfactor
= least_common_multiple (mod_constraint
, factor
);
1405 if (nfactor
<= upper_bound
)
1409 if (!should_unroll_loop_p (loop
, desc
, factor
))
1415 /* Returns the total volume of the memory references REFS, taking into account
1416 reuses in the innermost loop and cache line size. TODO -- we should also
1417 take into account reuses across the iterations of the loops in the loop
1421 volume_of_references (struct mem_ref_group
*refs
)
1423 unsigned volume
= 0;
1424 struct mem_ref_group
*gr
;
1425 struct mem_ref
*ref
;
1427 for (gr
= refs
; gr
; gr
= gr
->next
)
1428 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1430 /* Almost always reuses another value? */
1431 if (ref
->prefetch_before
!= PREFETCH_ALL
)
1434 /* If several iterations access the same cache line, use the size of
1435 the line divided by this number. Otherwise, a cache line is
1436 accessed in each iteration. TODO -- in the latter case, we should
1437 take the size of the reference into account, rounding it up on cache
1438 line size multiple. */
1439 volume
+= L1_CACHE_LINE_SIZE
/ ref
->prefetch_mod
;
1444 /* Returns the volume of memory references accessed across VEC iterations of
1445 loops, whose sizes are described in the LOOP_SIZES array. N is the number
1446 of the loops in the nest (length of VEC and LOOP_SIZES vectors). */
1449 volume_of_dist_vector (lambda_vector vec
, unsigned *loop_sizes
, unsigned n
)
1453 for (i
= 0; i
< n
; i
++)
1460 gcc_assert (vec
[i
] > 0);
1462 /* We ignore the parts of the distance vector in subloops, since usually
1463 the numbers of iterations are much smaller. */
1464 return loop_sizes
[i
] * vec
[i
];
1467 /* Add the steps of ACCESS_FN multiplied by STRIDE to the array STRIDE
1468 at the position corresponding to the loop of the step. N is the depth
1469 of the considered loop nest, and, LOOP is its innermost loop. */
1472 add_subscript_strides (tree access_fn
, unsigned stride
,
1473 HOST_WIDE_INT
*strides
, unsigned n
, struct loop
*loop
)
1477 HOST_WIDE_INT astep
;
1478 unsigned min_depth
= loop_depth (loop
) - n
;
1480 while (TREE_CODE (access_fn
) == POLYNOMIAL_CHREC
)
1482 aloop
= get_chrec_loop (access_fn
);
1483 step
= CHREC_RIGHT (access_fn
);
1484 access_fn
= CHREC_LEFT (access_fn
);
1486 if ((unsigned) loop_depth (aloop
) <= min_depth
)
1489 if (tree_fits_shwi_p (step
))
1490 astep
= tree_to_shwi (step
);
1492 astep
= L1_CACHE_LINE_SIZE
;
1494 strides
[n
- 1 - loop_depth (loop
) + loop_depth (aloop
)] += astep
* stride
;
1499 /* Returns the volume of memory references accessed between two consecutive
1500 self-reuses of the reference DR. We consider the subscripts of DR in N
1501 loops, and LOOP_SIZES contains the volumes of accesses in each of the
1502 loops. LOOP is the innermost loop of the current loop nest. */
1505 self_reuse_distance (data_reference_p dr
, unsigned *loop_sizes
, unsigned n
,
1508 tree stride
, access_fn
;
1509 HOST_WIDE_INT
*strides
, astride
;
1510 vec
<tree
> access_fns
;
1511 tree ref
= DR_REF (dr
);
1512 unsigned i
, ret
= ~0u;
1514 /* In the following example:
1516 for (i = 0; i < N; i++)
1517 for (j = 0; j < N; j++)
1519 the same cache line is accessed each N steps (except if the change from
1520 i to i + 1 crosses the boundary of the cache line). Thus, for self-reuse,
1521 we cannot rely purely on the results of the data dependence analysis.
1523 Instead, we compute the stride of the reference in each loop, and consider
1524 the innermost loop in that the stride is less than cache size. */
1526 strides
= XCNEWVEC (HOST_WIDE_INT
, n
);
1527 access_fns
= DR_ACCESS_FNS (dr
);
1529 FOR_EACH_VEC_ELT (access_fns
, i
, access_fn
)
1531 /* Keep track of the reference corresponding to the subscript, so that we
1533 while (handled_component_p (ref
) && TREE_CODE (ref
) != ARRAY_REF
)
1534 ref
= TREE_OPERAND (ref
, 0);
1536 if (TREE_CODE (ref
) == ARRAY_REF
)
1538 stride
= TYPE_SIZE_UNIT (TREE_TYPE (ref
));
1539 if (tree_fits_uhwi_p (stride
))
1540 astride
= tree_to_uhwi (stride
);
1542 astride
= L1_CACHE_LINE_SIZE
;
1544 ref
= TREE_OPERAND (ref
, 0);
1549 add_subscript_strides (access_fn
, astride
, strides
, n
, loop
);
1552 for (i
= n
; i
-- > 0; )
1554 unsigned HOST_WIDE_INT s
;
1556 s
= strides
[i
] < 0 ? -strides
[i
] : strides
[i
];
1558 if (s
< (unsigned) L1_CACHE_LINE_SIZE
1560 > (unsigned) (L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)))
1562 ret
= loop_sizes
[i
];
1571 /* Determines the distance till the first reuse of each reference in REFS
1572 in the loop nest of LOOP. NO_OTHER_REFS is true if there are no other
1573 memory references in the loop. Return false if the analysis fails. */
1576 determine_loop_nest_reuse (struct loop
*loop
, struct mem_ref_group
*refs
,
1579 struct loop
*nest
, *aloop
;
1580 vec
<data_reference_p
> datarefs
= vNULL
;
1581 vec
<ddr_p
> dependences
= vNULL
;
1582 struct mem_ref_group
*gr
;
1583 struct mem_ref
*ref
, *refb
;
1584 vec
<loop_p
> vloops
= vNULL
;
1585 unsigned *loop_data_size
;
1587 unsigned volume
, dist
, adist
;
1589 data_reference_p dr
;
1595 /* Find the outermost loop of the loop nest of loop (we require that
1596 there are no sibling loops inside the nest). */
1600 aloop
= loop_outer (nest
);
1602 if (aloop
== current_loops
->tree_root
1603 || aloop
->inner
->next
)
1609 /* For each loop, determine the amount of data accessed in each iteration.
1610 We use this to estimate whether the reference is evicted from the
1611 cache before its reuse. */
1612 find_loop_nest (nest
, &vloops
);
1613 n
= vloops
.length ();
1614 loop_data_size
= XNEWVEC (unsigned, n
);
1615 volume
= volume_of_references (refs
);
1619 loop_data_size
[i
] = volume
;
1620 /* Bound the volume by the L2 cache size, since above this bound,
1621 all dependence distances are equivalent. */
1622 if (volume
> L2_CACHE_SIZE_BYTES
)
1626 vol
= estimated_stmt_executions_int (aloop
);
1628 vol
= expected_loop_iterations (aloop
);
1632 /* Prepare the references in the form suitable for data dependence
1633 analysis. We ignore unanalyzable data references (the results
1634 are used just as a heuristics to estimate temporality of the
1635 references, hence we do not need to worry about correctness). */
1636 for (gr
= refs
; gr
; gr
= gr
->next
)
1637 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1639 dr
= create_data_ref (nest
, loop_containing_stmt (ref
->stmt
),
1640 ref
->mem
, ref
->stmt
, !ref
->write_p
);
1644 ref
->reuse_distance
= volume
;
1646 datarefs
.safe_push (dr
);
1649 no_other_refs
= false;
1652 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
1654 dist
= self_reuse_distance (dr
, loop_data_size
, n
, loop
);
1655 ref
= (struct mem_ref
*) dr
->aux
;
1656 if (ref
->reuse_distance
> dist
)
1657 ref
->reuse_distance
= dist
;
1660 ref
->independent_p
= true;
1663 if (!compute_all_dependences (datarefs
, &dependences
, vloops
, true))
1666 FOR_EACH_VEC_ELT (dependences
, i
, dep
)
1668 if (DDR_ARE_DEPENDENT (dep
) == chrec_known
)
1671 ref
= (struct mem_ref
*) DDR_A (dep
)->aux
;
1672 refb
= (struct mem_ref
*) DDR_B (dep
)->aux
;
1674 if (DDR_ARE_DEPENDENT (dep
) == chrec_dont_know
1675 || DDR_NUM_DIST_VECTS (dep
) == 0)
1677 /* If the dependence cannot be analyzed, assume that there might be
1681 ref
->independent_p
= false;
1682 refb
->independent_p
= false;
1686 /* The distance vectors are normalized to be always lexicographically
1687 positive, hence we cannot tell just from them whether DDR_A comes
1688 before DDR_B or vice versa. However, it is not important,
1689 anyway -- if DDR_A is close to DDR_B, then it is either reused in
1690 DDR_B (and it is not nontemporal), or it reuses the value of DDR_B
1691 in cache (and marking it as nontemporal would not affect
1695 for (j
= 0; j
< DDR_NUM_DIST_VECTS (dep
); j
++)
1697 adist
= volume_of_dist_vector (DDR_DIST_VECT (dep
, j
),
1700 /* If this is a dependence in the innermost loop (i.e., the
1701 distances in all superloops are zero) and it is not
1702 the trivial self-dependence with distance zero, record that
1703 the references are not completely independent. */
1704 if (lambda_vector_zerop (DDR_DIST_VECT (dep
, j
), n
- 1)
1706 || DDR_DIST_VECT (dep
, j
)[n
-1] != 0))
1708 ref
->independent_p
= false;
1709 refb
->independent_p
= false;
1712 /* Ignore accesses closer than
1713 L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
1714 so that we use nontemporal prefetches e.g. if single memory
1715 location is accessed several times in a single iteration of
1717 if (adist
< L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)
1725 if (ref
->reuse_distance
> dist
)
1726 ref
->reuse_distance
= dist
;
1727 if (refb
->reuse_distance
> dist
)
1728 refb
->reuse_distance
= dist
;
1731 free_dependence_relations (dependences
);
1732 free_data_refs (datarefs
);
1733 free (loop_data_size
);
1735 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1737 fprintf (dump_file
, "Reuse distances:\n");
1738 for (gr
= refs
; gr
; gr
= gr
->next
)
1739 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1740 fprintf (dump_file
, " ref %p distance %u\n",
1741 (void *) ref
, ref
->reuse_distance
);
1747 /* Determine whether or not the trip count to ahead ratio is too small based
1748 on prefitablility consideration.
1749 AHEAD: the iteration ahead distance,
1750 EST_NITER: the estimated trip count. */
1753 trip_count_to_ahead_ratio_too_small_p (unsigned ahead
, HOST_WIDE_INT est_niter
)
1755 /* Assume trip count to ahead ratio is big enough if the trip count could not
1756 be estimated at compile time. */
1760 if (est_niter
< (HOST_WIDE_INT
) (TRIP_COUNT_TO_AHEAD_RATIO
* ahead
))
1762 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1764 "Not prefetching -- loop estimated to roll only %d times\n",
1772 /* Determine whether or not the number of memory references in the loop is
1773 reasonable based on the profitablity and compilation time considerations.
1774 NINSNS: estimated number of instructions in the loop,
1775 MEM_REF_COUNT: total number of memory references in the loop. */
1778 mem_ref_count_reasonable_p (unsigned ninsns
, unsigned mem_ref_count
)
1780 int insn_to_mem_ratio
;
1782 if (mem_ref_count
== 0)
1785 /* Miss rate computation (is_miss_rate_acceptable) and dependence analysis
1786 (compute_all_dependences) have high costs based on quadratic complexity.
1787 To avoid huge compilation time, we give up prefetching if mem_ref_count
1789 if (mem_ref_count
> PREFETCH_MAX_MEM_REFS_PER_LOOP
)
1792 /* Prefetching improves performance by overlapping cache missing
1793 memory accesses with CPU operations. If the loop does not have
1794 enough CPU operations to overlap with memory operations, prefetching
1795 won't give a significant benefit. One approximate way of checking
1796 this is to require the ratio of instructions to memory references to
1797 be above a certain limit. This approximation works well in practice.
1798 TODO: Implement a more precise computation by estimating the time
1799 for each CPU or memory op in the loop. Time estimates for memory ops
1800 should account for cache misses. */
1801 insn_to_mem_ratio
= ninsns
/ mem_ref_count
;
1803 if (insn_to_mem_ratio
< PREFETCH_MIN_INSN_TO_MEM_RATIO
)
1805 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1807 "Not prefetching -- instruction to memory reference ratio (%d) too small\n",
1815 /* Determine whether or not the instruction to prefetch ratio in the loop is
1816 too small based on the profitablity consideration.
1817 NINSNS: estimated number of instructions in the loop,
1818 PREFETCH_COUNT: an estimate of the number of prefetches,
1819 UNROLL_FACTOR: the factor to unroll the loop if prefetching. */
1822 insn_to_prefetch_ratio_too_small_p (unsigned ninsns
, unsigned prefetch_count
,
1823 unsigned unroll_factor
)
1825 int insn_to_prefetch_ratio
;
1827 /* Prefetching most likely causes performance degradation when the instruction
1828 to prefetch ratio is too small. Too many prefetch instructions in a loop
1829 may reduce the I-cache performance.
1830 (unroll_factor * ninsns) is used to estimate the number of instructions in
1831 the unrolled loop. This implementation is a bit simplistic -- the number
1832 of issued prefetch instructions is also affected by unrolling. So,
1833 prefetch_mod and the unroll factor should be taken into account when
1834 determining prefetch_count. Also, the number of insns of the unrolled
1835 loop will usually be significantly smaller than the number of insns of the
1836 original loop * unroll_factor (at least the induction variable increases
1837 and the exit branches will get eliminated), so it might be better to use
1838 tree_estimate_loop_size + estimated_unrolled_size. */
1839 insn_to_prefetch_ratio
= (unroll_factor
* ninsns
) / prefetch_count
;
1840 if (insn_to_prefetch_ratio
< MIN_INSN_TO_PREFETCH_RATIO
)
1842 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1844 "Not prefetching -- instruction to prefetch ratio (%d) too small\n",
1845 insn_to_prefetch_ratio
);
1853 /* Issue prefetch instructions for array references in LOOP. Returns
1854 true if the LOOP was unrolled. */
1857 loop_prefetch_arrays (struct loop
*loop
)
1859 struct mem_ref_group
*refs
;
1860 unsigned ahead
, ninsns
, time
, unroll_factor
;
1861 HOST_WIDE_INT est_niter
;
1862 struct tree_niter_desc desc
;
1863 bool unrolled
= false, no_other_refs
;
1864 unsigned prefetch_count
;
1865 unsigned mem_ref_count
;
1867 if (optimize_loop_nest_for_size_p (loop
))
1869 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1870 fprintf (dump_file
, " ignored (cold area)\n");
1874 /* FIXME: the time should be weighted by the probabilities of the blocks in
1876 time
= tree_num_loop_insns (loop
, &eni_time_weights
);
1880 ahead
= (PREFETCH_LATENCY
+ time
- 1) / time
;
1881 est_niter
= estimated_stmt_executions_int (loop
);
1882 if (est_niter
== -1)
1883 est_niter
= max_stmt_executions_int (loop
);
1885 /* Prefetching is not likely to be profitable if the trip count to ahead
1886 ratio is too small. */
1887 if (trip_count_to_ahead_ratio_too_small_p (ahead
, est_niter
))
1890 ninsns
= tree_num_loop_insns (loop
, &eni_size_weights
);
1892 /* Step 1: gather the memory references. */
1893 refs
= gather_memory_references (loop
, &no_other_refs
, &mem_ref_count
);
1895 /* Give up prefetching if the number of memory references in the
1896 loop is not reasonable based on profitablity and compilation time
1898 if (!mem_ref_count_reasonable_p (ninsns
, mem_ref_count
))
1901 /* Step 2: estimate the reuse effects. */
1902 prune_by_reuse (refs
);
1904 if (nothing_to_prefetch_p (refs
))
1907 if (!determine_loop_nest_reuse (loop
, refs
, no_other_refs
))
1910 /* Step 3: determine unroll factor. */
1911 unroll_factor
= determine_unroll_factor (loop
, refs
, ninsns
, &desc
,
1914 /* Estimate prefetch count for the unrolled loop. */
1915 prefetch_count
= estimate_prefetch_count (refs
, unroll_factor
);
1916 if (prefetch_count
== 0)
1919 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1920 fprintf (dump_file
, "Ahead %d, unroll factor %d, trip count "
1921 HOST_WIDE_INT_PRINT_DEC
"\n"
1922 "insn count %d, mem ref count %d, prefetch count %d\n",
1923 ahead
, unroll_factor
, est_niter
,
1924 ninsns
, mem_ref_count
, prefetch_count
);
1926 /* Prefetching is not likely to be profitable if the instruction to prefetch
1927 ratio is too small. */
1928 if (insn_to_prefetch_ratio_too_small_p (ninsns
, prefetch_count
,
1932 mark_nontemporal_stores (loop
, refs
);
1934 /* Step 4: what to prefetch? */
1935 if (!schedule_prefetches (refs
, unroll_factor
, ahead
))
1938 /* Step 5: unroll the loop. TODO -- peeling of first and last few
1939 iterations so that we do not issue superfluous prefetches. */
1940 if (unroll_factor
!= 1)
1942 tree_unroll_loop (loop
, unroll_factor
,
1943 single_dom_exit (loop
), &desc
);
1947 /* Step 6: issue the prefetches. */
1948 issue_prefetches (refs
, unroll_factor
, ahead
);
1951 release_mem_refs (refs
);
1955 /* Issue prefetch instructions for array references in loops. */
1958 tree_ssa_prefetch_arrays (void)
1961 bool unrolled
= false;
1965 /* It is possible to ask compiler for say -mtune=i486 -march=pentium4.
1966 -mtune=i486 causes us having PREFETCH_BLOCK 0, since this is part
1967 of processor costs and i486 does not have prefetch, but
1968 -march=pentium4 causes HAVE_prefetch to be true. Ugh. */
1969 || PREFETCH_BLOCK
== 0)
1972 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1974 fprintf (dump_file
, "Prefetching parameters:\n");
1975 fprintf (dump_file
, " simultaneous prefetches: %d\n",
1976 SIMULTANEOUS_PREFETCHES
);
1977 fprintf (dump_file
, " prefetch latency: %d\n", PREFETCH_LATENCY
);
1978 fprintf (dump_file
, " prefetch block size: %d\n", PREFETCH_BLOCK
);
1979 fprintf (dump_file
, " L1 cache size: %d lines, %d kB\n",
1980 L1_CACHE_SIZE_BYTES
/ L1_CACHE_LINE_SIZE
, L1_CACHE_SIZE
);
1981 fprintf (dump_file
, " L1 cache line size: %d\n", L1_CACHE_LINE_SIZE
);
1982 fprintf (dump_file
, " L2 cache size: %d kB\n", L2_CACHE_SIZE
);
1983 fprintf (dump_file
, " min insn-to-prefetch ratio: %d \n",
1984 MIN_INSN_TO_PREFETCH_RATIO
);
1985 fprintf (dump_file
, " min insn-to-mem ratio: %d \n",
1986 PREFETCH_MIN_INSN_TO_MEM_RATIO
);
1987 fprintf (dump_file
, "\n");
1990 initialize_original_copy_tables ();
1992 if (!builtin_decl_explicit_p (BUILT_IN_PREFETCH
))
1994 tree type
= build_function_type_list (void_type_node
,
1995 const_ptr_type_node
, NULL_TREE
);
1996 tree decl
= add_builtin_function ("__builtin_prefetch", type
,
1997 BUILT_IN_PREFETCH
, BUILT_IN_NORMAL
,
1999 DECL_IS_NOVOPS (decl
) = true;
2000 set_builtin_decl (BUILT_IN_PREFETCH
, decl
, false);
2003 /* We assume that size of cache line is a power of two, so verify this
2005 gcc_assert ((PREFETCH_BLOCK
& (PREFETCH_BLOCK
- 1)) == 0);
2007 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
2009 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2010 fprintf (dump_file
, "Processing loop %d:\n", loop
->num
);
2012 unrolled
|= loop_prefetch_arrays (loop
);
2014 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2015 fprintf (dump_file
, "\n\n");
2021 todo_flags
|= TODO_cleanup_cfg
;
2024 free_original_copy_tables ();
2032 const pass_data pass_data_loop_prefetch
=
2034 GIMPLE_PASS
, /* type */
2035 "aprefetch", /* name */
2036 OPTGROUP_LOOP
, /* optinfo_flags */
2037 TV_TREE_PREFETCH
, /* tv_id */
2038 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2039 0, /* properties_provided */
2040 0, /* properties_destroyed */
2041 0, /* todo_flags_start */
2042 0, /* todo_flags_finish */
2045 class pass_loop_prefetch
: public gimple_opt_pass
2048 pass_loop_prefetch (gcc::context
*ctxt
)
2049 : gimple_opt_pass (pass_data_loop_prefetch
, ctxt
)
2052 /* opt_pass methods: */
2053 virtual bool gate (function
*) { return flag_prefetch_loop_arrays
> 0; }
2054 virtual unsigned int execute (function
*);
2056 }; // class pass_loop_prefetch
2059 pass_loop_prefetch::execute (function
*fun
)
2061 if (number_of_loops (fun
) <= 1)
2064 return tree_ssa_prefetch_arrays ();
2070 make_pass_loop_prefetch (gcc::context
*ctxt
)
2072 return new pass_loop_prefetch (ctxt
);