2 Copyright (C) 2005 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 2, 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 COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
38 #include "tree-pass.h"
40 #include "insn-config.h"
43 #include "tree-chrec.h"
44 #include "tree-scalar-evolution.h"
47 #include "langhooks.h"
48 #include "tree-inline.h"
49 #include "tree-data-ref.h"
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 (4) 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?
113 -- write and use more general reuse analysis (that could be also used
114 in other cache aimed loop optimizations)
115 -- make it behave sanely together with the prefetches given by user
116 (now we just ignore them; at the very least we should avoid
117 optimizing loops in that user put his own prefetches)
118 -- we assume cache line size alignment of arrays; this could be
121 /* Magic constants follow. These should be replaced by machine specific
124 /* True if write can be prefetched by a read prefetch. */
126 #ifndef WRITE_CAN_USE_READ_PREFETCH
127 #define WRITE_CAN_USE_READ_PREFETCH 1
130 /* True if read can be prefetched by a write prefetch. */
132 #ifndef READ_CAN_USE_WRITE_PREFETCH
133 #define READ_CAN_USE_WRITE_PREFETCH 0
136 /* The size of the block loaded by a single prefetch. Usually, this is
137 the same as cache line size (at the moment, we only consider one level
138 of cache hierarchy). */
140 #ifndef PREFETCH_BLOCK
141 #define PREFETCH_BLOCK L1_CACHE_LINE_SIZE
144 /* Do we have a forward hardware sequential prefetching? */
146 #ifndef HAVE_FORWARD_PREFETCH
147 #define HAVE_FORWARD_PREFETCH 0
150 /* Do we have a backward hardware sequential prefetching? */
152 #ifndef HAVE_BACKWARD_PREFETCH
153 #define HAVE_BACKWARD_PREFETCH 0
156 /* In some cases we are only able to determine that there is a certain
157 probability that the two accesses hit the same cache line. In this
158 case, we issue the prefetches for both of them if this probability
159 is less then (1000 - ACCEPTABLE_MISS_RATE) promile. */
161 #ifndef ACCEPTABLE_MISS_RATE
162 #define ACCEPTABLE_MISS_RATE 50
165 #ifndef HAVE_prefetch
166 #define HAVE_prefetch 0
169 #define L1_CACHE_SIZE_BYTES ((unsigned) (L1_CACHE_SIZE * L1_CACHE_LINE_SIZE))
170 /* TODO: Add parameter to specify L2 cache size. */
171 #define L2_CACHE_SIZE_BYTES (8 * L1_CACHE_SIZE_BYTES)
173 /* We consider a memory access nontemporal if it is not reused sooner than
174 after L2_CACHE_SIZE_BYTES of memory are accessed. However, we ignore
175 accesses closer than L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
176 so that we use nontemporal prefetches e.g. if single memory location
177 is accessed several times in a single iteration of the loop. */
178 #define NONTEMPORAL_FRACTION 16
180 /* The group of references between that reuse may occur. */
184 tree base
; /* Base of the reference. */
185 HOST_WIDE_INT step
; /* Step of the reference. */
186 struct mem_ref
*refs
; /* References in the group. */
187 struct mem_ref_group
*next
; /* Next group of references. */
190 /* Assigned to PREFETCH_BEFORE when all iterations are to be prefetched. */
192 #define PREFETCH_ALL (~(unsigned HOST_WIDE_INT) 0)
194 /* The memory reference. */
198 tree stmt
; /* Statement in that the reference appears. */
199 tree mem
; /* The reference. */
200 HOST_WIDE_INT delta
; /* Constant offset of the reference. */
201 bool write_p
; /* Is it a write? */
202 struct mem_ref_group
*group
; /* The group of references it belongs to. */
203 unsigned HOST_WIDE_INT prefetch_mod
;
204 /* Prefetch only each PREFETCH_MOD-th
206 unsigned HOST_WIDE_INT prefetch_before
;
207 /* Prefetch only first PREFETCH_BEFORE
209 unsigned reuse_distance
; /* The amount of data accessed before the first
210 reuse of this value. */
211 bool issue_prefetch_p
; /* Should we really issue the prefetch? */
212 struct mem_ref
*next
; /* The next reference in the group. */
215 /* Dumps information about reference REF to FILE. */
218 dump_mem_ref (FILE *file
, struct mem_ref
*ref
)
220 fprintf (file
, "Reference %p:\n", (void *) ref
);
222 fprintf (file
, " group %p (base ", (void *) ref
->group
);
223 print_generic_expr (file
, ref
->group
->base
, TDF_SLIM
);
224 fprintf (file
, ", step ");
225 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, ref
->group
->step
);
226 fprintf (file
, ")\n");
228 fprintf (file
, " delta ");
229 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, ref
->delta
);
230 fprintf (file
, "\n");
232 fprintf (file
, " %s\n", ref
->write_p
? "write" : "read");
234 fprintf (file
, "\n");
237 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
240 static struct mem_ref_group
*
241 find_or_create_group (struct mem_ref_group
**groups
, tree base
,
244 struct mem_ref_group
*group
;
246 for (; *groups
; groups
= &(*groups
)->next
)
248 if ((*groups
)->step
== step
249 && operand_equal_p ((*groups
)->base
, base
, 0))
252 /* Keep the list of groups sorted by decreasing step. */
253 if ((*groups
)->step
< step
)
257 group
= XNEW (struct mem_ref_group
);
261 group
->next
= *groups
;
267 /* Records a memory reference MEM in GROUP with offset DELTA and write status
268 WRITE_P. The reference occurs in statement STMT. */
271 record_ref (struct mem_ref_group
*group
, tree stmt
, tree mem
,
272 HOST_WIDE_INT delta
, bool write_p
)
274 struct mem_ref
**aref
;
276 /* Do not record the same address twice. */
277 for (aref
= &group
->refs
; *aref
; aref
= &(*aref
)->next
)
279 /* It does not have to be possible for write reference to reuse the read
280 prefetch, or vice versa. */
281 if (!WRITE_CAN_USE_READ_PREFETCH
283 && !(*aref
)->write_p
)
285 if (!READ_CAN_USE_WRITE_PREFETCH
290 if ((*aref
)->delta
== delta
)
294 (*aref
) = XNEW (struct mem_ref
);
295 (*aref
)->stmt
= stmt
;
297 (*aref
)->delta
= delta
;
298 (*aref
)->write_p
= write_p
;
299 (*aref
)->prefetch_before
= PREFETCH_ALL
;
300 (*aref
)->prefetch_mod
= 1;
301 (*aref
)->reuse_distance
= 0;
302 (*aref
)->issue_prefetch_p
= false;
303 (*aref
)->group
= group
;
304 (*aref
)->next
= NULL
;
306 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
307 dump_mem_ref (dump_file
, *aref
);
310 /* Release memory references in GROUPS. */
313 release_mem_refs (struct mem_ref_group
*groups
)
315 struct mem_ref_group
*next_g
;
316 struct mem_ref
*ref
, *next_r
;
318 for (; groups
; groups
= next_g
)
320 next_g
= groups
->next
;
321 for (ref
= groups
->refs
; ref
; ref
= next_r
)
330 /* A structure used to pass arguments to idx_analyze_ref. */
334 struct loop
*loop
; /* Loop of the reference. */
335 tree stmt
; /* Statement of the reference. */
336 HOST_WIDE_INT
*step
; /* Step of the memory reference. */
337 HOST_WIDE_INT
*delta
; /* Offset of the memory reference. */
340 /* Analyzes a single INDEX of a memory reference to obtain information
341 described at analyze_ref. Callback for for_each_index. */
344 idx_analyze_ref (tree base
, tree
*index
, void *data
)
346 struct ar_data
*ar_data
= (struct ar_data
*) data
;
347 tree ibase
, step
, stepsize
;
348 HOST_WIDE_INT istep
, idelta
= 0, imult
= 1;
351 if (TREE_CODE (base
) == MISALIGNED_INDIRECT_REF
352 || TREE_CODE (base
) == ALIGN_INDIRECT_REF
)
355 if (!simple_iv (ar_data
->loop
, ar_data
->stmt
, *index
, &iv
, false))
360 if (!cst_and_fits_in_hwi (step
))
362 istep
= int_cst_value (step
);
364 if (TREE_CODE (ibase
) == PLUS_EXPR
365 && cst_and_fits_in_hwi (TREE_OPERAND (ibase
, 1)))
367 idelta
= int_cst_value (TREE_OPERAND (ibase
, 1));
368 ibase
= TREE_OPERAND (ibase
, 0);
370 if (cst_and_fits_in_hwi (ibase
))
372 idelta
+= int_cst_value (ibase
);
373 ibase
= build_int_cst (TREE_TYPE (ibase
), 0);
376 if (TREE_CODE (base
) == ARRAY_REF
)
378 stepsize
= array_ref_element_size (base
);
379 if (!cst_and_fits_in_hwi (stepsize
))
381 imult
= int_cst_value (stepsize
);
387 *ar_data
->step
+= istep
;
388 *ar_data
->delta
+= idelta
;
394 /* Tries to express REF_P in shape &BASE + STEP * iter + DELTA, where DELTA and
395 STEP are integer constants and iter is number of iterations of LOOP. The
396 reference occurs in statement STMT. Strips nonaddressable component
397 references from REF_P. */
400 analyze_ref (struct loop
*loop
, tree
*ref_p
, tree
*base
,
401 HOST_WIDE_INT
*step
, HOST_WIDE_INT
*delta
,
404 struct ar_data ar_data
;
406 HOST_WIDE_INT bit_offset
;
412 /* First strip off the component references. Ignore bitfields. */
413 if (TREE_CODE (ref
) == COMPONENT_REF
414 && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref
, 1)))
415 ref
= TREE_OPERAND (ref
, 0);
419 for (; TREE_CODE (ref
) == COMPONENT_REF
; ref
= TREE_OPERAND (ref
, 0))
421 off
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
422 bit_offset
= TREE_INT_CST_LOW (off
);
423 gcc_assert (bit_offset
% BITS_PER_UNIT
== 0);
425 *delta
+= bit_offset
/ BITS_PER_UNIT
;
428 *base
= unshare_expr (ref
);
432 ar_data
.delta
= delta
;
433 return for_each_index (base
, idx_analyze_ref
, &ar_data
);
436 /* Record a memory reference REF to the list REFS. The reference occurs in
437 LOOP in statement STMT and it is write if WRITE_P. */
440 gather_memory_references_ref (struct loop
*loop
, struct mem_ref_group
**refs
,
441 tree ref
, bool write_p
, tree stmt
)
444 HOST_WIDE_INT step
, delta
;
445 struct mem_ref_group
*agrp
;
447 if (!analyze_ref (loop
, &ref
, &base
, &step
, &delta
, stmt
))
450 /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
451 are integer constants. */
452 agrp
= find_or_create_group (refs
, base
, step
);
453 record_ref (agrp
, stmt
, ref
, delta
, write_p
);
456 /* Record the suitable memory references in LOOP. */
458 static struct mem_ref_group
*
459 gather_memory_references (struct loop
*loop
)
461 basic_block
*body
= get_loop_body_in_dom_order (loop
);
464 block_stmt_iterator bsi
;
466 struct mem_ref_group
*refs
= NULL
;
468 /* Scan the loop body in order, so that the former references precede the
470 for (i
= 0; i
< loop
->num_nodes
; i
++)
473 if (bb
->loop_father
!= loop
)
476 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
478 stmt
= bsi_stmt (bsi
);
479 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
482 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
483 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
485 if (REFERENCE_CLASS_P (rhs
))
486 gather_memory_references_ref (loop
, &refs
, rhs
, false, stmt
);
487 if (REFERENCE_CLASS_P (lhs
))
488 gather_memory_references_ref (loop
, &refs
, lhs
, true, stmt
);
496 /* Prune the prefetch candidate REF using the self-reuse. */
499 prune_ref_by_self_reuse (struct mem_ref
*ref
)
501 HOST_WIDE_INT step
= ref
->group
->step
;
502 bool backward
= step
< 0;
506 /* Prefetch references to invariant address just once. */
507 ref
->prefetch_before
= 1;
514 if (step
> PREFETCH_BLOCK
)
517 if ((backward
&& HAVE_BACKWARD_PREFETCH
)
518 || (!backward
&& HAVE_FORWARD_PREFETCH
))
520 ref
->prefetch_before
= 1;
524 ref
->prefetch_mod
= PREFETCH_BLOCK
/ step
;
527 /* Divides X by BY, rounding down. */
530 ddown (HOST_WIDE_INT x
, unsigned HOST_WIDE_INT by
)
537 return (x
+ by
- 1) / by
;
540 /* Prune the prefetch candidate REF using the reuse with BY.
541 If BY_IS_BEFORE is true, BY is before REF in the loop. */
544 prune_ref_by_group_reuse (struct mem_ref
*ref
, struct mem_ref
*by
,
547 HOST_WIDE_INT step
= ref
->group
->step
;
548 bool backward
= step
< 0;
549 HOST_WIDE_INT delta_r
= ref
->delta
, delta_b
= by
->delta
;
550 HOST_WIDE_INT delta
= delta_b
- delta_r
;
551 HOST_WIDE_INT hit_from
;
552 unsigned HOST_WIDE_INT prefetch_before
, prefetch_block
;
556 /* If the references has the same address, only prefetch the
559 ref
->prefetch_before
= 0;
566 /* If the reference addresses are invariant and fall into the
567 same cache line, prefetch just the first one. */
571 if (ddown (ref
->delta
, PREFETCH_BLOCK
)
572 != ddown (by
->delta
, PREFETCH_BLOCK
))
575 ref
->prefetch_before
= 0;
579 /* Only prune the reference that is behind in the array. */
585 /* Transform the data so that we may assume that the accesses
589 delta_r
= PREFETCH_BLOCK
- 1 - delta_r
;
590 delta_b
= PREFETCH_BLOCK
- 1 - delta_b
;
598 /* Check whether the two references are likely to hit the same cache
599 line, and how distant the iterations in that it occurs are from
602 if (step
<= PREFETCH_BLOCK
)
604 /* The accesses are sure to meet. Let us check when. */
605 hit_from
= ddown (delta_b
, PREFETCH_BLOCK
) * PREFETCH_BLOCK
;
606 prefetch_before
= (hit_from
- delta_r
+ step
- 1) / step
;
608 if (prefetch_before
< ref
->prefetch_before
)
609 ref
->prefetch_before
= prefetch_before
;
614 /* A more complicated case. First let us ensure that size of cache line
615 and step are coprime (here we assume that PREFETCH_BLOCK is a power
617 prefetch_block
= PREFETCH_BLOCK
;
618 while ((step
& 1) == 0
619 && prefetch_block
> 1)
622 prefetch_block
>>= 1;
626 /* Now step > prefetch_block, and step and prefetch_block are coprime.
627 Determine the probability that the accesses hit the same cache line. */
629 prefetch_before
= delta
/ step
;
631 if ((unsigned HOST_WIDE_INT
) delta
632 <= (prefetch_block
* ACCEPTABLE_MISS_RATE
/ 1000))
634 if (prefetch_before
< ref
->prefetch_before
)
635 ref
->prefetch_before
= prefetch_before
;
640 /* Try also the following iteration. */
642 delta
= step
- delta
;
643 if ((unsigned HOST_WIDE_INT
) delta
644 <= (prefetch_block
* ACCEPTABLE_MISS_RATE
/ 1000))
646 if (prefetch_before
< ref
->prefetch_before
)
647 ref
->prefetch_before
= prefetch_before
;
652 /* The ref probably does not reuse by. */
656 /* Prune the prefetch candidate REF using the reuses with other references
660 prune_ref_by_reuse (struct mem_ref
*ref
, struct mem_ref
*refs
)
662 struct mem_ref
*prune_by
;
665 prune_ref_by_self_reuse (ref
);
667 for (prune_by
= refs
; prune_by
; prune_by
= prune_by
->next
)
675 if (!WRITE_CAN_USE_READ_PREFETCH
677 && !prune_by
->write_p
)
679 if (!READ_CAN_USE_WRITE_PREFETCH
681 && prune_by
->write_p
)
684 prune_ref_by_group_reuse (ref
, prune_by
, before
);
688 /* Prune the prefetch candidates in GROUP using the reuse analysis. */
691 prune_group_by_reuse (struct mem_ref_group
*group
)
693 struct mem_ref
*ref_pruned
;
695 for (ref_pruned
= group
->refs
; ref_pruned
; ref_pruned
= ref_pruned
->next
)
697 prune_ref_by_reuse (ref_pruned
, group
->refs
);
699 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
701 fprintf (dump_file
, "Reference %p:", (void *) ref_pruned
);
703 if (ref_pruned
->prefetch_before
== PREFETCH_ALL
704 && ref_pruned
->prefetch_mod
== 1)
705 fprintf (dump_file
, " no restrictions");
706 else if (ref_pruned
->prefetch_before
== 0)
707 fprintf (dump_file
, " do not prefetch");
708 else if (ref_pruned
->prefetch_before
<= ref_pruned
->prefetch_mod
)
709 fprintf (dump_file
, " prefetch once");
712 if (ref_pruned
->prefetch_before
!= PREFETCH_ALL
)
714 fprintf (dump_file
, " prefetch before ");
715 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
716 ref_pruned
->prefetch_before
);
718 if (ref_pruned
->prefetch_mod
!= 1)
720 fprintf (dump_file
, " prefetch mod ");
721 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
722 ref_pruned
->prefetch_mod
);
725 fprintf (dump_file
, "\n");
730 /* Prune the list of prefetch candidates GROUPS using the reuse analysis. */
733 prune_by_reuse (struct mem_ref_group
*groups
)
735 for (; groups
; groups
= groups
->next
)
736 prune_group_by_reuse (groups
);
739 /* Returns true if we should issue prefetch for REF. */
742 should_issue_prefetch_p (struct mem_ref
*ref
)
744 /* For now do not issue prefetches for only first few of the
746 if (ref
->prefetch_before
!= PREFETCH_ALL
)
752 /* Decide which of the prefetch candidates in GROUPS to prefetch.
753 AHEAD is the number of iterations to prefetch ahead (which corresponds
754 to the number of simultaneous instances of one prefetch running at a
755 time). UNROLL_FACTOR is the factor by that the loop is going to be
756 unrolled. Returns true if there is anything to prefetch. */
759 schedule_prefetches (struct mem_ref_group
*groups
, unsigned unroll_factor
,
762 unsigned remaining_prefetch_slots
, n_prefetches
, prefetch_slots
;
763 unsigned slots_per_prefetch
;
767 /* At most SIMULTANEOUS_PREFETCHES should be running at the same time. */
768 remaining_prefetch_slots
= SIMULTANEOUS_PREFETCHES
;
770 /* The prefetch will run for AHEAD iterations of the original loop, i.e.,
771 AHEAD / UNROLL_FACTOR iterations of the unrolled loop. In each iteration,
772 it will need a prefetch slot. */
773 slots_per_prefetch
= (ahead
+ unroll_factor
/ 2) / unroll_factor
;
774 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
775 fprintf (dump_file
, "Each prefetch instruction takes %u prefetch slots.\n",
778 /* For now we just take memory references one by one and issue
779 prefetches for as many as possible. The groups are sorted
780 starting with the largest step, since the references with
781 large step are more likely to cause many cache misses. */
783 for (; groups
; groups
= groups
->next
)
784 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
786 if (!should_issue_prefetch_p (ref
))
789 /* If we need to prefetch the reference each PREFETCH_MOD iterations,
790 and we unroll the loop UNROLL_FACTOR times, we need to insert
791 ceil (UNROLL_FACTOR / PREFETCH_MOD) instructions in each
793 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
794 / ref
->prefetch_mod
);
795 prefetch_slots
= n_prefetches
* slots_per_prefetch
;
797 /* If more than half of the prefetches would be lost anyway, do not
798 issue the prefetch. */
799 if (2 * remaining_prefetch_slots
< prefetch_slots
)
802 ref
->issue_prefetch_p
= true;
804 if (remaining_prefetch_slots
<= prefetch_slots
)
806 remaining_prefetch_slots
-= prefetch_slots
;
813 /* Determine whether there is any reference suitable for prefetching
817 anything_to_prefetch_p (struct mem_ref_group
*groups
)
821 for (; groups
; groups
= groups
->next
)
822 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
823 if (should_issue_prefetch_p (ref
))
829 /* Issue prefetches for the reference REF into loop as decided before.
830 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR
831 is the factor by which LOOP was unrolled. */
834 issue_prefetch_ref (struct mem_ref
*ref
, unsigned unroll_factor
, unsigned ahead
)
837 tree addr
, addr_base
, prefetch
, write_p
, local
;
838 block_stmt_iterator bsi
;
839 unsigned n_prefetches
, ap
;
840 bool nontemporal
= ref
->reuse_distance
>= L2_CACHE_SIZE_BYTES
;
842 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
843 fprintf (dump_file
, "Issued%s prefetch for %p.\n",
844 nontemporal
? " nontemporal" : "",
847 bsi
= bsi_for_stmt (ref
->stmt
);
849 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
850 / ref
->prefetch_mod
);
851 addr_base
= build_fold_addr_expr_with_type (ref
->mem
, ptr_type_node
);
852 addr_base
= force_gimple_operand_bsi (&bsi
, unshare_expr (addr_base
), true, NULL
);
853 write_p
= ref
->write_p
? integer_one_node
: integer_zero_node
;
854 local
= build_int_cst (integer_type_node
, nontemporal
? 0 : 3);
856 for (ap
= 0; ap
< n_prefetches
; ap
++)
858 /* Determine the address to prefetch. */
859 delta
= (ahead
+ ap
* ref
->prefetch_mod
) * ref
->group
->step
;
860 addr
= fold_build2 (PLUS_EXPR
, ptr_type_node
,
861 addr_base
, build_int_cst (ptr_type_node
, delta
));
862 addr
= force_gimple_operand_bsi (&bsi
, unshare_expr (addr
), true, NULL
);
864 /* Create the prefetch instruction. */
865 prefetch
= build_call_expr (built_in_decls
[BUILT_IN_PREFETCH
],
866 3, addr
, write_p
, local
);
867 bsi_insert_before (&bsi
, prefetch
, BSI_SAME_STMT
);
871 /* Issue prefetches for the references in GROUPS into loop as decided before.
872 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR is the
873 factor by that LOOP was unrolled. */
876 issue_prefetches (struct mem_ref_group
*groups
,
877 unsigned unroll_factor
, unsigned ahead
)
881 for (; groups
; groups
= groups
->next
)
882 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
883 if (ref
->issue_prefetch_p
)
884 issue_prefetch_ref (ref
, unroll_factor
, ahead
);
887 /* Determines whether we can profitably unroll LOOP FACTOR times, and if
888 this is the case, fill in DESC by the description of number of
892 should_unroll_loop_p (struct loop
*loop
, struct tree_niter_desc
*desc
,
895 if (!can_unroll_loop_p (loop
, factor
, desc
))
898 /* We only consider loops without control flow for unrolling. This is not
899 a hard restriction -- tree_unroll_loop works with arbitrary loops
900 as well; but the unrolling/prefetching is usually more profitable for
901 loops consisting of a single basic block, and we want to limit the
903 if (loop
->num_nodes
> 2)
909 /* Determine the coefficient by that unroll LOOP, from the information
910 contained in the list of memory references REFS. Description of
911 umber of iterations of LOOP is stored to DESC. NINSNS is the number of
912 insns of the LOOP. EST_NITER is the estimated number of iterations of
913 the loop, or -1 if no estimate is available. */
916 determine_unroll_factor (struct loop
*loop
, struct mem_ref_group
*refs
,
917 unsigned ninsns
, struct tree_niter_desc
*desc
,
918 HOST_WIDE_INT est_niter
)
920 unsigned upper_bound
;
921 unsigned nfactor
, factor
, mod_constraint
;
922 struct mem_ref_group
*agp
;
925 /* First check whether the loop is not too large to unroll. We ignore
926 PARAM_MAX_UNROLL_TIMES, because for small loops, it prevented us
927 from unrolling them enough to make exactly one cache line covered by each
928 iteration. Also, the goal of PARAM_MAX_UNROLL_TIMES is to prevent
929 us from unrolling the loops too many times in cases where we only expect
930 gains from better scheduling and decreasing loop overhead, which is not
932 upper_bound
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / ninsns
;
934 /* If we unrolled the loop more times than it iterates, the unrolled version
935 of the loop would be never entered. */
936 if (est_niter
>= 0 && est_niter
< (HOST_WIDE_INT
) upper_bound
)
937 upper_bound
= est_niter
;
939 if (upper_bound
<= 1)
942 /* Choose the factor so that we may prefetch each cache just once,
943 but bound the unrolling by UPPER_BOUND. */
945 for (agp
= refs
; agp
; agp
= agp
->next
)
946 for (ref
= agp
->refs
; ref
; ref
= ref
->next
)
947 if (should_issue_prefetch_p (ref
))
949 mod_constraint
= ref
->prefetch_mod
;
950 nfactor
= least_common_multiple (mod_constraint
, factor
);
951 if (nfactor
<= upper_bound
)
955 if (!should_unroll_loop_p (loop
, desc
, factor
))
961 /* Returns the total volume of the memory references REFS, taking into account
962 reuses in the innermost loop and cache line size. TODO -- we should also
963 take into account reuses across the iterations of the loops in the loop
967 volume_of_references (struct mem_ref_group
*refs
)
970 struct mem_ref_group
*gr
;
973 for (gr
= refs
; gr
; gr
= gr
->next
)
974 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
976 /* Almost always reuses another value? */
977 if (ref
->prefetch_before
!= PREFETCH_ALL
)
980 /* If several iterations access the same cache line, use the size of
981 the line divided by this number. Otherwise, a cache line is
982 accessed in each iteration. TODO -- in the latter case, we should
983 take the size of the reference into account, rounding it up on cache
984 line size multiple. */
985 volume
+= L1_CACHE_LINE_SIZE
/ ref
->prefetch_mod
;
990 /* Returns the volume of memory references accessed across VEC iterations of
991 loops, whose sizes are described in the LOOP_SIZES array. N is the number
992 of the loops in the nest (length of VEC and LOOP_SIZES vectors). */
995 volume_of_dist_vector (lambda_vector vec
, unsigned *loop_sizes
, unsigned n
)
999 for (i
= 0; i
< n
; i
++)
1006 gcc_assert (vec
[i
] > 0);
1008 /* We ignore the parts of the distance vector in subloops, since usually
1009 the numbers of iterations are much smaller. */
1010 return loop_sizes
[i
] * vec
[i
];
1013 /* Add the steps of ACCESS_FN multiplied by STRIDE to the array STRIDE
1014 at the position corresponding to the loop of the step. N is the depth
1015 of the considered loop nest, and, LOOP is its innermost loop. */
1018 add_subscript_strides (tree access_fn
, unsigned stride
,
1019 HOST_WIDE_INT
*strides
, unsigned n
, struct loop
*loop
)
1023 HOST_WIDE_INT astep
;
1024 unsigned min_depth
= loop_depth (loop
) - n
;
1026 while (TREE_CODE (access_fn
) == POLYNOMIAL_CHREC
)
1028 aloop
= get_chrec_loop (access_fn
);
1029 step
= CHREC_RIGHT (access_fn
);
1030 access_fn
= CHREC_LEFT (access_fn
);
1032 if ((unsigned) loop_depth (aloop
) <= min_depth
)
1035 if (host_integerp (step
, 0))
1036 astep
= tree_low_cst (step
, 0);
1038 astep
= L1_CACHE_LINE_SIZE
;
1040 strides
[n
- 1 - loop_depth (loop
) + loop_depth (aloop
)] += astep
* stride
;
1045 /* Returns the volume of memory references accessed between two consecutive
1046 self-reuses of the reference DR. We consider the subscripts of DR in N
1047 loops, and LOOP_SIZES contains the volumes of accesses in each of the
1048 loops. LOOP is the innermost loop of the current loop nest. */
1051 self_reuse_distance (data_reference_p dr
, unsigned *loop_sizes
, unsigned n
,
1054 tree stride
, access_fn
;
1055 HOST_WIDE_INT
*strides
, astride
;
1056 VEC (tree
, heap
) *access_fns
;
1057 tree ref
= DR_REF (dr
);
1058 unsigned i
, ret
= ~0u;
1060 /* In the following example:
1062 for (i = 0; i < N; i++)
1063 for (j = 0; j < N; j++)
1065 the same cache line is accessed each N steps (except if the change from
1066 i to i + 1 crosses the boundary of the cache line). Thus, for self-reuse,
1067 we cannot rely purely on the results of the data dependence analysis.
1069 Instead, we compute the stride of the reference in each loop, and consider
1070 the innermost loop in that the stride is less than cache size. */
1072 strides
= XCNEWVEC (HOST_WIDE_INT
, n
);
1073 access_fns
= DR_ACCESS_FNS (dr
);
1075 for (i
= 0; VEC_iterate (tree
, access_fns
, i
, access_fn
); i
++)
1077 /* Keep track of the reference corresponding to the subscript, so that we
1079 while (handled_component_p (ref
) && TREE_CODE (ref
) != ARRAY_REF
)
1080 ref
= TREE_OPERAND (ref
, 0);
1082 if (TREE_CODE (ref
) == ARRAY_REF
)
1084 stride
= TYPE_SIZE_UNIT (TREE_TYPE (ref
));
1085 if (host_integerp (stride
, 1))
1086 astride
= tree_low_cst (stride
, 1);
1088 astride
= L1_CACHE_LINE_SIZE
;
1090 ref
= TREE_OPERAND (ref
, 0);
1095 add_subscript_strides (access_fn
, astride
, strides
, n
, loop
);
1098 for (i
= n
; i
-- > 0; )
1100 unsigned HOST_WIDE_INT s
;
1102 s
= strides
[i
] < 0 ? -strides
[i
] : strides
[i
];
1104 if (s
< (unsigned) L1_CACHE_LINE_SIZE
1106 > (unsigned) (L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)))
1108 ret
= loop_sizes
[i
];
1117 /* Determines the distance till the first reuse of each reference in REFS
1118 in the loop nest of LOOP. */
1121 determine_loop_nest_reuse (struct loop
*loop
, struct mem_ref_group
*refs
)
1123 struct loop
*nest
, *aloop
;
1124 VEC (data_reference_p
, heap
) *datarefs
= NULL
;
1125 VEC (ddr_p
, heap
) *dependences
= NULL
;
1126 struct mem_ref_group
*gr
;
1127 struct mem_ref
*ref
;
1128 VEC (loop_p
, heap
) *vloops
= NULL
;
1129 unsigned *loop_data_size
;
1131 unsigned volume
, dist
, adist
;
1133 data_reference_p dr
;
1139 /* Find the outermost loop of the loop nest of loop (we require that
1140 there are no sibling loops inside the nest). */
1144 aloop
= loop_outer (nest
);
1146 if (aloop
== current_loops
->tree_root
1147 || aloop
->inner
->next
)
1153 /* For each loop, determine the amount of data accessed in each iteration.
1154 We use this to estimate whether the reference is evicted from the
1155 cache before its reuse. */
1156 find_loop_nest (nest
, &vloops
);
1157 n
= VEC_length (loop_p
, vloops
);
1158 loop_data_size
= XNEWVEC (unsigned, n
);
1159 volume
= volume_of_references (refs
);
1163 loop_data_size
[i
] = volume
;
1164 /* Bound the volume by the L2 cache size, since above this bound,
1165 all dependence distances are equivalent. */
1166 if (volume
> L2_CACHE_SIZE_BYTES
)
1169 aloop
= VEC_index (loop_p
, vloops
, i
);
1170 vol
= estimated_loop_iterations_int (aloop
, false);
1172 vol
= expected_loop_iterations (aloop
);
1176 /* Prepare the references in the form suitable for data dependence
1177 analysis. We ignore unanalysable data references (the results
1178 are used just as a heuristics to estimate temporality of the
1179 references, hence we do not need to worry about correctness). */
1180 for (gr
= refs
; gr
; gr
= gr
->next
)
1181 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1183 dr
= create_data_ref (nest
, ref
->mem
, ref
->stmt
, !ref
->write_p
);
1187 ref
->reuse_distance
= volume
;
1189 VEC_safe_push (data_reference_p
, heap
, datarefs
, dr
);
1193 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
1195 dist
= self_reuse_distance (dr
, loop_data_size
, n
, loop
);
1197 if (ref
->reuse_distance
> dist
)
1198 ref
->reuse_distance
= dist
;
1201 compute_all_dependences (datarefs
, &dependences
, vloops
, true);
1203 for (i
= 0; VEC_iterate (ddr_p
, dependences
, i
, dep
); i
++)
1205 if (DDR_ARE_DEPENDENT (dep
) == chrec_known
)
1208 if (DDR_ARE_DEPENDENT (dep
) == chrec_dont_know
1209 || DDR_NUM_DIST_VECTS (dep
) == 0)
1211 /* If the dependence cannot be analysed, assume that there might be
1217 /* The distance vectors are normalised to be always lexicographically
1218 positive, hence we cannot tell just from them whether DDR_A comes
1219 before DDR_B or vice versa. However, it is not important,
1220 anyway -- if DDR_A is close to DDR_B, then it is either reused in
1221 DDR_B (and it is not nontemporal), or it reuses the value of DDR_B
1222 in cache (and marking it as nontemporal would not affect
1226 for (j
= 0; j
< DDR_NUM_DIST_VECTS (dep
); j
++)
1228 adist
= volume_of_dist_vector (DDR_DIST_VECT (dep
, j
),
1231 /* Ignore accesses closer than
1232 L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
1233 so that we use nontemporal prefetches e.g. if single memory
1234 location is accessed several times in a single iteration of
1236 if (adist
< L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)
1244 ref
= DDR_A (dep
)->aux
;
1245 if (ref
->reuse_distance
> dist
)
1246 ref
->reuse_distance
= dist
;
1247 ref
= DDR_B (dep
)->aux
;
1248 if (ref
->reuse_distance
> dist
)
1249 ref
->reuse_distance
= dist
;
1252 free_dependence_relations (dependences
);
1253 free_data_refs (datarefs
);
1254 free (loop_data_size
);
1256 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1258 fprintf (dump_file
, "Reuse distances:\n");
1259 for (gr
= refs
; gr
; gr
= gr
->next
)
1260 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1261 fprintf (dump_file
, " ref %p distance %u\n",
1262 (void *) ref
, ref
->reuse_distance
);
1266 /* Issue prefetch instructions for array references in LOOP. Returns
1267 true if the LOOP was unrolled. */
1270 loop_prefetch_arrays (struct loop
*loop
)
1272 struct mem_ref_group
*refs
;
1273 unsigned ahead
, ninsns
, time
, unroll_factor
;
1274 HOST_WIDE_INT est_niter
;
1275 struct tree_niter_desc desc
;
1276 bool unrolled
= false;
1278 if (!maybe_hot_bb_p (loop
->header
))
1280 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1281 fprintf (dump_file
, " ignored (cold area)\n");
1285 /* Step 1: gather the memory references. */
1286 refs
= gather_memory_references (loop
);
1288 /* Step 2: estimate the reuse effects. */
1289 prune_by_reuse (refs
);
1291 if (!anything_to_prefetch_p (refs
))
1294 determine_loop_nest_reuse (loop
, refs
);
1296 /* Step 3: determine the ahead and unroll factor. */
1298 /* FIXME: the time should be weighted by the probabilities of the blocks in
1300 time
= tree_num_loop_insns (loop
, &eni_time_weights
);
1301 ahead
= (PREFETCH_LATENCY
+ time
- 1) / time
;
1302 est_niter
= estimated_loop_iterations_int (loop
, false);
1304 /* The prefetches will run for AHEAD iterations of the original loop. Unless
1305 the loop rolls at least AHEAD times, prefetching the references does not
1307 if (est_niter
>= 0 && est_niter
<= (HOST_WIDE_INT
) ahead
)
1309 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1311 "Not prefetching -- loop estimated to roll only %d times\n",
1316 ninsns
= tree_num_loop_insns (loop
, &eni_size_weights
);
1317 unroll_factor
= determine_unroll_factor (loop
, refs
, ninsns
, &desc
,
1319 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1320 fprintf (dump_file
, "Ahead %d, unroll factor %d\n", ahead
, unroll_factor
);
1322 /* Step 4: what to prefetch? */
1323 if (!schedule_prefetches (refs
, unroll_factor
, ahead
))
1326 /* Step 5: unroll the loop. TODO -- peeling of first and last few
1327 iterations so that we do not issue superfluous prefetches. */
1328 if (unroll_factor
!= 1)
1330 tree_unroll_loop (loop
, unroll_factor
,
1331 single_dom_exit (loop
), &desc
);
1335 /* Step 6: issue the prefetches. */
1336 issue_prefetches (refs
, unroll_factor
, ahead
);
1339 release_mem_refs (refs
);
1343 /* Issue prefetch instructions for array references in loops. */
1346 tree_ssa_prefetch_arrays (void)
1350 bool unrolled
= false;
1354 /* It is possible to ask compiler for say -mtune=i486 -march=pentium4.
1355 -mtune=i486 causes us having PREFETCH_BLOCK 0, since this is part
1356 of processor costs and i486 does not have prefetch, but
1357 -march=pentium4 causes HAVE_prefetch to be true. Ugh. */
1358 || PREFETCH_BLOCK
== 0)
1361 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1363 fprintf (dump_file
, "Prefetching parameters:\n");
1364 fprintf (dump_file
, " simultaneous prefetches: %d\n",
1365 SIMULTANEOUS_PREFETCHES
);
1366 fprintf (dump_file
, " prefetch latency: %d\n", PREFETCH_LATENCY
);
1367 fprintf (dump_file
, " prefetch block size: %d\n", PREFETCH_BLOCK
);
1368 fprintf (dump_file
, " L1 cache size: %d lines, %d bytes\n",
1369 L1_CACHE_SIZE
, L1_CACHE_SIZE_BYTES
);
1370 fprintf (dump_file
, " L1 cache line size: %d\n", L1_CACHE_LINE_SIZE
);
1371 fprintf (dump_file
, " L2 cache size: %d bytes\n", L2_CACHE_SIZE_BYTES
);
1372 fprintf (dump_file
, "\n");
1375 initialize_original_copy_tables ();
1377 if (!built_in_decls
[BUILT_IN_PREFETCH
])
1379 tree type
= build_function_type (void_type_node
,
1380 tree_cons (NULL_TREE
,
1381 const_ptr_type_node
,
1383 tree decl
= add_builtin_function ("__builtin_prefetch", type
,
1384 BUILT_IN_PREFETCH
, BUILT_IN_NORMAL
,
1386 DECL_IS_NOVOPS (decl
) = true;
1387 built_in_decls
[BUILT_IN_PREFETCH
] = decl
;
1390 /* We assume that size of cache line is a power of two, so verify this
1392 gcc_assert ((PREFETCH_BLOCK
& (PREFETCH_BLOCK
- 1)) == 0);
1394 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1396 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1397 fprintf (dump_file
, "Processing loop %d:\n", loop
->num
);
1399 unrolled
|= loop_prefetch_arrays (loop
);
1401 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1402 fprintf (dump_file
, "\n\n");
1408 todo_flags
|= TODO_cleanup_cfg
;
1411 free_original_copy_tables ();