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"
50 /* This pass inserts prefetch instructions to optimize cache usage during
51 accesses to arrays in loops. It processes loops sequentially and:
53 1) Gathers all memory references in the single loop.
54 2) For each of the references it decides when it is profitable to prefetch
55 it. To do it, we evaluate the reuse among the accesses, and determines
56 two values: PREFETCH_BEFORE (meaning that it only makes sense to do
57 prefetching in the first PREFETCH_BEFORE iterations of the loop) and
58 PREFETCH_MOD (meaning that it only makes sense to prefetch in the
59 iterations of the loop that are zero modulo PREFETCH_MOD). For example
60 (assuming cache line size is 64 bytes, char has size 1 byte and there
61 is no hardware sequential prefetch):
64 for (i = 0; i < max; i++)
71 a[187*i + 50] = ...; (5)
74 (0) obviously has PREFETCH_BEFORE 1
75 (1) has PREFETCH_BEFORE 64, since (2) accesses the same memory
76 location 64 iterations before it, and PREFETCH_MOD 64 (since
77 it hits the same cache line otherwise).
78 (2) has PREFETCH_MOD 64
79 (3) has PREFETCH_MOD 4
80 (4) has PREFETCH_MOD 1. We do not set PREFETCH_BEFORE here, since
81 the cache line accessed by (4) is the same with probability only
83 (5) has PREFETCH_MOD 1 as well.
85 3) We determine how much ahead we need to prefetch. The number of
86 iterations needed is time to fetch / time spent in one iteration of
87 the loop. The problem is that we do not know either of these values,
88 so we just make a heuristic guess based on a magic (possibly)
89 target-specific constant and size of the loop.
91 4) Determine which of the references we prefetch. We take into account
92 that there is a maximum number of simultaneous prefetches (provided
93 by machine description). We prefetch as many prefetches as possible
94 while still within this bound (starting with those with lowest
95 prefetch_mod, since they are responsible for most of the cache
98 5) We unroll and peel loops so that we are able to satisfy PREFETCH_MOD
99 and PREFETCH_BEFORE requirements (within some bounds), and to avoid
100 prefetching nonaccessed memory.
101 TODO -- actually implement peeling.
103 6) We actually emit the prefetch instructions. ??? Perhaps emit the
104 prefetch instructions with guards in cases where 5) was not sufficient
105 to satisfy the constraints?
108 -- write and use more general reuse analysis (that could be also used
109 in other cache aimed loop optimizations)
110 -- make it behave sanely together with the prefetches given by user
111 (now we just ignore them; at the very least we should avoid
112 optimizing loops in that user put his own prefetches)
113 -- we assume cache line size alignment of arrays; this could be
116 /* Magic constants follow. These should be replaced by machine specific
119 /* True if write can be prefetched by a read prefetch. */
121 #ifndef WRITE_CAN_USE_READ_PREFETCH
122 #define WRITE_CAN_USE_READ_PREFETCH 1
125 /* True if read can be prefetched by a write prefetch. */
127 #ifndef READ_CAN_USE_WRITE_PREFETCH
128 #define READ_CAN_USE_WRITE_PREFETCH 0
131 /* The size of the block loaded by a single prefetch. Usually, this is
132 the same as cache line size (at the moment, we only consider one level
133 of cache hierarchy). */
135 #ifndef PREFETCH_BLOCK
136 #define PREFETCH_BLOCK L1_CACHE_LINE_SIZE
139 /* Do we have a forward hardware sequential prefetching? */
141 #ifndef HAVE_FORWARD_PREFETCH
142 #define HAVE_FORWARD_PREFETCH 0
145 /* Do we have a backward hardware sequential prefetching? */
147 #ifndef HAVE_BACKWARD_PREFETCH
148 #define HAVE_BACKWARD_PREFETCH 0
151 /* In some cases we are only able to determine that there is a certain
152 probability that the two accesses hit the same cache line. In this
153 case, we issue the prefetches for both of them if this probability
154 is less then (1000 - ACCEPTABLE_MISS_RATE) promile. */
156 #ifndef ACCEPTABLE_MISS_RATE
157 #define ACCEPTABLE_MISS_RATE 50
160 #ifndef HAVE_prefetch
161 #define HAVE_prefetch 0
164 /* The group of references between that reuse may occur. */
168 tree base
; /* Base of the reference. */
169 HOST_WIDE_INT step
; /* Step of the reference. */
170 struct mem_ref
*refs
; /* References in the group. */
171 struct mem_ref_group
*next
; /* Next group of references. */
174 /* Assigned to PREFETCH_BEFORE when all iterations are to be prefetched. */
176 #define PREFETCH_ALL (~(unsigned HOST_WIDE_INT) 0)
178 /* The memory reference. */
182 tree stmt
; /* Statement in that the reference appears. */
183 tree mem
; /* The reference. */
184 HOST_WIDE_INT delta
; /* Constant offset of the reference. */
185 bool write_p
; /* Is it a write? */
186 struct mem_ref_group
*group
; /* The group of references it belongs to. */
187 unsigned HOST_WIDE_INT prefetch_mod
;
188 /* Prefetch only each PREFETCH_MOD-th
190 unsigned HOST_WIDE_INT prefetch_before
;
191 /* Prefetch only first PREFETCH_BEFORE
193 bool issue_prefetch_p
; /* Should we really issue the prefetch? */
194 struct mem_ref
*next
; /* The next reference in the group. */
197 /* Dumps information about reference REF to FILE. */
200 dump_mem_ref (FILE *file
, struct mem_ref
*ref
)
202 fprintf (file
, "Reference %p:\n", (void *) ref
);
204 fprintf (file
, " group %p (base ", (void *) ref
->group
);
205 print_generic_expr (file
, ref
->group
->base
, TDF_SLIM
);
206 fprintf (file
, ", step ");
207 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, ref
->group
->step
);
208 fprintf (file
, ")\n");
210 fprintf (file
, " delta ");
211 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, ref
->delta
);
212 fprintf (file
, "\n");
214 fprintf (file
, " %s\n", ref
->write_p
? "write" : "read");
216 fprintf (file
, "\n");
219 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
222 static struct mem_ref_group
*
223 find_or_create_group (struct mem_ref_group
**groups
, tree base
,
226 struct mem_ref_group
*group
;
228 for (; *groups
; groups
= &(*groups
)->next
)
230 if ((*groups
)->step
== step
231 && operand_equal_p ((*groups
)->base
, base
, 0))
234 /* Keep the list of groups sorted by decreasing step. */
235 if ((*groups
)->step
< step
)
239 group
= xcalloc (1, sizeof (struct mem_ref_group
));
243 group
->next
= *groups
;
249 /* Records a memory reference MEM in GROUP with offset DELTA and write status
250 WRITE_P. The reference occurs in statement STMT. */
253 record_ref (struct mem_ref_group
*group
, tree stmt
, tree mem
,
254 HOST_WIDE_INT delta
, bool write_p
)
256 struct mem_ref
**aref
;
258 /* Do not record the same address twice. */
259 for (aref
= &group
->refs
; *aref
; aref
= &(*aref
)->next
)
261 /* It does not have to be possible for write reference to reuse the read
262 prefetch, or vice versa. */
263 if (!WRITE_CAN_USE_READ_PREFETCH
265 && !(*aref
)->write_p
)
267 if (!READ_CAN_USE_WRITE_PREFETCH
272 if ((*aref
)->delta
== delta
)
276 (*aref
) = xcalloc (1, sizeof (struct mem_ref
));
277 (*aref
)->stmt
= stmt
;
279 (*aref
)->delta
= delta
;
280 (*aref
)->write_p
= write_p
;
281 (*aref
)->prefetch_before
= PREFETCH_ALL
;
282 (*aref
)->prefetch_mod
= 1;
283 (*aref
)->issue_prefetch_p
= false;
284 (*aref
)->group
= group
;
285 (*aref
)->next
= NULL
;
287 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
288 dump_mem_ref (dump_file
, *aref
);
291 /* Release memory references in GROUPS. */
294 release_mem_refs (struct mem_ref_group
*groups
)
296 struct mem_ref_group
*next_g
;
297 struct mem_ref
*ref
, *next_r
;
299 for (; groups
; groups
= next_g
)
301 next_g
= groups
->next
;
302 for (ref
= groups
->refs
; ref
; ref
= next_r
)
311 /* A structure used to pass arguments to idx_analyze_ref. */
315 struct loop
*loop
; /* Loop of the reference. */
316 tree stmt
; /* Statement of the reference. */
317 HOST_WIDE_INT
*step
; /* Step of the memory reference. */
318 HOST_WIDE_INT
*delta
; /* Offset of the memory reference. */
321 /* Analyzes a single INDEX of a memory reference to obtain information
322 described at analyze_ref. Callback for for_each_index. */
325 idx_analyze_ref (tree base
, tree
*index
, void *data
)
327 struct ar_data
*ar_data
= data
;
328 tree ibase
, step
, stepsize
;
329 HOST_WIDE_INT istep
, idelta
= 0, imult
= 1;
332 if (TREE_CODE (base
) == MISALIGNED_INDIRECT_REF
333 || TREE_CODE (base
) == ALIGN_INDIRECT_REF
)
336 if (!simple_iv (ar_data
->loop
, ar_data
->stmt
, *index
, &iv
, false))
341 if (!cst_and_fits_in_hwi (step
))
343 istep
= int_cst_value (step
);
345 if (TREE_CODE (ibase
) == PLUS_EXPR
346 && cst_and_fits_in_hwi (TREE_OPERAND (ibase
, 1)))
348 idelta
= int_cst_value (TREE_OPERAND (ibase
, 1));
349 ibase
= TREE_OPERAND (ibase
, 0);
351 if (cst_and_fits_in_hwi (ibase
))
353 idelta
+= int_cst_value (ibase
);
354 ibase
= build_int_cst (TREE_TYPE (ibase
), 0);
357 if (TREE_CODE (base
) == ARRAY_REF
)
359 stepsize
= array_ref_element_size (base
);
360 if (!cst_and_fits_in_hwi (stepsize
))
362 imult
= int_cst_value (stepsize
);
368 *ar_data
->step
+= istep
;
369 *ar_data
->delta
+= idelta
;
375 /* Tries to express REF_P in shape &BASE + STEP * iter + DELTA, where DELTA and
376 STEP are integer constants and iter is number of iterations of LOOP. The
377 reference occurs in statement STMT. Strips nonaddressable component
378 references from REF_P. */
381 analyze_ref (struct loop
*loop
, tree
*ref_p
, tree
*base
,
382 HOST_WIDE_INT
*step
, HOST_WIDE_INT
*delta
,
385 struct ar_data ar_data
;
387 HOST_WIDE_INT bit_offset
;
393 /* First strip off the component references. Ignore bitfields. */
394 if (TREE_CODE (ref
) == COMPONENT_REF
395 && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref
, 1)))
396 ref
= TREE_OPERAND (ref
, 0);
400 for (; TREE_CODE (ref
) == COMPONENT_REF
; ref
= TREE_OPERAND (ref
, 0))
402 off
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
403 bit_offset
= TREE_INT_CST_LOW (off
);
404 gcc_assert (bit_offset
% BITS_PER_UNIT
== 0);
406 *delta
+= bit_offset
/ BITS_PER_UNIT
;
409 *base
= unshare_expr (ref
);
413 ar_data
.delta
= delta
;
414 return for_each_index (base
, idx_analyze_ref
, &ar_data
);
417 /* Record a memory reference REF to the list REFS. The reference occurs in
418 LOOP in statement STMT and it is write if WRITE_P. */
421 gather_memory_references_ref (struct loop
*loop
, struct mem_ref_group
**refs
,
422 tree ref
, bool write_p
, tree stmt
)
425 HOST_WIDE_INT step
, delta
;
426 struct mem_ref_group
*agrp
;
428 if (!analyze_ref (loop
, &ref
, &base
, &step
, &delta
, stmt
))
431 /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
432 are integer constants. */
433 agrp
= find_or_create_group (refs
, base
, step
);
434 record_ref (agrp
, stmt
, ref
, delta
, write_p
);
437 /* Record the suitable memory references in LOOP. */
439 static struct mem_ref_group
*
440 gather_memory_references (struct loop
*loop
)
442 basic_block
*body
= get_loop_body_in_dom_order (loop
);
445 block_stmt_iterator bsi
;
447 struct mem_ref_group
*refs
= NULL
;
449 /* Scan the loop body in order, so that the former references precede the
451 for (i
= 0; i
< loop
->num_nodes
; i
++)
454 if (bb
->loop_father
!= loop
)
457 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
459 stmt
= bsi_stmt (bsi
);
460 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
463 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
464 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
466 if (REFERENCE_CLASS_P (rhs
))
467 gather_memory_references_ref (loop
, &refs
, rhs
, false, stmt
);
468 if (REFERENCE_CLASS_P (lhs
))
469 gather_memory_references_ref (loop
, &refs
, lhs
, true, stmt
);
477 /* Prune the prefetch candidate REF using the self-reuse. */
480 prune_ref_by_self_reuse (struct mem_ref
*ref
)
482 HOST_WIDE_INT step
= ref
->group
->step
;
483 bool backward
= step
< 0;
487 /* Prefetch references to invariant address just once. */
488 ref
->prefetch_before
= 1;
495 if (step
> PREFETCH_BLOCK
)
498 if ((backward
&& HAVE_BACKWARD_PREFETCH
)
499 || (!backward
&& HAVE_FORWARD_PREFETCH
))
501 ref
->prefetch_before
= 1;
505 ref
->prefetch_mod
= PREFETCH_BLOCK
/ step
;
508 /* Divides X by BY, rounding down. */
511 ddown (HOST_WIDE_INT x
, unsigned HOST_WIDE_INT by
)
518 return (x
+ by
- 1) / by
;
521 /* Prune the prefetch candidate REF using the reuse with BY.
522 If BY_IS_BEFORE is true, BY is before REF in the loop. */
525 prune_ref_by_group_reuse (struct mem_ref
*ref
, struct mem_ref
*by
,
528 HOST_WIDE_INT step
= ref
->group
->step
;
529 bool backward
= step
< 0;
530 HOST_WIDE_INT delta_r
= ref
->delta
, delta_b
= by
->delta
;
531 HOST_WIDE_INT delta
= delta_b
- delta_r
;
532 HOST_WIDE_INT hit_from
;
533 unsigned HOST_WIDE_INT prefetch_before
, prefetch_block
;
537 /* If the references has the same address, only prefetch the
540 ref
->prefetch_before
= 0;
547 /* If the reference addresses are invariant and fall into the
548 same cache line, prefetch just the first one. */
552 if (ddown (ref
->delta
, PREFETCH_BLOCK
)
553 != ddown (by
->delta
, PREFETCH_BLOCK
))
556 ref
->prefetch_before
= 0;
560 /* Only prune the reference that is behind in the array. */
566 /* Transform the data so that we may assume that the accesses
570 delta_r
= PREFETCH_BLOCK
- 1 - delta_r
;
571 delta_b
= PREFETCH_BLOCK
- 1 - delta_b
;
579 /* Check whether the two references are likely to hit the same cache
580 line, and how distant the iterations in that it occurs are from
583 if (step
<= PREFETCH_BLOCK
)
585 /* The accesses are sure to meet. Let us check when. */
586 hit_from
= ddown (delta_b
, PREFETCH_BLOCK
) * PREFETCH_BLOCK
;
587 prefetch_before
= (hit_from
- delta_r
+ step
- 1) / step
;
589 if (prefetch_before
< ref
->prefetch_before
)
590 ref
->prefetch_before
= prefetch_before
;
595 /* A more complicated case. First let us ensure that size of cache line
596 and step are coprime (here we assume that PREFETCH_BLOCK is a power
598 prefetch_block
= PREFETCH_BLOCK
;
599 while ((step
& 1) == 0
600 && prefetch_block
> 1)
603 prefetch_block
>>= 1;
607 /* Now step > prefetch_block, and step and prefetch_block are coprime.
608 Determine the probability that the accesses hit the same cache line. */
610 prefetch_before
= delta
/ step
;
612 if ((unsigned HOST_WIDE_INT
) delta
613 <= (prefetch_block
* ACCEPTABLE_MISS_RATE
/ 1000))
615 if (prefetch_before
< ref
->prefetch_before
)
616 ref
->prefetch_before
= prefetch_before
;
621 /* Try also the following iteration. */
623 delta
= step
- delta
;
624 if ((unsigned HOST_WIDE_INT
) delta
625 <= (prefetch_block
* ACCEPTABLE_MISS_RATE
/ 1000))
627 if (prefetch_before
< ref
->prefetch_before
)
628 ref
->prefetch_before
= prefetch_before
;
633 /* The ref probably does not reuse by. */
637 /* Prune the prefetch candidate REF using the reuses with other references
641 prune_ref_by_reuse (struct mem_ref
*ref
, struct mem_ref
*refs
)
643 struct mem_ref
*prune_by
;
646 prune_ref_by_self_reuse (ref
);
648 for (prune_by
= refs
; prune_by
; prune_by
= prune_by
->next
)
656 if (!WRITE_CAN_USE_READ_PREFETCH
658 && !prune_by
->write_p
)
660 if (!READ_CAN_USE_WRITE_PREFETCH
662 && prune_by
->write_p
)
665 prune_ref_by_group_reuse (ref
, prune_by
, before
);
669 /* Prune the prefetch candidates in GROUP using the reuse analysis. */
672 prune_group_by_reuse (struct mem_ref_group
*group
)
674 struct mem_ref
*ref_pruned
;
676 for (ref_pruned
= group
->refs
; ref_pruned
; ref_pruned
= ref_pruned
->next
)
678 prune_ref_by_reuse (ref_pruned
, group
->refs
);
680 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
682 fprintf (dump_file
, "Reference %p:", (void *) ref_pruned
);
684 if (ref_pruned
->prefetch_before
== PREFETCH_ALL
685 && ref_pruned
->prefetch_mod
== 1)
686 fprintf (dump_file
, " no restrictions");
687 else if (ref_pruned
->prefetch_before
== 0)
688 fprintf (dump_file
, " do not prefetch");
689 else if (ref_pruned
->prefetch_before
<= ref_pruned
->prefetch_mod
)
690 fprintf (dump_file
, " prefetch once");
693 if (ref_pruned
->prefetch_before
!= PREFETCH_ALL
)
695 fprintf (dump_file
, " prefetch before ");
696 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
697 ref_pruned
->prefetch_before
);
699 if (ref_pruned
->prefetch_mod
!= 1)
701 fprintf (dump_file
, " prefetch mod ");
702 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
703 ref_pruned
->prefetch_mod
);
706 fprintf (dump_file
, "\n");
711 /* Prune the list of prefetch candidates GROUPS using the reuse analysis. */
714 prune_by_reuse (struct mem_ref_group
*groups
)
716 for (; groups
; groups
= groups
->next
)
717 prune_group_by_reuse (groups
);
720 /* Returns true if we should issue prefetch for REF. */
723 should_issue_prefetch_p (struct mem_ref
*ref
)
725 /* For now do not issue prefetches for only first few of the
727 if (ref
->prefetch_before
!= PREFETCH_ALL
)
733 /* Decide which of the prefetch candidates in GROUPS to prefetch.
734 AHEAD is the number of iterations to prefetch ahead (which corresponds
735 to the number of simultaneous instances of one prefetch running at a
736 time). UNROLL_FACTOR is the factor by that the loop is going to be
737 unrolled. Returns true if there is anything to prefetch. */
740 schedule_prefetches (struct mem_ref_group
*groups
, unsigned unroll_factor
,
743 unsigned remaining_prefetch_slots
, n_prefetches
, prefetch_slots
;
744 unsigned slots_per_prefetch
;
748 /* At most SIMULTANEOUS_PREFETCHES should be running at the same time. */
749 remaining_prefetch_slots
= SIMULTANEOUS_PREFETCHES
;
751 /* The prefetch will run for AHEAD iterations of the original loop, i.e.,
752 AHEAD / UNROLL_FACTOR iterations of the unrolled loop. In each iteration,
753 it will need a prefetch slot. */
754 slots_per_prefetch
= (ahead
+ unroll_factor
/ 2) / unroll_factor
;
755 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
756 fprintf (dump_file
, "Each prefetch instruction takes %u prefetch slots.\n",
759 /* For now we just take memory references one by one and issue
760 prefetches for as many as possible. The groups are sorted
761 starting with the largest step, since the references with
762 large step are more likely to cause many cache misses. */
764 for (; groups
; groups
= groups
->next
)
765 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
767 if (!should_issue_prefetch_p (ref
))
770 /* If we need to prefetch the reference each PREFETCH_MOD iterations,
771 and we unroll the loop UNROLL_FACTOR times, we need to insert
772 ceil (UNROLL_FACTOR / PREFETCH_MOD) instructions in each
774 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
775 / ref
->prefetch_mod
);
776 prefetch_slots
= n_prefetches
* slots_per_prefetch
;
778 /* If more than half of the prefetches would be lost anyway, do not
779 issue the prefetch. */
780 if (2 * remaining_prefetch_slots
< prefetch_slots
)
783 ref
->issue_prefetch_p
= true;
785 if (remaining_prefetch_slots
<= prefetch_slots
)
787 remaining_prefetch_slots
-= prefetch_slots
;
794 /* Determine whether there is any reference suitable for prefetching
798 anything_to_prefetch_p (struct mem_ref_group
*groups
)
802 for (; groups
; groups
= groups
->next
)
803 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
804 if (should_issue_prefetch_p (ref
))
810 /* Issue prefetches for the reference REF into loop as decided before.
811 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR
812 is the factor by which LOOP was unrolled. */
815 issue_prefetch_ref (struct mem_ref
*ref
, unsigned unroll_factor
, unsigned ahead
)
818 tree addr
, addr_base
, prefetch
, write_p
;
819 block_stmt_iterator bsi
;
820 unsigned n_prefetches
, ap
;
822 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
823 fprintf (dump_file
, "Issued prefetch for %p.\n", (void *) ref
);
825 bsi
= bsi_for_stmt (ref
->stmt
);
827 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
828 / ref
->prefetch_mod
);
829 addr_base
= build_fold_addr_expr_with_type (ref
->mem
, ptr_type_node
);
830 addr_base
= force_gimple_operand_bsi (&bsi
, unshare_expr (addr_base
), true, NULL
);
831 write_p
= ref
->write_p
? integer_one_node
: integer_zero_node
;
833 for (ap
= 0; ap
< n_prefetches
; ap
++)
835 /* Determine the address to prefetch. */
836 delta
= (ahead
+ ap
* ref
->prefetch_mod
) * ref
->group
->step
;
837 addr
= fold_build2 (PLUS_EXPR
, ptr_type_node
,
838 addr_base
, build_int_cst (ptr_type_node
, delta
));
839 addr
= force_gimple_operand_bsi (&bsi
, unshare_expr (addr
), true, NULL
);
841 /* Create the prefetch instruction. */
842 prefetch
= build_call_expr (built_in_decls
[BUILT_IN_PREFETCH
],
844 bsi_insert_before (&bsi
, prefetch
, BSI_SAME_STMT
);
848 /* Issue prefetches for the references in GROUPS into loop as decided before.
849 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR is the
850 factor by that LOOP was unrolled. */
853 issue_prefetches (struct mem_ref_group
*groups
,
854 unsigned unroll_factor
, unsigned ahead
)
858 for (; groups
; groups
= groups
->next
)
859 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
860 if (ref
->issue_prefetch_p
)
861 issue_prefetch_ref (ref
, unroll_factor
, ahead
);
864 /* Determines whether we can profitably unroll LOOP FACTOR times, and if
865 this is the case, fill in DESC by the description of number of
869 should_unroll_loop_p (struct loop
*loop
, struct tree_niter_desc
*desc
,
872 if (!can_unroll_loop_p (loop
, factor
, desc
))
875 /* We only consider loops without control flow for unrolling. This is not
876 a hard restriction -- tree_unroll_loop works with arbitrary loops
877 as well; but the unrolling/prefetching is usually more profitable for
878 loops consisting of a single basic block, and we want to limit the
880 if (loop
->num_nodes
> 2)
886 /* Determine the coefficient by that unroll LOOP, from the information
887 contained in the list of memory references REFS. Description of
888 umber of iterations of LOOP is stored to DESC. NINSNS is the number of
889 insns of the LOOP. EST_NITER is the estimated number of iterations of
890 the loop, or -1 if no estimate is available. */
893 determine_unroll_factor (struct loop
*loop
, struct mem_ref_group
*refs
,
894 unsigned ninsns
, struct tree_niter_desc
*desc
,
895 HOST_WIDE_INT est_niter
)
897 unsigned upper_bound
;
898 unsigned nfactor
, factor
, mod_constraint
;
899 struct mem_ref_group
*agp
;
902 /* First check whether the loop is not too large to unroll. We ignore
903 PARAM_MAX_UNROLL_TIMES, because for small loops, it prevented us
904 from unrolling them enough to make exactly one cache line covered by each
905 iteration. Also, the goal of PARAM_MAX_UNROLL_TIMES is to prevent
906 us from unrolling the loops too many times in cases where we only expect
907 gains from better scheduling and decreasing loop overhead, which is not
909 upper_bound
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / ninsns
;
911 /* If we unrolled the loop more times than it iterates, the unrolled version
912 of the loop would be never entered. */
913 if (est_niter
>= 0 && est_niter
< (HOST_WIDE_INT
) upper_bound
)
914 upper_bound
= est_niter
;
916 if (upper_bound
<= 1)
919 /* Choose the factor so that we may prefetch each cache just once,
920 but bound the unrolling by UPPER_BOUND. */
922 for (agp
= refs
; agp
; agp
= agp
->next
)
923 for (ref
= agp
->refs
; ref
; ref
= ref
->next
)
924 if (should_issue_prefetch_p (ref
))
926 mod_constraint
= ref
->prefetch_mod
;
927 nfactor
= least_common_multiple (mod_constraint
, factor
);
928 if (nfactor
<= upper_bound
)
932 if (!should_unroll_loop_p (loop
, desc
, factor
))
938 /* Issue prefetch instructions for array references in LOOP. Returns
939 true if the LOOP was unrolled. */
942 loop_prefetch_arrays (struct loop
*loop
)
944 struct mem_ref_group
*refs
;
945 unsigned ahead
, ninsns
, time
, unroll_factor
;
946 HOST_WIDE_INT est_niter
;
947 struct tree_niter_desc desc
;
948 bool unrolled
= false;
950 /* Step 1: gather the memory references. */
951 refs
= gather_memory_references (loop
);
953 /* Step 2: estimate the reuse effects. */
954 prune_by_reuse (refs
);
956 if (!anything_to_prefetch_p (refs
))
959 /* Step 3: determine the ahead and unroll factor. */
961 /* FIXME: the time should be weighted by the probabilities of the blocks in
963 time
= tree_num_loop_insns (loop
, &eni_time_weights
);
964 ahead
= (PREFETCH_LATENCY
+ time
- 1) / time
;
965 est_niter
= estimated_loop_iterations_int (loop
, false);
967 /* The prefetches will run for AHEAD iterations of the original loop. Unless
968 the loop rolls at least AHEAD times, prefetching the references does not
970 if (est_niter
>= 0 && est_niter
<= (HOST_WIDE_INT
) ahead
)
972 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
974 "Not prefetching -- loop estimated to roll only %d times\n",
979 ninsns
= tree_num_loop_insns (loop
, &eni_size_weights
);
980 unroll_factor
= determine_unroll_factor (loop
, refs
, ninsns
, &desc
,
982 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
983 fprintf (dump_file
, "Ahead %d, unroll factor %d\n", ahead
, unroll_factor
);
985 /* Step 4: what to prefetch? */
986 if (!schedule_prefetches (refs
, unroll_factor
, ahead
))
989 /* Step 5: unroll the loop. TODO -- peeling of first and last few
990 iterations so that we do not issue superfluous prefetches. */
991 if (unroll_factor
!= 1)
993 tree_unroll_loop (loop
, unroll_factor
,
994 single_dom_exit (loop
), &desc
);
998 /* Step 6: issue the prefetches. */
999 issue_prefetches (refs
, unroll_factor
, ahead
);
1002 release_mem_refs (refs
);
1006 /* Issue prefetch instructions for array references in loops. */
1009 tree_ssa_prefetch_arrays (void)
1013 bool unrolled
= false;
1017 /* It is possible to ask compiler for say -mtune=i486 -march=pentium4.
1018 -mtune=i486 causes us having PREFETCH_BLOCK 0, since this is part
1019 of processor costs and i486 does not have prefetch, but
1020 -march=pentium4 causes HAVE_prefetch to be true. Ugh. */
1021 || PREFETCH_BLOCK
== 0)
1024 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1026 fprintf (dump_file
, "Prefetching parameters:\n");
1027 fprintf (dump_file
, " simultaneous prefetches: %d\n",
1028 SIMULTANEOUS_PREFETCHES
);
1029 fprintf (dump_file
, " prefetch latency: %d\n", PREFETCH_LATENCY
);
1030 fprintf (dump_file
, " L1 cache size: %d (%d bytes)\n",
1031 L1_CACHE_SIZE
, L1_CACHE_SIZE
* L1_CACHE_LINE_SIZE
);
1032 fprintf (dump_file
, " L1 cache line size: %d\n", L1_CACHE_LINE_SIZE
);
1033 fprintf (dump_file
, " prefetch block size: %d\n", PREFETCH_BLOCK
);
1034 fprintf (dump_file
, "\n");
1037 initialize_original_copy_tables ();
1039 if (!built_in_decls
[BUILT_IN_PREFETCH
])
1041 tree type
= build_function_type (void_type_node
,
1042 tree_cons (NULL_TREE
,
1043 const_ptr_type_node
,
1045 tree decl
= add_builtin_function ("__builtin_prefetch", type
,
1046 BUILT_IN_PREFETCH
, BUILT_IN_NORMAL
,
1048 DECL_IS_NOVOPS (decl
) = true;
1049 built_in_decls
[BUILT_IN_PREFETCH
] = decl
;
1052 /* We assume that size of cache line is a power of two, so verify this
1054 gcc_assert ((PREFETCH_BLOCK
& (PREFETCH_BLOCK
- 1)) == 0);
1056 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1058 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1059 fprintf (dump_file
, "Processing loop %d:\n", loop
->num
);
1061 unrolled
|= loop_prefetch_arrays (loop
);
1063 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1064 fprintf (dump_file
, "\n\n");
1070 todo_flags
|= TODO_cleanup_cfg
;
1073 free_original_copy_tables ();