2 Copyright (C) 2005, 2007 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
37 #include "tree-pass.h"
39 #include "insn-config.h"
42 #include "tree-chrec.h"
43 #include "tree-scalar-evolution.h"
46 #include "langhooks.h"
47 #include "tree-inline.h"
48 #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 /* In case we have to emit a memory fence instruction after the loop that
181 uses nontemporal stores, this defines the builtin to use. */
183 #ifndef FENCE_FOLLOWING_MOVNT
184 #define FENCE_FOLLOWING_MOVNT NULL_TREE
187 /* The group of references between that reuse may occur. */
191 tree base
; /* Base of the reference. */
192 HOST_WIDE_INT step
; /* Step of the reference. */
193 struct mem_ref
*refs
; /* References in the group. */
194 struct mem_ref_group
*next
; /* Next group of references. */
197 /* Assigned to PREFETCH_BEFORE when all iterations are to be prefetched. */
199 #define PREFETCH_ALL (~(unsigned HOST_WIDE_INT) 0)
201 /* The memory reference. */
205 tree stmt
; /* Statement in that the reference appears. */
206 tree mem
; /* The reference. */
207 HOST_WIDE_INT delta
; /* Constant offset of the reference. */
208 struct mem_ref_group
*group
; /* The group of references it belongs to. */
209 unsigned HOST_WIDE_INT prefetch_mod
;
210 /* Prefetch only each PREFETCH_MOD-th
212 unsigned HOST_WIDE_INT prefetch_before
;
213 /* Prefetch only first PREFETCH_BEFORE
215 unsigned reuse_distance
; /* The amount of data accessed before the first
216 reuse of this value. */
217 struct mem_ref
*next
; /* The next reference in the group. */
218 unsigned write_p
: 1; /* Is it a write? */
219 unsigned independent_p
: 1; /* True if the reference is independent on
220 all other references inside the loop. */
221 unsigned issue_prefetch_p
: 1; /* Should we really issue the prefetch? */
222 unsigned storent_p
: 1; /* True if we changed the store to a
226 /* Dumps information about reference REF to FILE. */
229 dump_mem_ref (FILE *file
, struct mem_ref
*ref
)
231 fprintf (file
, "Reference %p:\n", (void *) ref
);
233 fprintf (file
, " group %p (base ", (void *) ref
->group
);
234 print_generic_expr (file
, ref
->group
->base
, TDF_SLIM
);
235 fprintf (file
, ", step ");
236 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, ref
->group
->step
);
237 fprintf (file
, ")\n");
239 fprintf (file
, " delta ");
240 fprintf (file
, HOST_WIDE_INT_PRINT_DEC
, ref
->delta
);
241 fprintf (file
, "\n");
243 fprintf (file
, " %s\n", ref
->write_p
? "write" : "read");
245 fprintf (file
, "\n");
248 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
251 static struct mem_ref_group
*
252 find_or_create_group (struct mem_ref_group
**groups
, tree base
,
255 struct mem_ref_group
*group
;
257 for (; *groups
; groups
= &(*groups
)->next
)
259 if ((*groups
)->step
== step
260 && operand_equal_p ((*groups
)->base
, base
, 0))
263 /* Keep the list of groups sorted by decreasing step. */
264 if ((*groups
)->step
< step
)
268 group
= XNEW (struct mem_ref_group
);
272 group
->next
= *groups
;
278 /* Records a memory reference MEM in GROUP with offset DELTA and write status
279 WRITE_P. The reference occurs in statement STMT. */
282 record_ref (struct mem_ref_group
*group
, tree stmt
, tree mem
,
283 HOST_WIDE_INT delta
, bool write_p
)
285 struct mem_ref
**aref
;
287 /* Do not record the same address twice. */
288 for (aref
= &group
->refs
; *aref
; aref
= &(*aref
)->next
)
290 /* It does not have to be possible for write reference to reuse the read
291 prefetch, or vice versa. */
292 if (!WRITE_CAN_USE_READ_PREFETCH
294 && !(*aref
)->write_p
)
296 if (!READ_CAN_USE_WRITE_PREFETCH
301 if ((*aref
)->delta
== delta
)
305 (*aref
) = XNEW (struct mem_ref
);
306 (*aref
)->stmt
= stmt
;
308 (*aref
)->delta
= delta
;
309 (*aref
)->write_p
= write_p
;
310 (*aref
)->prefetch_before
= PREFETCH_ALL
;
311 (*aref
)->prefetch_mod
= 1;
312 (*aref
)->reuse_distance
= 0;
313 (*aref
)->issue_prefetch_p
= false;
314 (*aref
)->group
= group
;
315 (*aref
)->next
= NULL
;
316 (*aref
)->independent_p
= false;
317 (*aref
)->storent_p
= false;
319 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
320 dump_mem_ref (dump_file
, *aref
);
323 /* Release memory references in GROUPS. */
326 release_mem_refs (struct mem_ref_group
*groups
)
328 struct mem_ref_group
*next_g
;
329 struct mem_ref
*ref
, *next_r
;
331 for (; groups
; groups
= next_g
)
333 next_g
= groups
->next
;
334 for (ref
= groups
->refs
; ref
; ref
= next_r
)
343 /* A structure used to pass arguments to idx_analyze_ref. */
347 struct loop
*loop
; /* Loop of the reference. */
348 tree stmt
; /* Statement of the reference. */
349 HOST_WIDE_INT
*step
; /* Step of the memory reference. */
350 HOST_WIDE_INT
*delta
; /* Offset of the memory reference. */
353 /* Analyzes a single INDEX of a memory reference to obtain information
354 described at analyze_ref. Callback for for_each_index. */
357 idx_analyze_ref (tree base
, tree
*index
, void *data
)
359 struct ar_data
*ar_data
= (struct ar_data
*) data
;
360 tree ibase
, step
, stepsize
;
361 HOST_WIDE_INT istep
, idelta
= 0, imult
= 1;
364 if (TREE_CODE (base
) == MISALIGNED_INDIRECT_REF
365 || TREE_CODE (base
) == ALIGN_INDIRECT_REF
)
368 if (!simple_iv (ar_data
->loop
, ar_data
->stmt
, *index
, &iv
, false))
373 if (!cst_and_fits_in_hwi (step
))
375 istep
= int_cst_value (step
);
377 if (TREE_CODE (ibase
) == POINTER_PLUS_EXPR
378 && cst_and_fits_in_hwi (TREE_OPERAND (ibase
, 1)))
380 idelta
= int_cst_value (TREE_OPERAND (ibase
, 1));
381 ibase
= TREE_OPERAND (ibase
, 0);
383 if (cst_and_fits_in_hwi (ibase
))
385 idelta
+= int_cst_value (ibase
);
386 ibase
= build_int_cst (TREE_TYPE (ibase
), 0);
389 if (TREE_CODE (base
) == ARRAY_REF
)
391 stepsize
= array_ref_element_size (base
);
392 if (!cst_and_fits_in_hwi (stepsize
))
394 imult
= int_cst_value (stepsize
);
400 *ar_data
->step
+= istep
;
401 *ar_data
->delta
+= idelta
;
407 /* Tries to express REF_P in shape &BASE + STEP * iter + DELTA, where DELTA and
408 STEP are integer constants and iter is number of iterations of LOOP. The
409 reference occurs in statement STMT. Strips nonaddressable component
410 references from REF_P. */
413 analyze_ref (struct loop
*loop
, tree
*ref_p
, tree
*base
,
414 HOST_WIDE_INT
*step
, HOST_WIDE_INT
*delta
,
417 struct ar_data ar_data
;
419 HOST_WIDE_INT bit_offset
;
425 /* First strip off the component references. Ignore bitfields. */
426 if (TREE_CODE (ref
) == COMPONENT_REF
427 && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref
, 1)))
428 ref
= TREE_OPERAND (ref
, 0);
432 for (; TREE_CODE (ref
) == COMPONENT_REF
; ref
= TREE_OPERAND (ref
, 0))
434 off
= DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref
, 1));
435 bit_offset
= TREE_INT_CST_LOW (off
);
436 gcc_assert (bit_offset
% BITS_PER_UNIT
== 0);
438 *delta
+= bit_offset
/ BITS_PER_UNIT
;
441 *base
= unshare_expr (ref
);
445 ar_data
.delta
= delta
;
446 return for_each_index (base
, idx_analyze_ref
, &ar_data
);
449 /* Record a memory reference REF to the list REFS. The reference occurs in
450 LOOP in statement STMT and it is write if WRITE_P. Returns true if the
451 reference was recorded, false otherwise. */
454 gather_memory_references_ref (struct loop
*loop
, struct mem_ref_group
**refs
,
455 tree ref
, bool write_p
, tree stmt
)
458 HOST_WIDE_INT step
, delta
;
459 struct mem_ref_group
*agrp
;
461 if (!analyze_ref (loop
, &ref
, &base
, &step
, &delta
, stmt
))
464 /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
465 are integer constants. */
466 agrp
= find_or_create_group (refs
, base
, step
);
467 record_ref (agrp
, stmt
, ref
, delta
, write_p
);
472 /* Record the suitable memory references in LOOP. NO_OTHER_REFS is set to
473 true if there are no other memory references inside the loop. */
475 static struct mem_ref_group
*
476 gather_memory_references (struct loop
*loop
, bool *no_other_refs
)
478 basic_block
*body
= get_loop_body_in_dom_order (loop
);
481 block_stmt_iterator bsi
;
482 tree stmt
, lhs
, rhs
, call
;
483 struct mem_ref_group
*refs
= NULL
;
485 *no_other_refs
= true;
487 /* Scan the loop body in order, so that the former references precede the
489 for (i
= 0; i
< loop
->num_nodes
; i
++)
492 if (bb
->loop_father
!= loop
)
495 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
497 stmt
= bsi_stmt (bsi
);
498 call
= get_call_expr_in (stmt
);
499 if (call
&& !(call_expr_flags (call
) & ECF_CONST
))
500 *no_other_refs
= false;
502 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
504 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
505 *no_other_refs
= false;
509 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
510 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
512 if (REFERENCE_CLASS_P (rhs
))
513 *no_other_refs
&= gather_memory_references_ref (loop
, &refs
,
515 if (REFERENCE_CLASS_P (lhs
))
516 *no_other_refs
&= gather_memory_references_ref (loop
, &refs
,
525 /* Prune the prefetch candidate REF using the self-reuse. */
528 prune_ref_by_self_reuse (struct mem_ref
*ref
)
530 HOST_WIDE_INT step
= ref
->group
->step
;
531 bool backward
= step
< 0;
535 /* Prefetch references to invariant address just once. */
536 ref
->prefetch_before
= 1;
543 if (step
> PREFETCH_BLOCK
)
546 if ((backward
&& HAVE_BACKWARD_PREFETCH
)
547 || (!backward
&& HAVE_FORWARD_PREFETCH
))
549 ref
->prefetch_before
= 1;
553 ref
->prefetch_mod
= PREFETCH_BLOCK
/ step
;
556 /* Divides X by BY, rounding down. */
559 ddown (HOST_WIDE_INT x
, unsigned HOST_WIDE_INT by
)
566 return (x
+ by
- 1) / by
;
569 /* Prune the prefetch candidate REF using the reuse with BY.
570 If BY_IS_BEFORE is true, BY is before REF in the loop. */
573 prune_ref_by_group_reuse (struct mem_ref
*ref
, struct mem_ref
*by
,
576 HOST_WIDE_INT step
= ref
->group
->step
;
577 bool backward
= step
< 0;
578 HOST_WIDE_INT delta_r
= ref
->delta
, delta_b
= by
->delta
;
579 HOST_WIDE_INT delta
= delta_b
- delta_r
;
580 HOST_WIDE_INT hit_from
;
581 unsigned HOST_WIDE_INT prefetch_before
, prefetch_block
;
585 /* If the references has the same address, only prefetch the
588 ref
->prefetch_before
= 0;
595 /* If the reference addresses are invariant and fall into the
596 same cache line, prefetch just the first one. */
600 if (ddown (ref
->delta
, PREFETCH_BLOCK
)
601 != ddown (by
->delta
, PREFETCH_BLOCK
))
604 ref
->prefetch_before
= 0;
608 /* Only prune the reference that is behind in the array. */
614 /* Transform the data so that we may assume that the accesses
618 delta_r
= PREFETCH_BLOCK
- 1 - delta_r
;
619 delta_b
= PREFETCH_BLOCK
- 1 - delta_b
;
627 /* Check whether the two references are likely to hit the same cache
628 line, and how distant the iterations in that it occurs are from
631 if (step
<= PREFETCH_BLOCK
)
633 /* The accesses are sure to meet. Let us check when. */
634 hit_from
= ddown (delta_b
, PREFETCH_BLOCK
) * PREFETCH_BLOCK
;
635 prefetch_before
= (hit_from
- delta_r
+ step
- 1) / step
;
637 if (prefetch_before
< ref
->prefetch_before
)
638 ref
->prefetch_before
= prefetch_before
;
643 /* A more complicated case. First let us ensure that size of cache line
644 and step are coprime (here we assume that PREFETCH_BLOCK is a power
646 prefetch_block
= PREFETCH_BLOCK
;
647 while ((step
& 1) == 0
648 && prefetch_block
> 1)
651 prefetch_block
>>= 1;
655 /* Now step > prefetch_block, and step and prefetch_block are coprime.
656 Determine the probability that the accesses hit the same cache line. */
658 prefetch_before
= delta
/ step
;
660 if ((unsigned HOST_WIDE_INT
) delta
661 <= (prefetch_block
* ACCEPTABLE_MISS_RATE
/ 1000))
663 if (prefetch_before
< ref
->prefetch_before
)
664 ref
->prefetch_before
= prefetch_before
;
669 /* Try also the following iteration. */
671 delta
= step
- delta
;
672 if ((unsigned HOST_WIDE_INT
) delta
673 <= (prefetch_block
* ACCEPTABLE_MISS_RATE
/ 1000))
675 if (prefetch_before
< ref
->prefetch_before
)
676 ref
->prefetch_before
= prefetch_before
;
681 /* The ref probably does not reuse by. */
685 /* Prune the prefetch candidate REF using the reuses with other references
689 prune_ref_by_reuse (struct mem_ref
*ref
, struct mem_ref
*refs
)
691 struct mem_ref
*prune_by
;
694 prune_ref_by_self_reuse (ref
);
696 for (prune_by
= refs
; prune_by
; prune_by
= prune_by
->next
)
704 if (!WRITE_CAN_USE_READ_PREFETCH
706 && !prune_by
->write_p
)
708 if (!READ_CAN_USE_WRITE_PREFETCH
710 && prune_by
->write_p
)
713 prune_ref_by_group_reuse (ref
, prune_by
, before
);
717 /* Prune the prefetch candidates in GROUP using the reuse analysis. */
720 prune_group_by_reuse (struct mem_ref_group
*group
)
722 struct mem_ref
*ref_pruned
;
724 for (ref_pruned
= group
->refs
; ref_pruned
; ref_pruned
= ref_pruned
->next
)
726 prune_ref_by_reuse (ref_pruned
, group
->refs
);
728 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
730 fprintf (dump_file
, "Reference %p:", (void *) ref_pruned
);
732 if (ref_pruned
->prefetch_before
== PREFETCH_ALL
733 && ref_pruned
->prefetch_mod
== 1)
734 fprintf (dump_file
, " no restrictions");
735 else if (ref_pruned
->prefetch_before
== 0)
736 fprintf (dump_file
, " do not prefetch");
737 else if (ref_pruned
->prefetch_before
<= ref_pruned
->prefetch_mod
)
738 fprintf (dump_file
, " prefetch once");
741 if (ref_pruned
->prefetch_before
!= PREFETCH_ALL
)
743 fprintf (dump_file
, " prefetch before ");
744 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
745 ref_pruned
->prefetch_before
);
747 if (ref_pruned
->prefetch_mod
!= 1)
749 fprintf (dump_file
, " prefetch mod ");
750 fprintf (dump_file
, HOST_WIDE_INT_PRINT_DEC
,
751 ref_pruned
->prefetch_mod
);
754 fprintf (dump_file
, "\n");
759 /* Prune the list of prefetch candidates GROUPS using the reuse analysis. */
762 prune_by_reuse (struct mem_ref_group
*groups
)
764 for (; groups
; groups
= groups
->next
)
765 prune_group_by_reuse (groups
);
768 /* Returns true if we should issue prefetch for REF. */
771 should_issue_prefetch_p (struct mem_ref
*ref
)
773 /* For now do not issue prefetches for only first few of the
775 if (ref
->prefetch_before
!= PREFETCH_ALL
)
778 /* Do not prefetch nontemporal stores. */
785 /* Decide which of the prefetch candidates in GROUPS to prefetch.
786 AHEAD is the number of iterations to prefetch ahead (which corresponds
787 to the number of simultaneous instances of one prefetch running at a
788 time). UNROLL_FACTOR is the factor by that the loop is going to be
789 unrolled. Returns true if there is anything to prefetch. */
792 schedule_prefetches (struct mem_ref_group
*groups
, unsigned unroll_factor
,
795 unsigned remaining_prefetch_slots
, n_prefetches
, prefetch_slots
;
796 unsigned slots_per_prefetch
;
800 /* At most SIMULTANEOUS_PREFETCHES should be running at the same time. */
801 remaining_prefetch_slots
= SIMULTANEOUS_PREFETCHES
;
803 /* The prefetch will run for AHEAD iterations of the original loop, i.e.,
804 AHEAD / UNROLL_FACTOR iterations of the unrolled loop. In each iteration,
805 it will need a prefetch slot. */
806 slots_per_prefetch
= (ahead
+ unroll_factor
/ 2) / unroll_factor
;
807 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
808 fprintf (dump_file
, "Each prefetch instruction takes %u prefetch slots.\n",
811 /* For now we just take memory references one by one and issue
812 prefetches for as many as possible. The groups are sorted
813 starting with the largest step, since the references with
814 large step are more likely to cause many cache misses. */
816 for (; groups
; groups
= groups
->next
)
817 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
819 if (!should_issue_prefetch_p (ref
))
822 /* If we need to prefetch the reference each PREFETCH_MOD iterations,
823 and we unroll the loop UNROLL_FACTOR times, we need to insert
824 ceil (UNROLL_FACTOR / PREFETCH_MOD) instructions in each
826 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
827 / ref
->prefetch_mod
);
828 prefetch_slots
= n_prefetches
* slots_per_prefetch
;
830 /* If more than half of the prefetches would be lost anyway, do not
831 issue the prefetch. */
832 if (2 * remaining_prefetch_slots
< prefetch_slots
)
835 ref
->issue_prefetch_p
= true;
837 if (remaining_prefetch_slots
<= prefetch_slots
)
839 remaining_prefetch_slots
-= prefetch_slots
;
846 /* Determine whether there is any reference suitable for prefetching
850 anything_to_prefetch_p (struct mem_ref_group
*groups
)
854 for (; groups
; groups
= groups
->next
)
855 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
856 if (should_issue_prefetch_p (ref
))
862 /* Issue prefetches for the reference REF into loop as decided before.
863 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR
864 is the factor by which LOOP was unrolled. */
867 issue_prefetch_ref (struct mem_ref
*ref
, unsigned unroll_factor
, unsigned ahead
)
870 tree addr
, addr_base
, prefetch
, write_p
, local
;
871 block_stmt_iterator bsi
;
872 unsigned n_prefetches
, ap
;
873 bool nontemporal
= ref
->reuse_distance
>= L2_CACHE_SIZE_BYTES
;
875 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
876 fprintf (dump_file
, "Issued%s prefetch for %p.\n",
877 nontemporal
? " nontemporal" : "",
880 bsi
= bsi_for_stmt (ref
->stmt
);
882 n_prefetches
= ((unroll_factor
+ ref
->prefetch_mod
- 1)
883 / ref
->prefetch_mod
);
884 addr_base
= build_fold_addr_expr_with_type (ref
->mem
, ptr_type_node
);
885 addr_base
= force_gimple_operand_bsi (&bsi
, unshare_expr (addr_base
),
886 true, NULL
, true, BSI_SAME_STMT
);
887 write_p
= ref
->write_p
? integer_one_node
: integer_zero_node
;
888 local
= build_int_cst (integer_type_node
, nontemporal
? 0 : 3);
890 for (ap
= 0; ap
< n_prefetches
; ap
++)
892 /* Determine the address to prefetch. */
893 delta
= (ahead
+ ap
* ref
->prefetch_mod
) * ref
->group
->step
;
894 addr
= fold_build2 (POINTER_PLUS_EXPR
, ptr_type_node
,
895 addr_base
, size_int (delta
));
896 addr
= force_gimple_operand_bsi (&bsi
, unshare_expr (addr
), true, NULL
,
897 true, BSI_SAME_STMT
);
899 /* Create the prefetch instruction. */
900 prefetch
= build_call_expr (built_in_decls
[BUILT_IN_PREFETCH
],
901 3, addr
, write_p
, local
);
902 bsi_insert_before (&bsi
, prefetch
, BSI_SAME_STMT
);
906 /* Issue prefetches for the references in GROUPS into loop as decided before.
907 HEAD is the number of iterations to prefetch ahead. UNROLL_FACTOR is the
908 factor by that LOOP was unrolled. */
911 issue_prefetches (struct mem_ref_group
*groups
,
912 unsigned unroll_factor
, unsigned ahead
)
916 for (; groups
; groups
= groups
->next
)
917 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
918 if (ref
->issue_prefetch_p
)
919 issue_prefetch_ref (ref
, unroll_factor
, ahead
);
922 /* Returns true if REF is a memory write for that a nontemporal store insn
926 nontemporal_store_p (struct mem_ref
*ref
)
928 enum machine_mode mode
;
931 /* REF must be a write that is not reused. We require it to be independent
932 on all other memory references in the loop, as the nontemporal stores may
933 be reordered with respect to other memory references. */
935 || !ref
->independent_p
936 || ref
->reuse_distance
< L2_CACHE_SIZE_BYTES
)
939 /* Check that we have the storent instruction for the mode. */
940 mode
= TYPE_MODE (TREE_TYPE (ref
->mem
));
944 code
= storent_optab
->handlers
[mode
].insn_code
;
945 return code
!= CODE_FOR_nothing
;
948 /* If REF is a nontemporal store, we mark the corresponding modify statement
949 and return true. Otherwise, we return false. */
952 mark_nontemporal_store (struct mem_ref
*ref
)
954 if (!nontemporal_store_p (ref
))
957 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
958 fprintf (dump_file
, "Marked reference %p as a nontemporal store.\n",
961 MOVE_NONTEMPORAL (ref
->stmt
) = true;
962 ref
->storent_p
= true;
967 /* Issue a memory fence instruction after LOOP. */
970 emit_mfence_after_loop (struct loop
*loop
)
972 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
975 block_stmt_iterator bsi
;
978 for (i
= 0; VEC_iterate (edge
, exits
, i
, exit
); i
++)
980 call
= build_function_call_expr (FENCE_FOLLOWING_MOVNT
, NULL_TREE
);
982 if (!single_pred_p (exit
->dest
)
983 /* If possible, we prefer not to insert the fence on other paths
985 && !(exit
->flags
& EDGE_ABNORMAL
))
986 split_loop_exit_edge (exit
);
987 bsi
= bsi_after_labels (exit
->dest
);
989 bsi_insert_before (&bsi
, call
, BSI_NEW_STMT
);
990 mark_virtual_ops_for_renaming (call
);
993 VEC_free (edge
, heap
, exits
);
994 update_ssa (TODO_update_ssa_only_virtuals
);
997 /* Returns true if we can use storent in loop, false otherwise. */
1000 may_use_storent_in_loop_p (struct loop
*loop
)
1004 if (loop
->inner
!= NULL
)
1007 /* If we must issue a mfence insn after using storent, check that there
1008 is a suitable place for it at each of the loop exits. */
1009 if (FENCE_FOLLOWING_MOVNT
!= NULL_TREE
)
1011 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
1015 for (i
= 0; VEC_iterate (edge
, exits
, i
, exit
); i
++)
1016 if ((exit
->flags
& EDGE_ABNORMAL
)
1017 && exit
->dest
== EXIT_BLOCK_PTR
)
1020 VEC_free (edge
, heap
, exits
);
1026 /* Marks nontemporal stores in LOOP. GROUPS contains the description of memory
1027 references in the loop. */
1030 mark_nontemporal_stores (struct loop
*loop
, struct mem_ref_group
*groups
)
1032 struct mem_ref
*ref
;
1035 if (!may_use_storent_in_loop_p (loop
))
1038 for (; groups
; groups
= groups
->next
)
1039 for (ref
= groups
->refs
; ref
; ref
= ref
->next
)
1040 any
|= mark_nontemporal_store (ref
);
1042 if (any
&& FENCE_FOLLOWING_MOVNT
!= NULL_TREE
)
1043 emit_mfence_after_loop (loop
);
1046 /* Determines whether we can profitably unroll LOOP FACTOR times, and if
1047 this is the case, fill in DESC by the description of number of
1051 should_unroll_loop_p (struct loop
*loop
, struct tree_niter_desc
*desc
,
1054 if (!can_unroll_loop_p (loop
, factor
, desc
))
1057 /* We only consider loops without control flow for unrolling. This is not
1058 a hard restriction -- tree_unroll_loop works with arbitrary loops
1059 as well; but the unrolling/prefetching is usually more profitable for
1060 loops consisting of a single basic block, and we want to limit the
1062 if (loop
->num_nodes
> 2)
1068 /* Determine the coefficient by that unroll LOOP, from the information
1069 contained in the list of memory references REFS. Description of
1070 umber of iterations of LOOP is stored to DESC. NINSNS is the number of
1071 insns of the LOOP. EST_NITER is the estimated number of iterations of
1072 the loop, or -1 if no estimate is available. */
1075 determine_unroll_factor (struct loop
*loop
, struct mem_ref_group
*refs
,
1076 unsigned ninsns
, struct tree_niter_desc
*desc
,
1077 HOST_WIDE_INT est_niter
)
1079 unsigned upper_bound
;
1080 unsigned nfactor
, factor
, mod_constraint
;
1081 struct mem_ref_group
*agp
;
1082 struct mem_ref
*ref
;
1084 /* First check whether the loop is not too large to unroll. We ignore
1085 PARAM_MAX_UNROLL_TIMES, because for small loops, it prevented us
1086 from unrolling them enough to make exactly one cache line covered by each
1087 iteration. Also, the goal of PARAM_MAX_UNROLL_TIMES is to prevent
1088 us from unrolling the loops too many times in cases where we only expect
1089 gains from better scheduling and decreasing loop overhead, which is not
1091 upper_bound
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / ninsns
;
1093 /* If we unrolled the loop more times than it iterates, the unrolled version
1094 of the loop would be never entered. */
1095 if (est_niter
>= 0 && est_niter
< (HOST_WIDE_INT
) upper_bound
)
1096 upper_bound
= est_niter
;
1098 if (upper_bound
<= 1)
1101 /* Choose the factor so that we may prefetch each cache just once,
1102 but bound the unrolling by UPPER_BOUND. */
1104 for (agp
= refs
; agp
; agp
= agp
->next
)
1105 for (ref
= agp
->refs
; ref
; ref
= ref
->next
)
1106 if (should_issue_prefetch_p (ref
))
1108 mod_constraint
= ref
->prefetch_mod
;
1109 nfactor
= least_common_multiple (mod_constraint
, factor
);
1110 if (nfactor
<= upper_bound
)
1114 if (!should_unroll_loop_p (loop
, desc
, factor
))
1120 /* Returns the total volume of the memory references REFS, taking into account
1121 reuses in the innermost loop and cache line size. TODO -- we should also
1122 take into account reuses across the iterations of the loops in the loop
1126 volume_of_references (struct mem_ref_group
*refs
)
1128 unsigned volume
= 0;
1129 struct mem_ref_group
*gr
;
1130 struct mem_ref
*ref
;
1132 for (gr
= refs
; gr
; gr
= gr
->next
)
1133 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1135 /* Almost always reuses another value? */
1136 if (ref
->prefetch_before
!= PREFETCH_ALL
)
1139 /* If several iterations access the same cache line, use the size of
1140 the line divided by this number. Otherwise, a cache line is
1141 accessed in each iteration. TODO -- in the latter case, we should
1142 take the size of the reference into account, rounding it up on cache
1143 line size multiple. */
1144 volume
+= L1_CACHE_LINE_SIZE
/ ref
->prefetch_mod
;
1149 /* Returns the volume of memory references accessed across VEC iterations of
1150 loops, whose sizes are described in the LOOP_SIZES array. N is the number
1151 of the loops in the nest (length of VEC and LOOP_SIZES vectors). */
1154 volume_of_dist_vector (lambda_vector vec
, unsigned *loop_sizes
, unsigned n
)
1158 for (i
= 0; i
< n
; i
++)
1165 gcc_assert (vec
[i
] > 0);
1167 /* We ignore the parts of the distance vector in subloops, since usually
1168 the numbers of iterations are much smaller. */
1169 return loop_sizes
[i
] * vec
[i
];
1172 /* Add the steps of ACCESS_FN multiplied by STRIDE to the array STRIDE
1173 at the position corresponding to the loop of the step. N is the depth
1174 of the considered loop nest, and, LOOP is its innermost loop. */
1177 add_subscript_strides (tree access_fn
, unsigned stride
,
1178 HOST_WIDE_INT
*strides
, unsigned n
, struct loop
*loop
)
1182 HOST_WIDE_INT astep
;
1183 unsigned min_depth
= loop_depth (loop
) - n
;
1185 while (TREE_CODE (access_fn
) == POLYNOMIAL_CHREC
)
1187 aloop
= get_chrec_loop (access_fn
);
1188 step
= CHREC_RIGHT (access_fn
);
1189 access_fn
= CHREC_LEFT (access_fn
);
1191 if ((unsigned) loop_depth (aloop
) <= min_depth
)
1194 if (host_integerp (step
, 0))
1195 astep
= tree_low_cst (step
, 0);
1197 astep
= L1_CACHE_LINE_SIZE
;
1199 strides
[n
- 1 - loop_depth (loop
) + loop_depth (aloop
)] += astep
* stride
;
1204 /* Returns the volume of memory references accessed between two consecutive
1205 self-reuses of the reference DR. We consider the subscripts of DR in N
1206 loops, and LOOP_SIZES contains the volumes of accesses in each of the
1207 loops. LOOP is the innermost loop of the current loop nest. */
1210 self_reuse_distance (data_reference_p dr
, unsigned *loop_sizes
, unsigned n
,
1213 tree stride
, access_fn
;
1214 HOST_WIDE_INT
*strides
, astride
;
1215 VEC (tree
, heap
) *access_fns
;
1216 tree ref
= DR_REF (dr
);
1217 unsigned i
, ret
= ~0u;
1219 /* In the following example:
1221 for (i = 0; i < N; i++)
1222 for (j = 0; j < N; j++)
1224 the same cache line is accessed each N steps (except if the change from
1225 i to i + 1 crosses the boundary of the cache line). Thus, for self-reuse,
1226 we cannot rely purely on the results of the data dependence analysis.
1228 Instead, we compute the stride of the reference in each loop, and consider
1229 the innermost loop in that the stride is less than cache size. */
1231 strides
= XCNEWVEC (HOST_WIDE_INT
, n
);
1232 access_fns
= DR_ACCESS_FNS (dr
);
1234 for (i
= 0; VEC_iterate (tree
, access_fns
, i
, access_fn
); i
++)
1236 /* Keep track of the reference corresponding to the subscript, so that we
1238 while (handled_component_p (ref
) && TREE_CODE (ref
) != ARRAY_REF
)
1239 ref
= TREE_OPERAND (ref
, 0);
1241 if (TREE_CODE (ref
) == ARRAY_REF
)
1243 stride
= TYPE_SIZE_UNIT (TREE_TYPE (ref
));
1244 if (host_integerp (stride
, 1))
1245 astride
= tree_low_cst (stride
, 1);
1247 astride
= L1_CACHE_LINE_SIZE
;
1249 ref
= TREE_OPERAND (ref
, 0);
1254 add_subscript_strides (access_fn
, astride
, strides
, n
, loop
);
1257 for (i
= n
; i
-- > 0; )
1259 unsigned HOST_WIDE_INT s
;
1261 s
= strides
[i
] < 0 ? -strides
[i
] : strides
[i
];
1263 if (s
< (unsigned) L1_CACHE_LINE_SIZE
1265 > (unsigned) (L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)))
1267 ret
= loop_sizes
[i
];
1276 /* Determines the distance till the first reuse of each reference in REFS
1277 in the loop nest of LOOP. NO_OTHER_REFS is true if there are no other
1278 memory references in the loop. */
1281 determine_loop_nest_reuse (struct loop
*loop
, struct mem_ref_group
*refs
,
1284 struct loop
*nest
, *aloop
;
1285 VEC (data_reference_p
, heap
) *datarefs
= NULL
;
1286 VEC (ddr_p
, heap
) *dependences
= NULL
;
1287 struct mem_ref_group
*gr
;
1288 struct mem_ref
*ref
, *refb
;
1289 VEC (loop_p
, heap
) *vloops
= NULL
;
1290 unsigned *loop_data_size
;
1292 unsigned volume
, dist
, adist
;
1294 data_reference_p dr
;
1300 /* Find the outermost loop of the loop nest of loop (we require that
1301 there are no sibling loops inside the nest). */
1305 aloop
= loop_outer (nest
);
1307 if (aloop
== current_loops
->tree_root
1308 || aloop
->inner
->next
)
1314 /* For each loop, determine the amount of data accessed in each iteration.
1315 We use this to estimate whether the reference is evicted from the
1316 cache before its reuse. */
1317 find_loop_nest (nest
, &vloops
);
1318 n
= VEC_length (loop_p
, vloops
);
1319 loop_data_size
= XNEWVEC (unsigned, n
);
1320 volume
= volume_of_references (refs
);
1324 loop_data_size
[i
] = volume
;
1325 /* Bound the volume by the L2 cache size, since above this bound,
1326 all dependence distances are equivalent. */
1327 if (volume
> L2_CACHE_SIZE_BYTES
)
1330 aloop
= VEC_index (loop_p
, vloops
, i
);
1331 vol
= estimated_loop_iterations_int (aloop
, false);
1333 vol
= expected_loop_iterations (aloop
);
1337 /* Prepare the references in the form suitable for data dependence
1338 analysis. We ignore unanalyzable data references (the results
1339 are used just as a heuristics to estimate temporality of the
1340 references, hence we do not need to worry about correctness). */
1341 for (gr
= refs
; gr
; gr
= gr
->next
)
1342 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1344 dr
= create_data_ref (nest
, ref
->mem
, ref
->stmt
, !ref
->write_p
);
1348 ref
->reuse_distance
= volume
;
1350 VEC_safe_push (data_reference_p
, heap
, datarefs
, dr
);
1353 no_other_refs
= false;
1356 for (i
= 0; VEC_iterate (data_reference_p
, datarefs
, i
, dr
); i
++)
1358 dist
= self_reuse_distance (dr
, loop_data_size
, n
, loop
);
1360 if (ref
->reuse_distance
> dist
)
1361 ref
->reuse_distance
= dist
;
1364 ref
->independent_p
= true;
1367 compute_all_dependences (datarefs
, &dependences
, vloops
, true);
1369 for (i
= 0; VEC_iterate (ddr_p
, dependences
, i
, dep
); i
++)
1371 if (DDR_ARE_DEPENDENT (dep
) == chrec_known
)
1374 ref
= DDR_A (dep
)->aux
;
1375 refb
= DDR_B (dep
)->aux
;
1377 if (DDR_ARE_DEPENDENT (dep
) == chrec_dont_know
1378 || DDR_NUM_DIST_VECTS (dep
) == 0)
1380 /* If the dependence cannot be analyzed, assume that there might be
1384 ref
->independent_p
= false;
1385 refb
->independent_p
= false;
1389 /* The distance vectors are normalized to be always lexicographically
1390 positive, hence we cannot tell just from them whether DDR_A comes
1391 before DDR_B or vice versa. However, it is not important,
1392 anyway -- if DDR_A is close to DDR_B, then it is either reused in
1393 DDR_B (and it is not nontemporal), or it reuses the value of DDR_B
1394 in cache (and marking it as nontemporal would not affect
1398 for (j
= 0; j
< DDR_NUM_DIST_VECTS (dep
); j
++)
1400 adist
= volume_of_dist_vector (DDR_DIST_VECT (dep
, j
),
1403 /* If this is a dependence in the innermost loop (i.e., the
1404 distances in all superloops are zero) and it is not
1405 the trivial self-dependence with distance zero, record that
1406 the references are not completely independent. */
1407 if (lambda_vector_zerop (DDR_DIST_VECT (dep
, j
), n
- 1)
1409 || DDR_DIST_VECT (dep
, j
)[n
-1] != 0))
1411 ref
->independent_p
= false;
1412 refb
->independent_p
= false;
1415 /* Ignore accesses closer than
1416 L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
1417 so that we use nontemporal prefetches e.g. if single memory
1418 location is accessed several times in a single iteration of
1420 if (adist
< L1_CACHE_SIZE_BYTES
/ NONTEMPORAL_FRACTION
)
1428 if (ref
->reuse_distance
> dist
)
1429 ref
->reuse_distance
= dist
;
1430 if (refb
->reuse_distance
> dist
)
1431 refb
->reuse_distance
= dist
;
1434 free_dependence_relations (dependences
);
1435 free_data_refs (datarefs
);
1436 free (loop_data_size
);
1438 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1440 fprintf (dump_file
, "Reuse distances:\n");
1441 for (gr
= refs
; gr
; gr
= gr
->next
)
1442 for (ref
= gr
->refs
; ref
; ref
= ref
->next
)
1443 fprintf (dump_file
, " ref %p distance %u\n",
1444 (void *) ref
, ref
->reuse_distance
);
1448 /* Issue prefetch instructions for array references in LOOP. Returns
1449 true if the LOOP was unrolled. */
1452 loop_prefetch_arrays (struct loop
*loop
)
1454 struct mem_ref_group
*refs
;
1455 unsigned ahead
, ninsns
, time
, unroll_factor
;
1456 HOST_WIDE_INT est_niter
;
1457 struct tree_niter_desc desc
;
1458 bool unrolled
= false, no_other_refs
;
1460 if (!maybe_hot_bb_p (loop
->header
))
1462 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1463 fprintf (dump_file
, " ignored (cold area)\n");
1467 /* Step 1: gather the memory references. */
1468 refs
= gather_memory_references (loop
, &no_other_refs
);
1470 /* Step 2: estimate the reuse effects. */
1471 prune_by_reuse (refs
);
1473 if (!anything_to_prefetch_p (refs
))
1476 determine_loop_nest_reuse (loop
, refs
, no_other_refs
);
1478 /* Step 3: determine the ahead and unroll factor. */
1480 /* FIXME: the time should be weighted by the probabilities of the blocks in
1482 time
= tree_num_loop_insns (loop
, &eni_time_weights
);
1483 ahead
= (PREFETCH_LATENCY
+ time
- 1) / time
;
1484 est_niter
= estimated_loop_iterations_int (loop
, false);
1486 /* The prefetches will run for AHEAD iterations of the original loop. Unless
1487 the loop rolls at least AHEAD times, prefetching the references does not
1489 if (est_niter
>= 0 && est_niter
<= (HOST_WIDE_INT
) ahead
)
1491 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1493 "Not prefetching -- loop estimated to roll only %d times\n",
1498 mark_nontemporal_stores (loop
, refs
);
1500 ninsns
= tree_num_loop_insns (loop
, &eni_size_weights
);
1501 unroll_factor
= determine_unroll_factor (loop
, refs
, ninsns
, &desc
,
1503 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1504 fprintf (dump_file
, "Ahead %d, unroll factor %d\n", ahead
, unroll_factor
);
1506 /* Step 4: what to prefetch? */
1507 if (!schedule_prefetches (refs
, unroll_factor
, ahead
))
1510 /* Step 5: unroll the loop. TODO -- peeling of first and last few
1511 iterations so that we do not issue superfluous prefetches. */
1512 if (unroll_factor
!= 1)
1514 tree_unroll_loop (loop
, unroll_factor
,
1515 single_dom_exit (loop
), &desc
);
1519 /* Step 6: issue the prefetches. */
1520 issue_prefetches (refs
, unroll_factor
, ahead
);
1523 release_mem_refs (refs
);
1527 /* Issue prefetch instructions for array references in loops. */
1530 tree_ssa_prefetch_arrays (void)
1534 bool unrolled
= false;
1538 /* It is possible to ask compiler for say -mtune=i486 -march=pentium4.
1539 -mtune=i486 causes us having PREFETCH_BLOCK 0, since this is part
1540 of processor costs and i486 does not have prefetch, but
1541 -march=pentium4 causes HAVE_prefetch to be true. Ugh. */
1542 || PREFETCH_BLOCK
== 0)
1545 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1547 fprintf (dump_file
, "Prefetching parameters:\n");
1548 fprintf (dump_file
, " simultaneous prefetches: %d\n",
1549 SIMULTANEOUS_PREFETCHES
);
1550 fprintf (dump_file
, " prefetch latency: %d\n", PREFETCH_LATENCY
);
1551 fprintf (dump_file
, " prefetch block size: %d\n", PREFETCH_BLOCK
);
1552 fprintf (dump_file
, " L1 cache size: %d lines, %d bytes\n",
1553 L1_CACHE_SIZE
, L1_CACHE_SIZE_BYTES
);
1554 fprintf (dump_file
, " L1 cache line size: %d\n", L1_CACHE_LINE_SIZE
);
1555 fprintf (dump_file
, " L2 cache size: %d bytes\n", L2_CACHE_SIZE_BYTES
);
1556 fprintf (dump_file
, "\n");
1559 initialize_original_copy_tables ();
1561 if (!built_in_decls
[BUILT_IN_PREFETCH
])
1563 tree type
= build_function_type (void_type_node
,
1564 tree_cons (NULL_TREE
,
1565 const_ptr_type_node
,
1567 tree decl
= add_builtin_function ("__builtin_prefetch", type
,
1568 BUILT_IN_PREFETCH
, BUILT_IN_NORMAL
,
1570 DECL_IS_NOVOPS (decl
) = true;
1571 built_in_decls
[BUILT_IN_PREFETCH
] = decl
;
1574 /* We assume that size of cache line is a power of two, so verify this
1576 gcc_assert ((PREFETCH_BLOCK
& (PREFETCH_BLOCK
- 1)) == 0);
1578 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1580 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1581 fprintf (dump_file
, "Processing loop %d:\n", loop
->num
);
1583 unrolled
|= loop_prefetch_arrays (loop
);
1585 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1586 fprintf (dump_file
, "\n\n");
1592 todo_flags
|= TODO_cleanup_cfg
;
1595 free_original_copy_tables ();