2 Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "basic-block.h"
28 #include "tree-pretty-print.h"
29 #include "tree-flow.h"
30 #include "tree-dump.h"
33 #include "tree-pass.h"
34 #include "insn-config.h"
36 #include "tree-chrec.h"
37 #include "tree-scalar-evolution.h"
38 #include "diagnostic-core.h"
40 #include "langhooks.h"
41 #include "tree-inline.h"
42 #include "tree-data-ref.h"
45 /* FIXME: Needed for optabs, but this should all be moved to a TBD interface
46 between the GIMPLE and RTL worlds. */
51 /* This pass inserts prefetch instructions to optimize cache usage during
52 accesses to arrays in loops. It processes loops sequentially and:
54 1) Gathers all memory references in the single loop.
55 2) For each of the references it decides when it is profitable to prefetch
56 it. To do it, we evaluate the reuse among the accesses, and determines
57 two values: PREFETCH_BEFORE (meaning that it only makes sense to do
58 prefetching in the first PREFETCH_BEFORE iterations of the loop) and
59 PREFETCH_MOD (meaning that it only makes sense to prefetch in the
60 iterations of the loop that are zero modulo PREFETCH_MOD). For example
61 (assuming cache line size is 64 bytes, char has size 1 byte and there
62 is no hardware sequential prefetch):
65 for (i = 0; i < max; i++)
72 a[187*i + 50] = ...; (5)
75 (0) obviously has PREFETCH_BEFORE 1
76 (1) has PREFETCH_BEFORE 64, since (2) accesses the same memory
77 location 64 iterations before it, and PREFETCH_MOD 64 (since
78 it hits the same cache line otherwise).
79 (2) has PREFETCH_MOD 64
80 (3) has PREFETCH_MOD 4
81 (4) has PREFETCH_MOD 1. We do not set PREFETCH_BEFORE here, since
82 the cache line accessed by (5) is the same with probability only
84 (5) has PREFETCH_MOD 1 as well.
86 Additionally, we use data dependence analysis to determine for each
87 reference the distance till the first reuse; this information is used
88 to determine the temporality of the issued prefetch instruction.
90 3) We determine how much ahead we need to prefetch. The number of
91 iterations needed is time to fetch / time spent in one iteration of
92 the loop. The problem is that we do not know either of these values,
93 so we just make a heuristic guess based on a magic (possibly)
94 target-specific constant and size of the loop.
96 4) Determine which of the references we prefetch. We take into account
97 that there is a maximum number of simultaneous prefetches (provided
98 by machine description). We prefetch as many prefetches as possible
99 while still within this bound (starting with those with lowest
100 prefetch_mod, since they are responsible for most of the cache
103 5) We unroll and peel loops so that we are able to satisfy PREFETCH_MOD
104 and PREFETCH_BEFORE requirements (within some bounds), and to avoid
105 prefetching nonaccessed memory.
106 TODO -- actually implement peeling.
108 6) We actually emit the prefetch instructions. ??? Perhaps emit the
109 prefetch instructions with guards in cases where 5) was not sufficient
110 to satisfy the constraints?
112 A cost model is implemented to determine whether or not prefetching is
113 profitable for a given loop. The cost model has three heuristics:
115 1. Function trip_count_to_ahead_ratio_too_small_p implements a
116 heuristic that determines whether or not the loop has too few
117 iterations (compared to ahead). Prefetching is not likely to be
118 beneficial if the trip count to ahead ratio is below a certain
121 2. Function mem_ref_count_reasonable_p implements a heuristic that
122 determines whether the given loop has enough CPU ops that can be
123 overlapped with cache missing memory ops. If not, the loop
124 won't benefit from prefetching. In the implementation,
125 prefetching is not considered beneficial if the ratio between
126 the instruction count and the mem ref count is below a certain
129 3. Function insn_to_prefetch_ratio_too_small_p implements a
130 heuristic that disables prefetching in a loop if the prefetching
131 cost is above a certain limit. The relative prefetching cost is
132 estimated by taking the ratio between the prefetch count and the
133 total intruction count (this models the I-cache cost).
135 The limits used in these heuristics are defined as parameters with
136 reasonable default values. Machine-specific default values will be
140 -- write and use more general reuse analysis (that could be also used
141 in other cache aimed loop optimizations)
142 -- make it behave sanely together with the prefetches given by user
143 (now we just ignore them; at the very least we should avoid
144 optimizing loops in that user put his own prefetches)
145 -- we assume cache line size alignment of arrays; this could be
148 /* Magic constants follow. These should be replaced by machine specific
151 /* True if write can be prefetched by a read prefetch. */
153 #ifndef WRITE_CAN_USE_READ_PREFETCH
154 #define WRITE_CAN_USE_READ_PREFETCH 1
157 /* True if read can be prefetched by a write prefetch. */
159 #ifndef READ_CAN_USE_WRITE_PREFETCH
160 #define READ_CAN_USE_WRITE_PREFETCH 0
163 /* The size of the block loaded by a single prefetch. Usually, this is
164 the same as cache line size (at the moment, we only consider one level
165 of cache hierarchy). */
167 #ifndef PREFETCH_BLOCK
168 #define PREFETCH_BLOCK L1_CACHE_LINE_SIZE
171 /* Do we have a forward hardware sequential prefetching? */
173 #ifndef HAVE_FORWARD_PREFETCH
174 #define HAVE_FORWARD_PREFETCH 0
177 /* Do we have a backward hardware sequential prefetching? */
179 #ifndef HAVE_BACKWARD_PREFETCH
180 #define HAVE_BACKWARD_PREFETCH 0
183 /* In some cases we are only able to determine that there is a certain
184 probability that the two accesses hit the same cache line. In this
185 case, we issue the prefetches for both of them if this probability
186 is less then (1000 - ACCEPTABLE_MISS_RATE) per thousand. */
188 #ifndef ACCEPTABLE_MISS_RATE
189 #define ACCEPTABLE_MISS_RATE 50
192 #ifndef HAVE_prefetch
193 #define HAVE_prefetch 0
196 #define L1_CACHE_SIZE_BYTES ((unsigned) (L1_CACHE_SIZE * 1024))
197 #define L2_CACHE_SIZE_BYTES ((unsigned) (L2_CACHE_SIZE * 1024))
199 /* We consider a memory access nontemporal if it is not reused sooner than
200 after L2_CACHE_SIZE_BYTES of memory are accessed. However, we ignore
201 accesses closer than L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
202 so that we use nontemporal prefetches e.g. if single memory location
203 is accessed several times in a single iteration of the loop. */
204 #define NONTEMPORAL_FRACTION 16
206 /* In case we have to emit a memory fence instruction after the loop that
207 uses nontemporal stores, this defines the builtin to use. */
209 #ifndef FENCE_FOLLOWING_MOVNT
210 #define FENCE_FOLLOWING_MOVNT NULL_TREE
213 /* It is not profitable to prefetch when the trip count is not at
214 least TRIP_COUNT_TO_AHEAD_RATIO times the prefetch ahead distance.
215 For example, in a loop with a prefetch ahead distance of 10,
216 supposing that TRIP_COUNT_TO_AHEAD_RATIO is equal to 4, it is
217 profitable to prefetch when the trip count is greater or equal to
218 40. In that case, 30 out of the 40 iterations will benefit from
221 #ifndef TRIP_COUNT_TO_AHEAD_RATIO
222 #define TRIP_COUNT_TO_AHEAD_RATIO 4
225 /* The group of references between that reuse may occur. */
229 tree base
; /* Base of the reference. */
230 tree step
; /* Step of the reference. */
231 struct mem_ref
*refs
; /* References in the group. */
232 struct mem_ref_group
*next
; /* Next group of references. */
235 /* Assigned to PREFETCH_BEFORE when all iterations are to be prefetched. */
237 #define PREFETCH_ALL (~(unsigned HOST_WIDE_INT) 0)
239 /* Do not generate a prefetch if the unroll factor is significantly less
240 than what is required by the prefetch. This is to avoid redundant
241 prefetches. For example, when prefetch_mod is 16 and unroll_factor is
242 2, prefetching requires unrolling the loop 16 times, but
243 the loop is actually unrolled twice. In this case (ratio = 8),
244 prefetching is not likely to be beneficial. */
246 #ifndef PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
247 #define PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO 4
250 /* Some of the prefetch computations have quadratic complexity. We want to
251 avoid huge compile times and, therefore, want to limit the amount of
252 memory references per loop where we consider prefetching. */
254 #ifndef PREFETCH_MAX_MEM_REFS_PER_LOOP
255 #define PREFETCH_MAX_MEM_REFS_PER_LOOP 200
258 /* The memory reference. */
262 gimple stmt
; /* Statement in that the reference appears. */
263 tree mem
; /* The reference. */
264 HOST_WIDE_INT delta
; /* Constant offset of the reference. */
265 struct mem_ref_group
*group
; /* The group of references it belongs to. */
266 unsigned HOST_WIDE_INT prefetch_mod
;
267 /* Prefetch only each PREFETCH_MOD-th
269 unsigned HOST_WIDE_INT prefetch_before
;
270 /* Prefetch only first PREFETCH_BEFORE
272 unsigned reuse_distance
; /* The amount of data accessed before the first
273 reuse of this value. */
274 struct mem_ref
*next
; /* The next reference in the group. */
275 unsigned write_p
: 1; /* Is it a write? */
276 unsigned independent_p
: 1; /* True if the reference is independent on
277 all other references inside the loop. */
278 unsigned issue_prefetch_p
: 1; /* Should we really issue the prefetch? */
279 unsigned storent_p
: 1; /* True if we changed the store to a
283 /* Dumps information about reference REF to FILE. */
286 dump_mem_ref (FILE *file
, struct mem_ref
*ref
)
288 fprintf (file
, "Reference %p:\n", (void *) ref
);
290 fprintf (file
, " group %p (base ", (void *) ref
->group
);
291 print_generic_expr (file
, ref
->group
->base
, TDF_SLIM
);
292 fprintf (file
, ", step ");
293 if (cst_and_fits_in_hwi (ref
->group
->step
))
294 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, int_cst_value (ref
->group
->step
));
296 print_generic_expr (file
, ref
->group
->step
, TDF_TREE
);
297 fprintf (file
, ")\n");
299 fprintf (file
, " delta ");
300 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, ref
->delta
);
301 fprintf (file
, "\n");
303 fprintf (file
, " %s\n", ref
->write_p
? "write" : "read");
305 fprintf (file
, "\n");
308 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
311 static struct mem_ref_group
*
312 find_or_create_group (struct mem_ref_group
**groups
, tree base
, tree step
)
314 struct mem_ref_group
*group
;
316 for (; *groups
; groups
= &(*groups
)->next
)
318 if (operand_equal_p ((*groups
)->step
, step
, 0)
319 && operand_equal_p ((*groups
)->base
, base
, 0))
322 /* If step is an integer constant, keep the list of groups sorted
323 by decreasing step. */
324 if (cst_and_fits_in_hwi ((*groups
)->step
) && cst_and_fits_in_hwi (step
)
325 && int_cst_value ((*groups
)->step
) < int_cst_value (step
))
329 group
= XNEW (struct mem_ref_group
);
333 group
->next
= *groups
;
339 /* Records a memory reference MEM in GROUP with offset DELTA and write status
340 WRITE_P. The reference occurs in statement STMT. */
343 record_ref (struct mem_ref_group
*group
, gimple stmt
, tree mem
,
344 HOST_WIDE_INT delta
, bool write_p
)
346 struct mem_ref
**aref
;
348 /* Do not record the same address twice. */
349 for (aref
= &group
->refs
; *aref
; aref
= &(*aref
)->next
)
351 /* It does not have to be possible for write reference to reuse the read
352 prefetch, or vice versa. */
353 if (!WRITE_CAN_USE_READ_PREFETCH
355 && !(*aref
)->write_p
)
357 if (!READ_CAN_USE_WRITE_PREFETCH
362 if ((*aref
)->delta
== delta
)
366 (*aref
) = XNEW (struct mem_ref
);
367 (*aref
)->stmt
= stmt
;
369 (*aref
)->delta
= delta
;
370 (*aref
)->write_p
= write_p
;
371 (*aref
)->prefetch_before
= PREFETCH_ALL
;
372 (*aref
)->prefetch_mod
= 1;
373 (*aref
)->reuse_distance
= 0;
374 (*aref
)->issue_prefetch_p
= false;
375 (*aref
)->group
= group
;
376 (*aref
)->next
= NULL
;
377 (*aref
)->independent_p
= false;
378 (*aref
)->storent_p
= false;
380 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
381 dump_mem_ref (dump_file
, *aref
);
384 /* Release memory references in GROUPS. */
387 release_mem_refs (struct mem_ref_group
*groups
)
389 struct mem_ref_group
*next_g
;
390 struct mem_ref
*ref
, *next_r
;
392 for (; groups
; groups
= next_g
)
394 next_g
= groups
->next
;
395 for (ref
= groups
->refs
; ref
; ref
= next_r
)
404 /* A structure used to pass arguments to idx_analyze_ref. */
408 struct loop
*loop
; /* Loop of the reference. */
409 gimple stmt
; /* Statement of the reference. */
410 tree
*step
; /* Step of the memory reference. */
411 HOST_WIDE_INT
*delta
; /* Offset of the memory reference. */
414 /* Analyzes a single INDEX of a memory reference to obtain information
415 described at analyze_ref. Callback for for_each_index. */
418 idx_analyze_ref (tree base
, tree
*index
, void *data
)
420 struct ar_data
*ar_data
= (struct ar_data
*) data
;
421 tree ibase
, step
, stepsize
;
422 HOST_WIDE_INT idelta
= 0, imult
= 1;
425 if (!simple_iv (ar_data
->loop
, loop_containing_stmt (ar_data
->stmt
),
431 if (TREE_CODE (ibase
) == POINTER_PLUS_EXPR
432 && cst_and_fits_in_hwi (TREE_OPERAND (ibase
, 1)))
434 idelta
= int_cst_value (TREE_OPERAND (ibase
, 1));
435 ibase
= TREE_OPERAND (ibase
, 0);
437 if (cst_and_fits_in_hwi (ibase
))
439 idelta
+= int_cst_value (ibase
);
440 ibase
= build_int_cst (TREE_TYPE (ibase
), 0);
443 if (TREE_CODE (base
) == ARRAY_REF
)
445 stepsize
= array_ref_element_size (base
);
446 if (!cst_and_fits_in_hwi (stepsize
))
448 imult
= int_cst_value (stepsize
);
449 step
= fold_build2 (MULT_EXPR
, sizetype
,
450 fold_convert (sizetype
, step
),
451 fold_convert (sizetype
, stepsize
));
455 if (*ar_data
->step
== NULL_TREE
)
456 *ar_data
->step
= step
;
458 *ar_data
->step
= fold_build2 (PLUS_EXPR
, sizetype
,
459 fold_convert (sizetype
, *ar_data
->step
),
460 fold_convert (sizetype
, step
));
461 *ar_data
->delta
+= idelta
;
467 /* Tries to express REF_P in shape &BASE + STEP * iter + DELTA, where DELTA and
468 STEP are integer constants and iter is number of iterations of LOOP. The
469 reference occurs in statement STMT. Strips nonaddressable component
470 references from REF_P. */
473 analyze_ref (struct loop
*loop
, tree
*ref_p
, tree
*base
,
474 tree
*step
, HOST_WIDE_INT
*delta
,
477 struct ar_data ar_data
;
479 HOST_WIDE_INT bit_offset
;
485 /* First strip off the component references. Ignore bitfields.
486 Also strip off the real and imagine parts of a complex, so that
487 they can have the same base. */
488 if (TREE_CODE (ref
) == REALPART_EXPR
489 || TREE_CODE (ref
) == IMAGPART_EXPR
490 || (TREE_CODE (ref
) == COMPONENT_REF
491 && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref
, 1))))
493 if (TREE_CODE (ref
) == IMAGPART_EXPR
)
494 *delta
+= int_size_in_bytes (TREE_TYPE (ref
));
495 ref
= TREE_OPERAND (ref
, 0);
500 for (; TREE_CODE (ref
) == COMPONENT_REF
; ref
= TREE_OPERAND (ref
, 0))
502 off
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
503 bit_offset
= TREE_INT_CST_LOW (off
);
504 gcc_assert (bit_offset
% BITS_PER_UNIT
== 0);
506 *delta
+= bit_offset
/ BITS_PER_UNIT
;
509 *base
= unshare_expr (ref
);
513 ar_data
.delta
= delta
;
514 return for_each_index (base
, idx_analyze_ref
, &ar_data
);
517 /* Record a memory reference REF to the list REFS. The reference occurs in
518 LOOP in statement STMT and it is write if WRITE_P. Returns true if the
519 reference was recorded, false otherwise. */
522 gather_memory_references_ref (struct loop
*loop
, struct mem_ref_group
**refs
,
523 tree ref
, bool write_p
, gimple stmt
)
527 struct mem_ref_group
*agrp
;
529 if (get_base_address (ref
) == NULL
)
532 if (!analyze_ref (loop
, &ref
, &base
, &step
, &delta
, stmt
))
534 /* If analyze_ref fails the default is a NULL_TREE. We can stop here. */
535 if (step
== NULL_TREE
)
538 /* Stop if the address of BASE could not be taken. */
539 if (may_be_nonaddressable_p (base
))
542 /* Limit non-constant step prefetching only to the innermost loops. */
543 if (!cst_and_fits_in_hwi (step
) && loop
->inner
!= NULL
)
546 /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
547 are integer constants. */
548 agrp
= find_or_create_group (refs
, base
, step
);
549 record_ref (agrp
, stmt
, ref
, delta
, write_p
);
554 /* Record the suitable memory references in LOOP. NO_OTHER_REFS is set to
555 true if there are no other memory references inside the loop. */
557 static struct mem_ref_group
*
558 gather_memory_references (struct loop
*loop
, bool *no_other_refs
, unsigned *ref_count
)
560 basic_block
*body
= get_loop_body_in_dom_order (loop
);
563 gimple_stmt_iterator bsi
;
566 struct mem_ref_group
*refs
= NULL
;
568 *no_other_refs
= true;
571 /* Scan the loop body in order, so that the former references precede the
573 for (i
= 0; i
< loop
->num_nodes
; i
++)
576 if (bb
->loop_father
!= loop
)
579 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
581 stmt
= gsi_stmt (bsi
);
583 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
585 if (gimple_vuse (stmt
)
586 || (is_gimple_call (stmt
)
587 && !(gimple_call_flags (stmt
) & ECF_CONST
)))
588 *no_other_refs
= false;
592 lhs
= gimple_assign_lhs (stmt
);
593 rhs
= gimple_assign_rhs1 (stmt
);
595 if (REFERENCE_CLASS_P (rhs
))
597 *no_other_refs
&= gather_memory_references_ref (loop
, &refs
,
601 if (REFERENCE_CLASS_P (lhs
))
603 *no_other_refs
&= gather_memory_references_ref (loop
, &refs
,
614 /* Prune the prefetch candidate REF using the self-reuse. */
617 prune_ref_by_self_reuse (struct mem_ref
*ref
)
622 /* If the step size is non constant, we cannot calculate prefetch_mod. */
623 if (!cst_and_fits_in_hwi (ref
->group
->step
))
626 step
= int_cst_value (ref
->group
->step
);
632 /* Prefetch references to invariant address just once. */
633 ref
->prefetch_before
= 1;
640 if (step
> PREFETCH_BLOCK
)
643 if ((backward
&& HAVE_BACKWARD_PREFETCH
)
644 || (!backward
&& HAVE_FORWARD_PREFETCH
))
646 ref
->prefetch_before
= 1;
650 ref
->prefetch_mod
= PREFETCH_BLOCK
/ step
;
653 /* Divides X by BY, rounding down. */
656 ddown (HOST_WIDE_INT x
, unsigned HOST_WIDE_INT by
)
663 return (x
+ by
- 1) / by
;
666 /* Given a CACHE_LINE_SIZE and two inductive memory references
667 with a common STEP greater than CACHE_LINE_SIZE and an address
668 difference DELTA, compute the probability that they will fall
669 in different cache lines. Return true if the computed miss rate
670 is not greater than the ACCEPTABLE_MISS_RATE. DISTINCT_ITERS is the
671 number of distinct iterations after which the pattern repeats itself.
672 ALIGN_UNIT is the unit of alignment in bytes. */
675 is_miss_rate_acceptable (unsigned HOST_WIDE_INT cache_line_size
,
676 HOST_WIDE_INT step
, HOST_WIDE_INT delta
,
677 unsigned HOST_WIDE_INT distinct_iters
,
680 unsigned align
, iter
;
681 int total_positions
, miss_positions
, max_allowed_miss_positions
;
682 int address1
, address2
, cache_line1
, cache_line2
;
684 /* It always misses if delta is greater than or equal to the cache
686 if (delta
>= (HOST_WIDE_INT
) cache_line_size
)
690 total_positions
= (cache_line_size
/ align_unit
) * distinct_iters
;
691 max_allowed_miss_positions
= (ACCEPTABLE_MISS_RATE
* total_positions
) / 1000;
693 /* Iterate through all possible alignments of the first
694 memory reference within its cache line. */
695 for (align
= 0; align
< cache_line_size
; align
+= align_unit
)
697 /* Iterate through all distinct iterations. */
698 for (iter
= 0; iter
< distinct_iters
; iter
++)
700 address1
= align
+ step
* iter
;
701 address2
= address1
+ delta
;
702 cache_line1
= address1
/ cache_line_size
;
703 cache_line2
= address2
/ cache_line_size
;
704 if (cache_line1
!= cache_line2
)
707 if (miss_positions
> max_allowed_miss_positions
)
714 /* Prune the prefetch candidate REF using the reuse with BY.
715 If BY_IS_BEFORE is true, BY is before REF in the loop. */
718 prune_ref_by_group_reuse (struct mem_ref
*ref
, struct mem_ref
*by
,
723 HOST_WIDE_INT delta_r
= ref
->delta
, delta_b
= by
->delta
;
724 HOST_WIDE_INT delta
= delta_b
- delta_r
;
725 HOST_WIDE_INT hit_from
;
726 unsigned HOST_WIDE_INT prefetch_before
, prefetch_block
;
727 HOST_WIDE_INT reduced_step
;
728 unsigned HOST_WIDE_INT reduced_prefetch_block
;
732 /* If the step is non constant we cannot calculate prefetch_before. */
733 if (!cst_and_fits_in_hwi (ref
->group
->step
)) {
737 step
= int_cst_value (ref
->group
->step
);
744 /* If the references has the same address, only prefetch the
747 ref
->prefetch_before
= 0;
754 /* If the reference addresses are invariant and fall into the
755 same cache line, prefetch just the first one. */
759 if (ddown (ref
->delta
, PREFETCH_BLOCK
)
760 != ddown (by
->delta
, PREFETCH_BLOCK
))
763 ref
->prefetch_before
= 0;
767 /* Only prune the reference that is behind in the array. */
773 /* Transform the data so that we may assume that the accesses
777 delta_r
= PREFETCH_BLOCK
- 1 - delta_r
;
778 delta_b
= PREFETCH_BLOCK
- 1 - delta_b
;
786 /* Check whether the two references are likely to hit the same cache
787 line, and how distant the iterations in that it occurs are from
790 if (step
<= PREFETCH_BLOCK
)
792 /* The accesses are sure to meet. Let us check when. */
793 hit_from
= ddown (delta_b
, PREFETCH_BLOCK
) * PREFETCH_BLOCK
;
794 prefetch_before
= (hit_from
- delta_r
+ step
- 1) / step
;
796 /* Do not reduce prefetch_before if we meet beyond cache size. */
797 if (prefetch_before
> absu_hwi (L2_CACHE_SIZE_BYTES
/ step
))
798 prefetch_before
= PREFETCH_ALL
;
799 if (prefetch_before
< ref
->prefetch_before
)
800 ref
->prefetch_before
= prefetch_before
;
805 /* A more complicated case with step > prefetch_block. First reduce
806 the ratio between the step and the cache line size to its simplest
807 terms. The resulting denominator will then represent the number of
808 distinct iterations after which each address will go back to its
809 initial location within the cache line. This computation assumes
810 that PREFETCH_BLOCK is a power of two. */
811 prefetch_block
= PREFETCH_BLOCK
;
812 reduced_prefetch_block
= prefetch_block
;
814 while ((reduced_step
& 1) == 0
815 && reduced_prefetch_block
> 1)
818 reduced_prefetch_block
>>= 1;
821 prefetch_before
= delta
/ step
;
823 ref_type
= TREE_TYPE (ref
->mem
);
824 align_unit
= TYPE_ALIGN (ref_type
) / 8;
825 if (is_miss_rate_acceptable (prefetch_block
, step
, delta
,
826 reduced_prefetch_block
, align_unit
))
828 /* Do not reduce prefetch_before if we meet beyond cache size. */
829 if (prefetch_before
> L2_CACHE_SIZE_BYTES
/ PREFETCH_BLOCK
)
830 prefetch_before
= PREFETCH_ALL
;
831 if (prefetch_before
< ref
->prefetch_before
)
832 ref
->prefetch_before
= prefetch_before
;
837 /* Try also the following iteration. */
839 delta
= step
- delta
;
840 if (is_miss_rate_acceptable (prefetch_block
, step
, delta
,
841 reduced_prefetch_block
, align_unit
))
843 if (prefetch_before
< ref
->prefetch_before
)
844 ref
->prefetch_before
= prefetch_before
;
849 /* The ref probably does not reuse by. */
853 /* Prune the prefetch candidate REF using the reuses with other references
857 prune_ref_by_reuse (struct mem_ref
*ref
, struct mem_ref
*refs
)
859 struct mem_ref
*prune_by
;
862 prune_ref_by_self_reuse (ref
);
864 for (prune_by
= refs
; prune_by
; prune_by
= prune_by
->next
)
872 if (!WRITE_CAN_USE_READ_PREFETCH
874 && !prune_by
->write_p
)
876 if (!READ_CAN_USE_WRITE_PREFETCH
878 && prune_by
->write_p
)
881 prune_ref_by_group_reuse (ref
, prune_by
, before
);
885 /* Prune the prefetch candidates in GROUP using the reuse analysis. */
888 prune_group_by_reuse (struct mem_ref_group
*group
)
890 struct mem_ref
*ref_pruned
;
892 for (ref_pruned
= group
->refs
; ref_pruned
; ref_pruned
= ref_pruned
->next
)
894 prune_ref_by_reuse (ref_pruned
, group
->refs
);
896 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
898 fprintf (dump_file
, "Reference %p:", (void *) ref_pruned
);
900 if (ref_pruned
->prefetch_before
== PREFETCH_ALL
901 && ref_pruned
->prefetch_mod
== 1)
902 fprintf (dump_file
, " no restrictions");
903 else if (ref_pruned
->prefetch_before
== 0)
904 fprintf (dump_file
, " do not prefetch");
905 else if (ref_pruned
->prefetch_before
<= ref_pruned
->prefetch_mod
)
906 fprintf (dump_file
, " prefetch once");
909 if (ref_pruned
->prefetch_before
!= PREFETCH_ALL
)
911 fprintf (dump_file
, " prefetch before ");
912 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
913 ref_pruned
->prefetch_before
);
915 if (ref_pruned
->prefetch_mod
!= 1)
917 fprintf (dump_file
, " prefetch mod ");
918 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
919 ref_pruned
->prefetch_mod
);
922 fprintf (dump_file
, "\n");
927 /* Prune the list of prefetch candidates GROUPS using the reuse analysis. */
930 prune_by_reuse (struct mem_ref_group
*groups
)
932 for (; groups
; groups
= groups
->next
)
933 prune_group_by_reuse (groups
);
936 /* Returns true if we should issue prefetch for REF. */
939 should_issue_prefetch_p (struct mem_ref
*ref
)
941 /* For now do not issue prefetches for only first few of the
943 if (ref
->prefetch_before
!= PREFETCH_ALL
)
945 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
946 fprintf (dump_file
, "Ignoring %p due to prefetch_before\n",
951 /* Do not prefetch nontemporal stores. */
954 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
955 fprintf (dump_file
, "Ignoring nontemporal store %p\n", (void *) ref
);
962 /* Decide which of the prefetch candidates in GROUPS to prefetch.
963 AHEAD is the number of iterations to prefetch ahead (which corresponds
964 to the number of simultaneous instances of one prefetch running at a
965 time). UNROLL_FACTOR is the factor by that the loop is going to be
966 unrolled. Returns true if there is anything to prefetch. */
969 schedule_prefetches (struct mem_ref_group
*groups
, unsigned unroll_factor
,
972 unsigned remaining_prefetch_slots
, n_prefetches
, prefetch_slots
;
973 unsigned slots_per_prefetch
;
977 /* At most SIMULTANEOUS_PREFETCHES should be running at the same time. */
978 remaining_prefetch_slots
= SIMULTANEOUS_PREFETCHES
;
980 /* The prefetch will run for AHEAD iterations of the original loop, i.e.,
981 AHEAD / UNROLL_FACTOR iterations of the unrolled loop. In each iteration,
982 it will need a prefetch slot. */
983 slots_per_prefetch
= (ahead
+ unroll_factor
/ 2) / unroll_factor
;
984 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
985 fprintf (dump_file
, "Each prefetch instruction takes %u prefetch slots.\n",
988 /* For now we just take memory references one by one and issue
989 prefetches for as many as possible. The groups are sorted
990 starting with the largest step, since the references with
991 large step are more likely to cause many cache misses. */
993 for (; groups
; groups
= groups
->next
)
994 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
996 if (!should_issue_prefetch_p (ref
))
999 /* The loop is far from being sufficiently unrolled for this
1000 prefetch. Do not generate prefetch to avoid many redudant
1002 if (ref
->prefetch_mod
/ unroll_factor
> PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
)
1005 /* If we need to prefetch the reference each PREFETCH_MOD iterations,
1006 and we unroll the loop UNROLL_FACTOR times, we need to insert
1007 ceil (UNROLL_FACTOR / PREFETCH_MOD) instructions in each
1009 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1010 / ref
->prefetch_mod
);
1011 prefetch_slots
= n_prefetches
* slots_per_prefetch
;
1013 /* If more than half of the prefetches would be lost anyway, do not
1014 issue the prefetch. */
1015 if (2 * remaining_prefetch_slots
< prefetch_slots
)
1018 ref
->issue_prefetch_p
= true;
1020 if (remaining_prefetch_slots
<= prefetch_slots
)
1022 remaining_prefetch_slots
-= prefetch_slots
;
1029 /* Return TRUE if no prefetch is going to be generated in the given
1033 nothing_to_prefetch_p (struct mem_ref_group
*groups
)
1035 struct mem_ref
*ref
;
1037 for (; groups
; groups
= groups
->next
)
1038 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1039 if (should_issue_prefetch_p (ref
))
1045 /* Estimate the number of prefetches in the given GROUPS.
1046 UNROLL_FACTOR is the factor by which LOOP was unrolled. */
1049 estimate_prefetch_count (struct mem_ref_group
*groups
, unsigned unroll_factor
)
1051 struct mem_ref
*ref
;
1052 unsigned n_prefetches
;
1053 int prefetch_count
= 0;
1055 for (; groups
; groups
= groups
->next
)
1056 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1057 if (should_issue_prefetch_p (ref
))
1059 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1060 / ref
->prefetch_mod
);
1061 prefetch_count
+= n_prefetches
;
1064 return prefetch_count
;
1067 /* Issue prefetches for the reference REF into loop as decided before.
1068 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR
1069 is the factor by which LOOP was unrolled. */
1072 issue_prefetch_ref (struct mem_ref
*ref
, unsigned unroll_factor
, unsigned ahead
)
1074 HOST_WIDE_INT delta
;
1075 tree addr
, addr_base
, write_p
, local
, forward
;
1077 gimple_stmt_iterator bsi
;
1078 unsigned n_prefetches
, ap
;
1079 bool nontemporal
= ref
->reuse_distance
>= L2_CACHE_SIZE_BYTES
;
1081 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1082 fprintf (dump_file
, "Issued%s prefetch for %p.\n",
1083 nontemporal
? " nontemporal" : "",
1086 bsi
= gsi_for_stmt (ref
->stmt
);
1088 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
1089 / ref
->prefetch_mod
);
1090 addr_base
= build_fold_addr_expr_with_type (ref
->mem
, ptr_type_node
);
1091 addr_base
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr_base
),
1092 true, NULL
, true, GSI_SAME_STMT
);
1093 write_p
= ref
->write_p
? integer_one_node
: integer_zero_node
;
1094 local
= nontemporal
? integer_zero_node
: integer_three_node
;
1096 for (ap
= 0; ap
< n_prefetches
; ap
++)
1098 if (cst_and_fits_in_hwi (ref
->group
->step
))
1100 /* Determine the address to prefetch. */
1101 delta
= (ahead
+ ap
* ref
->prefetch_mod
) *
1102 int_cst_value (ref
->group
->step
);
1103 addr
= fold_build_pointer_plus_hwi (addr_base
, delta
);
1104 addr
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr
), true, NULL
,
1105 true, GSI_SAME_STMT
);
1109 /* The step size is non-constant but loop-invariant. We use the
1110 heuristic to simply prefetch ahead iterations ahead. */
1111 forward
= fold_build2 (MULT_EXPR
, sizetype
,
1112 fold_convert (sizetype
, ref
->group
->step
),
1113 fold_convert (sizetype
, size_int (ahead
)));
1114 addr
= fold_build_pointer_plus (addr_base
, forward
);
1115 addr
= force_gimple_operand_gsi (&bsi
, unshare_expr (addr
), true,
1116 NULL
, true, GSI_SAME_STMT
);
1118 /* Create the prefetch instruction. */
1119 prefetch
= gimple_build_call (builtin_decl_explicit (BUILT_IN_PREFETCH
),
1120 3, addr
, write_p
, local
);
1121 gsi_insert_before (&bsi
, prefetch
, GSI_SAME_STMT
);
1125 /* Issue prefetches for the references in GROUPS into loop as decided before.
1126 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR is the
1127 factor by that LOOP was unrolled. */
1130 issue_prefetches (struct mem_ref_group
*groups
,
1131 unsigned unroll_factor
, unsigned ahead
)
1133 struct mem_ref
*ref
;
1135 for (; groups
; groups
= groups
->next
)
1136 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1137 if (ref
->issue_prefetch_p
)
1138 issue_prefetch_ref (ref
, unroll_factor
, ahead
);
1141 /* Returns true if REF is a memory write for that a nontemporal store insn
1145 nontemporal_store_p (struct mem_ref
*ref
)
1147 enum machine_mode mode
;
1148 enum insn_code code
;
1150 /* REF must be a write that is not reused. We require it to be independent
1151 on all other memory references in the loop, as the nontemporal stores may
1152 be reordered with respect to other memory references. */
1154 || !ref
->independent_p
1155 || ref
->reuse_distance
< L2_CACHE_SIZE_BYTES
)
1158 /* Check that we have the storent instruction for the mode. */
1159 mode
= TYPE_MODE (TREE_TYPE (ref
->mem
));
1160 if (mode
== BLKmode
)
1163 code
= optab_handler (storent_optab
, mode
);
1164 return code
!= CODE_FOR_nothing
;
1167 /* If REF is a nontemporal store, we mark the corresponding modify statement
1168 and return true. Otherwise, we return false. */
1171 mark_nontemporal_store (struct mem_ref
*ref
)
1173 if (!nontemporal_store_p (ref
))
1176 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1177 fprintf (dump_file
, "Marked reference %p as a nontemporal store.\n",
1180 gimple_assign_set_nontemporal_move (ref
->stmt
, true);
1181 ref
->storent_p
= true;
1186 /* Issue a memory fence instruction after LOOP. */
1189 emit_mfence_after_loop (struct loop
*loop
)
1191 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
1194 gimple_stmt_iterator bsi
;
1197 FOR_EACH_VEC_ELT (edge
, exits
, i
, exit
)
1199 call
= gimple_build_call (FENCE_FOLLOWING_MOVNT
, 0);
1201 if (!single_pred_p (exit
->dest
)
1202 /* If possible, we prefer not to insert the fence on other paths
1204 && !(exit
->flags
& EDGE_ABNORMAL
))
1205 split_loop_exit_edge (exit
);
1206 bsi
= gsi_after_labels (exit
->dest
);
1208 gsi_insert_before (&bsi
, call
, GSI_NEW_STMT
);
1209 mark_virtual_ops_for_renaming (call
);
1212 VEC_free (edge
, heap
, exits
);
1213 update_ssa (TODO_update_ssa_only_virtuals
);
1216 /* Returns true if we can use storent in loop, false otherwise. */
1219 may_use_storent_in_loop_p (struct loop
*loop
)
1223 if (loop
->inner
!= NULL
)
1226 /* If we must issue a mfence insn after using storent, check that there
1227 is a suitable place for it at each of the loop exits. */
1228 if (FENCE_FOLLOWING_MOVNT
!= NULL_TREE
)
1230 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
1234 FOR_EACH_VEC_ELT (edge
, exits
, i
, exit
)
1235 if ((exit
->flags
& EDGE_ABNORMAL
)
1236 && exit
->dest
== EXIT_BLOCK_PTR
)
1239 VEC_free (edge
, heap
, exits
);
1245 /* Marks nontemporal stores in LOOP. GROUPS contains the description of memory
1246 references in the loop. */
1249 mark_nontemporal_stores (struct loop
*loop
, struct mem_ref_group
*groups
)
1251 struct mem_ref
*ref
;
1254 if (!may_use_storent_in_loop_p (loop
))
1257 for (; groups
; groups
= groups
->next
)
1258 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1259 any
|= mark_nontemporal_store (ref
);
1261 if (any
&& FENCE_FOLLOWING_MOVNT
!= NULL_TREE
)
1262 emit_mfence_after_loop (loop
);
1265 /* Determines whether we can profitably unroll LOOP FACTOR times, and if
1266 this is the case, fill in DESC by the description of number of
1270 should_unroll_loop_p (struct loop
*loop
, struct tree_niter_desc
*desc
,
1273 if (!can_unroll_loop_p (loop
, factor
, desc
))
1276 /* We only consider loops without control flow for unrolling. This is not
1277 a hard restriction -- tree_unroll_loop works with arbitrary loops
1278 as well; but the unrolling/prefetching is usually more profitable for
1279 loops consisting of a single basic block, and we want to limit the
1281 if (loop
->num_nodes
> 2)
1287 /* Determine the coefficient by that unroll LOOP, from the information
1288 contained in the list of memory references REFS. Description of
1289 umber of iterations of LOOP is stored to DESC. NINSNS is the number of
1290 insns of the LOOP. EST_NITER is the estimated number of iterations of
1291 the loop, or -1 if no estimate is available. */
1294 determine_unroll_factor (struct loop
*loop
, struct mem_ref_group
*refs
,
1295 unsigned ninsns
, struct tree_niter_desc
*desc
,
1296 HOST_WIDE_INT est_niter
)
1298 unsigned upper_bound
;
1299 unsigned nfactor
, factor
, mod_constraint
;
1300 struct mem_ref_group
*agp
;
1301 struct mem_ref
*ref
;
1303 /* First check whether the loop is not too large to unroll. We ignore
1304 PARAM_MAX_UNROLL_TIMES, because for small loops, it prevented us
1305 from unrolling them enough to make exactly one cache line covered by each
1306 iteration. Also, the goal of PARAM_MAX_UNROLL_TIMES is to prevent
1307 us from unrolling the loops too many times in cases where we only expect
1308 gains from better scheduling and decreasing loop overhead, which is not
1310 upper_bound
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / ninsns
;
1312 /* If we unrolled the loop more times than it iterates, the unrolled version
1313 of the loop would be never entered. */
1314 if (est_niter
>= 0 && est_niter
< (HOST_WIDE_INT
) upper_bound
)
1315 upper_bound
= est_niter
;
1317 if (upper_bound
<= 1)
1320 /* Choose the factor so that we may prefetch each cache just once,
1321 but bound the unrolling by UPPER_BOUND. */
1323 for (agp
= refs
; agp
; agp
= agp
->next
)
1324 for (ref
= agp
->refs
; ref
; ref
= ref
->next
)
1325 if (should_issue_prefetch_p (ref
))
1327 mod_constraint
= ref
->prefetch_mod
;
1328 nfactor
= least_common_multiple (mod_constraint
, factor
);
1329 if (nfactor
<= upper_bound
)
1333 if (!should_unroll_loop_p (loop
, desc
, factor
))
1339 /* Returns the total volume of the memory references REFS, taking into account
1340 reuses in the innermost loop and cache line size. TODO -- we should also
1341 take into account reuses across the iterations of the loops in the loop
1345 volume_of_references (struct mem_ref_group
*refs
)
1347 unsigned volume
= 0;
1348 struct mem_ref_group
*gr
;
1349 struct mem_ref
*ref
;
1351 for (gr
= refs
; gr
; gr
= gr
->next
)
1352 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1354 /* Almost always reuses another value? */
1355 if (ref
->prefetch_before
!= PREFETCH_ALL
)
1358 /* If several iterations access the same cache line, use the size of
1359 the line divided by this number. Otherwise, a cache line is
1360 accessed in each iteration. TODO -- in the latter case, we should
1361 take the size of the reference into account, rounding it up on cache
1362 line size multiple. */
1363 volume
+= L1_CACHE_LINE_SIZE
/ ref
->prefetch_mod
;
1368 /* Returns the volume of memory references accessed across VEC iterations of
1369 loops, whose sizes are described in the LOOP_SIZES array. N is the number
1370 of the loops in the nest (length of VEC and LOOP_SIZES vectors). */
1373 volume_of_dist_vector (lambda_vector vec
, unsigned *loop_sizes
, unsigned n
)
1377 for (i
= 0; i
< n
; i
++)
1384 gcc_assert (vec
[i
] > 0);
1386 /* We ignore the parts of the distance vector in subloops, since usually
1387 the numbers of iterations are much smaller. */
1388 return loop_sizes
[i
] * vec
[i
];
1391 /* Add the steps of ACCESS_FN multiplied by STRIDE to the array STRIDE
1392 at the position corresponding to the loop of the step. N is the depth
1393 of the considered loop nest, and, LOOP is its innermost loop. */
1396 add_subscript_strides (tree access_fn
, unsigned stride
,
1397 HOST_WIDE_INT
*strides
, unsigned n
, struct loop
*loop
)
1401 HOST_WIDE_INT astep
;
1402 unsigned min_depth
= loop_depth (loop
) - n
;
1404 while (TREE_CODE (access_fn
) == POLYNOMIAL_CHREC
)
1406 aloop
= get_chrec_loop (access_fn
);
1407 step
= CHREC_RIGHT (access_fn
);
1408 access_fn
= CHREC_LEFT (access_fn
);
1410 if ((unsigned) loop_depth (aloop
) <= min_depth
)
1413 if (host_integerp (step
, 0))
1414 astep
= tree_low_cst (step
, 0);
1416 astep
= L1_CACHE_LINE_SIZE
;
1418 strides
[n
- 1 - loop_depth (loop
) + loop_depth (aloop
)] += astep
* stride
;
1423 /* Returns the volume of memory references accessed between two consecutive
1424 self-reuses of the reference DR. We consider the subscripts of DR in N
1425 loops, and LOOP_SIZES contains the volumes of accesses in each of the
1426 loops. LOOP is the innermost loop of the current loop nest. */
1429 self_reuse_distance (data_reference_p dr
, unsigned *loop_sizes
, unsigned n
,
1432 tree stride
, access_fn
;
1433 HOST_WIDE_INT
*strides
, astride
;
1434 VEC (tree
, heap
) *access_fns
;
1435 tree ref
= DR_REF (dr
);
1436 unsigned i
, ret
= ~0u;
1438 /* In the following example:
1440 for (i = 0; i < N; i++)
1441 for (j = 0; j < N; j++)
1443 the same cache line is accessed each N steps (except if the change from
1444 i to i + 1 crosses the boundary of the cache line). Thus, for self-reuse,
1445 we cannot rely purely on the results of the data dependence analysis.
1447 Instead, we compute the stride of the reference in each loop, and consider
1448 the innermost loop in that the stride is less than cache size. */
1450 strides
= XCNEWVEC (HOST_WIDE_INT
, n
);
1451 access_fns
= DR_ACCESS_FNS (dr
);
1453 FOR_EACH_VEC_ELT (tree
, access_fns
, i
, access_fn
)
1455 /* Keep track of the reference corresponding to the subscript, so that we
1457 while (handled_component_p (ref
) && TREE_CODE (ref
) != ARRAY_REF
)
1458 ref
= TREE_OPERAND (ref
, 0);
1460 if (TREE_CODE (ref
) == ARRAY_REF
)
1462 stride
= TYPE_SIZE_UNIT (TREE_TYPE (ref
));
1463 if (host_integerp (stride
, 1))
1464 astride
= tree_low_cst (stride
, 1);
1466 astride
= L1_CACHE_LINE_SIZE
;
1468 ref
= TREE_OPERAND (ref
, 0);
1473 add_subscript_strides (access_fn
, astride
, strides
, n
, loop
);
1476 for (i
= n
; i
-- > 0; )
1478 unsigned HOST_WIDE_INT s
;
1480 s
= strides
[i
] < 0 ? -strides
[i
] : strides
[i
];
1482 if (s
< (unsigned) L1_CACHE_LINE_SIZE
1484 > (unsigned) (L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)))
1486 ret
= loop_sizes
[i
];
1495 /* Determines the distance till the first reuse of each reference in REFS
1496 in the loop nest of LOOP. NO_OTHER_REFS is true if there are no other
1497 memory references in the loop. Return false if the analysis fails. */
1500 determine_loop_nest_reuse (struct loop
*loop
, struct mem_ref_group
*refs
,
1503 struct loop
*nest
, *aloop
;
1504 VEC (data_reference_p
, heap
) *datarefs
= NULL
;
1505 VEC (ddr_p
, heap
) *dependences
= NULL
;
1506 struct mem_ref_group
*gr
;
1507 struct mem_ref
*ref
, *refb
;
1508 VEC (loop_p
, heap
) *vloops
= NULL
;
1509 unsigned *loop_data_size
;
1511 unsigned volume
, dist
, adist
;
1513 data_reference_p dr
;
1519 /* Find the outermost loop of the loop nest of loop (we require that
1520 there are no sibling loops inside the nest). */
1524 aloop
= loop_outer (nest
);
1526 if (aloop
== current_loops
->tree_root
1527 || aloop
->inner
->next
)
1533 /* For each loop, determine the amount of data accessed in each iteration.
1534 We use this to estimate whether the reference is evicted from the
1535 cache before its reuse. */
1536 find_loop_nest (nest
, &vloops
);
1537 n
= VEC_length (loop_p
, vloops
);
1538 loop_data_size
= XNEWVEC (unsigned, n
);
1539 volume
= volume_of_references (refs
);
1543 loop_data_size
[i
] = volume
;
1544 /* Bound the volume by the L2 cache size, since above this bound,
1545 all dependence distances are equivalent. */
1546 if (volume
> L2_CACHE_SIZE_BYTES
)
1549 aloop
= VEC_index (loop_p
, vloops
, i
);
1550 vol
= estimated_stmt_executions_int (aloop
);
1552 vol
= expected_loop_iterations (aloop
);
1556 /* Prepare the references in the form suitable for data dependence
1557 analysis. We ignore unanalyzable data references (the results
1558 are used just as a heuristics to estimate temporality of the
1559 references, hence we do not need to worry about correctness). */
1560 for (gr
= refs
; gr
; gr
= gr
->next
)
1561 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1563 dr
= create_data_ref (nest
, loop_containing_stmt (ref
->stmt
),
1564 ref
->mem
, ref
->stmt
, !ref
->write_p
);
1568 ref
->reuse_distance
= volume
;
1570 VEC_safe_push (data_reference_p
, heap
, datarefs
, dr
);
1573 no_other_refs
= false;
1576 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
1578 dist
= self_reuse_distance (dr
, loop_data_size
, n
, loop
);
1579 ref
= (struct mem_ref
*) dr
->aux
;
1580 if (ref
->reuse_distance
> dist
)
1581 ref
->reuse_distance
= dist
;
1584 ref
->independent_p
= true;
1587 if (!compute_all_dependences (datarefs
, &dependences
, vloops
, true))
1590 FOR_EACH_VEC_ELT (ddr_p
, dependences
, i
, dep
)
1592 if (DDR_ARE_DEPENDENT (dep
) == chrec_known
)
1595 ref
= (struct mem_ref
*) DDR_A (dep
)->aux
;
1596 refb
= (struct mem_ref
*) DDR_B (dep
)->aux
;
1598 if (DDR_ARE_DEPENDENT (dep
) == chrec_dont_know
1599 || DDR_NUM_DIST_VECTS (dep
) == 0)
1601 /* If the dependence cannot be analyzed, assume that there might be
1605 ref
->independent_p
= false;
1606 refb
->independent_p
= false;
1610 /* The distance vectors are normalized to be always lexicographically
1611 positive, hence we cannot tell just from them whether DDR_A comes
1612 before DDR_B or vice versa. However, it is not important,
1613 anyway -- if DDR_A is close to DDR_B, then it is either reused in
1614 DDR_B (and it is not nontemporal), or it reuses the value of DDR_B
1615 in cache (and marking it as nontemporal would not affect
1619 for (j
= 0; j
< DDR_NUM_DIST_VECTS (dep
); j
++)
1621 adist
= volume_of_dist_vector (DDR_DIST_VECT (dep
, j
),
1624 /* If this is a dependence in the innermost loop (i.e., the
1625 distances in all superloops are zero) and it is not
1626 the trivial self-dependence with distance zero, record that
1627 the references are not completely independent. */
1628 if (lambda_vector_zerop (DDR_DIST_VECT (dep
, j
), n
- 1)
1630 || DDR_DIST_VECT (dep
, j
)[n
-1] != 0))
1632 ref
->independent_p
= false;
1633 refb
->independent_p
= false;
1636 /* Ignore accesses closer than
1637 L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
1638 so that we use nontemporal prefetches e.g. if single memory
1639 location is accessed several times in a single iteration of
1641 if (adist
< L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)
1649 if (ref
->reuse_distance
> dist
)
1650 ref
->reuse_distance
= dist
;
1651 if (refb
->reuse_distance
> dist
)
1652 refb
->reuse_distance
= dist
;
1655 free_dependence_relations (dependences
);
1656 free_data_refs (datarefs
);
1657 free (loop_data_size
);
1659 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1661 fprintf (dump_file
, "Reuse distances:\n");
1662 for (gr
= refs
; gr
; gr
= gr
->next
)
1663 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1664 fprintf (dump_file
, " ref %p distance %u\n",
1665 (void *) ref
, ref
->reuse_distance
);
1671 /* Determine whether or not the trip count to ahead ratio is too small based
1672 on prefitablility consideration.
1673 AHEAD: the iteration ahead distance,
1674 EST_NITER: the estimated trip count. */
1677 trip_count_to_ahead_ratio_too_small_p (unsigned ahead
, HOST_WIDE_INT est_niter
)
1679 /* Assume trip count to ahead ratio is big enough if the trip count could not
1680 be estimated at compile time. */
1684 if (est_niter
< (HOST_WIDE_INT
) (TRIP_COUNT_TO_AHEAD_RATIO
* ahead
))
1686 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1688 "Not prefetching -- loop estimated to roll only %d times\n",
1696 /* Determine whether or not the number of memory references in the loop is
1697 reasonable based on the profitablity and compilation time considerations.
1698 NINSNS: estimated number of instructions in the loop,
1699 MEM_REF_COUNT: total number of memory references in the loop. */
1702 mem_ref_count_reasonable_p (unsigned ninsns
, unsigned mem_ref_count
)
1704 int insn_to_mem_ratio
;
1706 if (mem_ref_count
== 0)
1709 /* Miss rate computation (is_miss_rate_acceptable) and dependence analysis
1710 (compute_all_dependences) have high costs based on quadratic complexity.
1711 To avoid huge compilation time, we give up prefetching if mem_ref_count
1713 if (mem_ref_count
> PREFETCH_MAX_MEM_REFS_PER_LOOP
)
1716 /* Prefetching improves performance by overlapping cache missing
1717 memory accesses with CPU operations. If the loop does not have
1718 enough CPU operations to overlap with memory operations, prefetching
1719 won't give a significant benefit. One approximate way of checking
1720 this is to require the ratio of instructions to memory references to
1721 be above a certain limit. This approximation works well in practice.
1722 TODO: Implement a more precise computation by estimating the time
1723 for each CPU or memory op in the loop. Time estimates for memory ops
1724 should account for cache misses. */
1725 insn_to_mem_ratio
= ninsns
/ mem_ref_count
;
1727 if (insn_to_mem_ratio
< PREFETCH_MIN_INSN_TO_MEM_RATIO
)
1729 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1731 "Not prefetching -- instruction to memory reference ratio (%d) too small\n",
1739 /* Determine whether or not the instruction to prefetch ratio in the loop is
1740 too small based on the profitablity consideration.
1741 NINSNS: estimated number of instructions in the loop,
1742 PREFETCH_COUNT: an estimate of the number of prefetches,
1743 UNROLL_FACTOR: the factor to unroll the loop if prefetching. */
1746 insn_to_prefetch_ratio_too_small_p (unsigned ninsns
, unsigned prefetch_count
,
1747 unsigned unroll_factor
)
1749 int insn_to_prefetch_ratio
;
1751 /* Prefetching most likely causes performance degradation when the instruction
1752 to prefetch ratio is too small. Too many prefetch instructions in a loop
1753 may reduce the I-cache performance.
1754 (unroll_factor * ninsns) is used to estimate the number of instructions in
1755 the unrolled loop. This implementation is a bit simplistic -- the number
1756 of issued prefetch instructions is also affected by unrolling. So,
1757 prefetch_mod and the unroll factor should be taken into account when
1758 determining prefetch_count. Also, the number of insns of the unrolled
1759 loop will usually be significantly smaller than the number of insns of the
1760 original loop * unroll_factor (at least the induction variable increases
1761 and the exit branches will get eliminated), so it might be better to use
1762 tree_estimate_loop_size + estimated_unrolled_size. */
1763 insn_to_prefetch_ratio
= (unroll_factor
* ninsns
) / prefetch_count
;
1764 if (insn_to_prefetch_ratio
< MIN_INSN_TO_PREFETCH_RATIO
)
1766 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1768 "Not prefetching -- instruction to prefetch ratio (%d) too small\n",
1769 insn_to_prefetch_ratio
);
1777 /* Issue prefetch instructions for array references in LOOP. Returns
1778 true if the LOOP was unrolled. */
1781 loop_prefetch_arrays (struct loop
*loop
)
1783 struct mem_ref_group
*refs
;
1784 unsigned ahead
, ninsns
, time
, unroll_factor
;
1785 HOST_WIDE_INT est_niter
;
1786 struct tree_niter_desc desc
;
1787 bool unrolled
= false, no_other_refs
;
1788 unsigned prefetch_count
;
1789 unsigned mem_ref_count
;
1791 if (optimize_loop_nest_for_size_p (loop
))
1793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1794 fprintf (dump_file
, " ignored (cold area)\n");
1798 /* FIXME: the time should be weighted by the probabilities of the blocks in
1800 time
= tree_num_loop_insns (loop
, &eni_time_weights
);
1804 ahead
= (PREFETCH_LATENCY
+ time
- 1) / time
;
1805 est_niter
= estimated_stmt_executions_int (loop
);
1806 if (est_niter
== -1)
1807 est_niter
= max_stmt_executions_int (loop
);
1809 /* Prefetching is not likely to be profitable if the trip count to ahead
1810 ratio is too small. */
1811 if (trip_count_to_ahead_ratio_too_small_p (ahead
, est_niter
))
1814 ninsns
= tree_num_loop_insns (loop
, &eni_size_weights
);
1816 /* Step 1: gather the memory references. */
1817 refs
= gather_memory_references (loop
, &no_other_refs
, &mem_ref_count
);
1819 /* Give up prefetching if the number of memory references in the
1820 loop is not reasonable based on profitablity and compilation time
1822 if (!mem_ref_count_reasonable_p (ninsns
, mem_ref_count
))
1825 /* Step 2: estimate the reuse effects. */
1826 prune_by_reuse (refs
);
1828 if (nothing_to_prefetch_p (refs
))
1831 if (!determine_loop_nest_reuse (loop
, refs
, no_other_refs
))
1834 /* Step 3: determine unroll factor. */
1835 unroll_factor
= determine_unroll_factor (loop
, refs
, ninsns
, &desc
,
1838 /* Estimate prefetch count for the unrolled loop. */
1839 prefetch_count
= estimate_prefetch_count (refs
, unroll_factor
);
1840 if (prefetch_count
== 0)
1843 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1844 fprintf (dump_file
, "Ahead %d, unroll factor %d, trip count "
1845 HOST_WIDE_INT_PRINT_DEC
"\n"
1846 "insn count %d, mem ref count %d, prefetch count %d\n",
1847 ahead
, unroll_factor
, est_niter
,
1848 ninsns
, mem_ref_count
, prefetch_count
);
1850 /* Prefetching is not likely to be profitable if the instruction to prefetch
1851 ratio is too small. */
1852 if (insn_to_prefetch_ratio_too_small_p (ninsns
, prefetch_count
,
1856 mark_nontemporal_stores (loop
, refs
);
1858 /* Step 4: what to prefetch? */
1859 if (!schedule_prefetches (refs
, unroll_factor
, ahead
))
1862 /* Step 5: unroll the loop. TODO -- peeling of first and last few
1863 iterations so that we do not issue superfluous prefetches. */
1864 if (unroll_factor
!= 1)
1866 tree_unroll_loop (loop
, unroll_factor
,
1867 single_dom_exit (loop
), &desc
);
1871 /* Step 6: issue the prefetches. */
1872 issue_prefetches (refs
, unroll_factor
, ahead
);
1875 release_mem_refs (refs
);
1879 /* Issue prefetch instructions for array references in loops. */
1882 tree_ssa_prefetch_arrays (void)
1886 bool unrolled
= false;
1890 /* It is possible to ask compiler for say -mtune=i486 -march=pentium4.
1891 -mtune=i486 causes us having PREFETCH_BLOCK 0, since this is part
1892 of processor costs and i486 does not have prefetch, but
1893 -march=pentium4 causes HAVE_prefetch to be true. Ugh. */
1894 || PREFETCH_BLOCK
== 0)
1897 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1899 fprintf (dump_file
, "Prefetching parameters:\n");
1900 fprintf (dump_file
, " simultaneous prefetches: %d\n",
1901 SIMULTANEOUS_PREFETCHES
);
1902 fprintf (dump_file
, " prefetch latency: %d\n", PREFETCH_LATENCY
);
1903 fprintf (dump_file
, " prefetch block size: %d\n", PREFETCH_BLOCK
);
1904 fprintf (dump_file
, " L1 cache size: %d lines, %d kB\n",
1905 L1_CACHE_SIZE_BYTES
/ L1_CACHE_LINE_SIZE
, L1_CACHE_SIZE
);
1906 fprintf (dump_file
, " L1 cache line size: %d\n", L1_CACHE_LINE_SIZE
);
1907 fprintf (dump_file
, " L2 cache size: %d kB\n", L2_CACHE_SIZE
);
1908 fprintf (dump_file
, " min insn-to-prefetch ratio: %d \n",
1909 MIN_INSN_TO_PREFETCH_RATIO
);
1910 fprintf (dump_file
, " min insn-to-mem ratio: %d \n",
1911 PREFETCH_MIN_INSN_TO_MEM_RATIO
);
1912 fprintf (dump_file
, "\n");
1915 initialize_original_copy_tables ();
1917 if (!builtin_decl_explicit_p (BUILT_IN_PREFETCH
))
1919 tree type
= build_function_type_list (void_type_node
,
1920 const_ptr_type_node
, NULL_TREE
);
1921 tree decl
= add_builtin_function ("__builtin_prefetch", type
,
1922 BUILT_IN_PREFETCH
, BUILT_IN_NORMAL
,
1924 DECL_IS_NOVOPS (decl
) = true;
1925 set_builtin_decl (BUILT_IN_PREFETCH
, decl
, false);
1928 /* We assume that size of cache line is a power of two, so verify this
1930 gcc_assert ((PREFETCH_BLOCK
& (PREFETCH_BLOCK
- 1)) == 0);
1932 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1934 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1935 fprintf (dump_file
, "Processing loop %d:\n", loop
->num
);
1937 unrolled
|= loop_prefetch_arrays (loop
);
1939 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1940 fprintf (dump_file
, "\n\n");
1946 todo_flags
|= TODO_cleanup_cfg
;
1949 free_original_copy_tables ();