1 /* Array prefetching.
2    Copyright (C) 2005-2018 Free Software Foundation, Inc.
3 
4 This file is part of GCC.
5 
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
9 later version.
10 
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
14 for more details.
15 
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/>.  */
19 
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "target.h"
25 #include "rtl.h"
26 #include "tree.h"
27 #include "gimple.h"
28 #include "predict.h"
29 #include "tree-pass.h"
30 #include "gimple-ssa.h"
31 #include "optabs-query.h"
32 #include "tree-pretty-print.h"
33 #include "fold-const.h"
34 #include "stor-layout.h"
35 #include "gimplify.h"
36 #include "gimple-iterator.h"
37 #include "gimplify-me.h"
38 #include "tree-ssa-loop-ivopts.h"
39 #include "tree-ssa-loop-manip.h"
40 #include "tree-ssa-loop-niter.h"
41 #include "tree-ssa-loop.h"
42 #include "ssa.h"
43 #include "tree-into-ssa.h"
44 #include "cfgloop.h"
45 #include "tree-scalar-evolution.h"
46 #include "params.h"
47 #include "langhooks.h"
48 #include "tree-inline.h"
49 #include "tree-data-ref.h"
50 #include "diagnostic-core.h"
51 #include "dbgcnt.h"
52 
53 /* This pass inserts prefetch instructions to optimize cache usage during
54    accesses to arrays in loops.  It processes loops sequentially and:
55 
56    1) Gathers all memory references in the single loop.
57    2) For each of the references it decides when it is profitable to prefetch
58       it.  To do it, we evaluate the reuse among the accesses, and determines
59       two values: PREFETCH_BEFORE (meaning that it only makes sense to do
60       prefetching in the first PREFETCH_BEFORE iterations of the loop) and
61       PREFETCH_MOD (meaning that it only makes sense to prefetch in the
62       iterations of the loop that are zero modulo PREFETCH_MOD).  For example
63       (assuming cache line size is 64 bytes, char has size 1 byte and there
64       is no hardware sequential prefetch):
65 
66       char *a;
67       for (i = 0; i < max; i++)
68 	{
69 	  a[255] = ...;		(0)
70 	  a[i] = ...;		(1)
71 	  a[i + 64] = ...;	(2)
72 	  a[16*i] = ...;	(3)
73 	  a[187*i] = ...;	(4)
74 	  a[187*i + 50] = ...;	(5)
75 	}
76 
77        (0) obviously has PREFETCH_BEFORE 1
78        (1) has PREFETCH_BEFORE 64, since (2) accesses the same memory
79            location 64 iterations before it, and PREFETCH_MOD 64 (since
80 	   it hits the same cache line otherwise).
81        (2) has PREFETCH_MOD 64
82        (3) has PREFETCH_MOD 4
83        (4) has PREFETCH_MOD 1.  We do not set PREFETCH_BEFORE here, since
84            the cache line accessed by (5) is the same with probability only
85 	   7/32.
86        (5) has PREFETCH_MOD 1 as well.
87 
88       Additionally, we use data dependence analysis to determine for each
89       reference the distance till the first reuse; this information is used
90       to determine the temporality of the issued prefetch instruction.
91 
92    3) We determine how much ahead we need to prefetch.  The number of
93       iterations needed is time to fetch / time spent in one iteration of
94       the loop.  The problem is that we do not know either of these values,
95       so we just make a heuristic guess based on a magic (possibly)
96       target-specific constant and size of the loop.
97 
98    4) Determine which of the references we prefetch.  We take into account
99       that there is a maximum number of simultaneous prefetches (provided
100       by machine description).  We prefetch as many prefetches as possible
101       while still within this bound (starting with those with lowest
102       prefetch_mod, since they are responsible for most of the cache
103       misses).
104 
105    5) We unroll and peel loops so that we are able to satisfy PREFETCH_MOD
106       and PREFETCH_BEFORE requirements (within some bounds), and to avoid
107       prefetching nonaccessed memory.
108       TODO -- actually implement peeling.
109 
110    6) We actually emit the prefetch instructions.  ??? Perhaps emit the
111       prefetch instructions with guards in cases where 5) was not sufficient
112       to satisfy the constraints?
113 
114    A cost model is implemented to determine whether or not prefetching is
115    profitable for a given loop.  The cost model has three heuristics:
116 
117    1. Function trip_count_to_ahead_ratio_too_small_p implements a
118       heuristic that determines whether or not the loop has too few
119       iterations (compared to ahead).  Prefetching is not likely to be
120       beneficial if the trip count to ahead ratio is below a certain
121       minimum.
122 
123    2. Function mem_ref_count_reasonable_p implements a heuristic that
124       determines whether the given loop has enough CPU ops that can be
125       overlapped with cache missing memory ops.  If not, the loop
126       won't benefit from prefetching.  In the implementation,
127       prefetching is not considered beneficial if the ratio between
128       the instruction count and the mem ref count is below a certain
129       minimum.
130 
131    3. Function insn_to_prefetch_ratio_too_small_p implements a
132       heuristic that disables prefetching in a loop if the prefetching
133       cost is above a certain limit.  The relative prefetching cost is
134       estimated by taking the ratio between the prefetch count and the
135       total intruction count (this models the I-cache cost).
136 
137    The limits used in these heuristics are defined as parameters with
138    reasonable default values. Machine-specific default values will be
139    added later.
140 
141    Some other TODO:
142       -- write and use more general reuse analysis (that could be also used
143 	 in other cache aimed loop optimizations)
144       -- make it behave sanely together with the prefetches given by user
145 	 (now we just ignore them; at the very least we should avoid
146 	 optimizing loops in that user put his own prefetches)
147       -- we assume cache line size alignment of arrays; this could be
148 	 improved.  */
149 
150 /* Magic constants follow.  These should be replaced by machine specific
151    numbers.  */
152 
153 /* True if write can be prefetched by a read prefetch.  */
154 
155 #ifndef WRITE_CAN_USE_READ_PREFETCH
156 #define WRITE_CAN_USE_READ_PREFETCH 1
157 #endif
158 
159 /* True if read can be prefetched by a write prefetch. */
160 
161 #ifndef READ_CAN_USE_WRITE_PREFETCH
162 #define READ_CAN_USE_WRITE_PREFETCH 0
163 #endif
164 
165 /* The size of the block loaded by a single prefetch.  Usually, this is
166    the same as cache line size (at the moment, we only consider one level
167    of cache hierarchy).  */
168 
169 #ifndef PREFETCH_BLOCK
170 #define PREFETCH_BLOCK L1_CACHE_LINE_SIZE
171 #endif
172 
173 /* Do we have a forward hardware sequential prefetching?  */
174 
175 #ifndef HAVE_FORWARD_PREFETCH
176 #define HAVE_FORWARD_PREFETCH 0
177 #endif
178 
179 /* Do we have a backward hardware sequential prefetching?  */
180 
181 #ifndef HAVE_BACKWARD_PREFETCH
182 #define HAVE_BACKWARD_PREFETCH 0
183 #endif
184 
185 /* In some cases we are only able to determine that there is a certain
186    probability that the two accesses hit the same cache line.  In this
187    case, we issue the prefetches for both of them if this probability
188    is less then (1000 - ACCEPTABLE_MISS_RATE) per thousand.  */
189 
190 #ifndef ACCEPTABLE_MISS_RATE
191 #define ACCEPTABLE_MISS_RATE 50
192 #endif
193 
194 #define L1_CACHE_SIZE_BYTES ((unsigned) (L1_CACHE_SIZE * 1024))
195 #define L2_CACHE_SIZE_BYTES ((unsigned) (L2_CACHE_SIZE * 1024))
196 
197 /* We consider a memory access nontemporal if it is not reused sooner than
198    after L2_CACHE_SIZE_BYTES of memory are accessed.  However, we ignore
199    accesses closer than L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
200    so that we use nontemporal prefetches e.g. if single memory location
201    is accessed several times in a single iteration of the loop.  */
202 #define NONTEMPORAL_FRACTION 16
203 
204 /* In case we have to emit a memory fence instruction after the loop that
205    uses nontemporal stores, this defines the builtin to use.  */
206 
207 #ifndef FENCE_FOLLOWING_MOVNT
208 #define FENCE_FOLLOWING_MOVNT NULL_TREE
209 #endif
210 
211 /* It is not profitable to prefetch when the trip count is not at
212    least TRIP_COUNT_TO_AHEAD_RATIO times the prefetch ahead distance.
213    For example, in a loop with a prefetch ahead distance of 10,
214    supposing that TRIP_COUNT_TO_AHEAD_RATIO is equal to 4, it is
215    profitable to prefetch when the trip count is greater or equal to
216    40.  In that case, 30 out of the 40 iterations will benefit from
217    prefetching.  */
218 
219 #ifndef TRIP_COUNT_TO_AHEAD_RATIO
220 #define TRIP_COUNT_TO_AHEAD_RATIO 4
221 #endif
222 
223 /* The group of references between that reuse may occur.  */
224 
225 struct mem_ref_group
226 {
227   tree base;			/* Base of the reference.  */
228   tree step;			/* Step of the reference.  */
229   struct mem_ref *refs;		/* References in the group.  */
230   struct mem_ref_group *next;	/* Next group of references.  */
231   unsigned int uid;		/* Group UID, used only for debugging.  */
232 };
233 
234 /* Assigned to PREFETCH_BEFORE when all iterations are to be prefetched.  */
235 
236 #define PREFETCH_ALL		HOST_WIDE_INT_M1U
237 
238 /* Do not generate a prefetch if the unroll factor is significantly less
239    than what is required by the prefetch.  This is to avoid redundant
240    prefetches.  For example, when prefetch_mod is 16 and unroll_factor is
241    2, prefetching requires unrolling the loop 16 times, but
242    the loop is actually unrolled twice.  In this case (ratio = 8),
243    prefetching is not likely to be beneficial.  */
244 
245 #ifndef PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO
246 #define PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO 4
247 #endif
248 
249 /* Some of the prefetch computations have quadratic complexity.  We want to
250    avoid huge compile times and, therefore, want to limit the amount of
251    memory references per loop where we consider prefetching.  */
252 
253 #ifndef PREFETCH_MAX_MEM_REFS_PER_LOOP
254 #define PREFETCH_MAX_MEM_REFS_PER_LOOP 200
255 #endif
256 
257 /* The memory reference.  */
258 
259 struct mem_ref
260 {
261   gimple *stmt;			/* Statement in that the reference appears.  */
262   tree mem;			/* The reference.  */
263   HOST_WIDE_INT delta;		/* Constant offset of the reference.  */
264   struct mem_ref_group *group;	/* The group of references it belongs to.  */
265   unsigned HOST_WIDE_INT prefetch_mod;
266 				/* Prefetch only each PREFETCH_MOD-th
267 				   iteration.  */
268   unsigned HOST_WIDE_INT prefetch_before;
269 				/* Prefetch only first PREFETCH_BEFORE
270 				   iterations.  */
271   unsigned reuse_distance;	/* The amount of data accessed before the first
272 				   reuse of this value.  */
273   struct mem_ref *next;		/* The next reference in the group.  */
274   unsigned int uid;		/* Ref UID, used only for debugging.  */
275   unsigned write_p : 1;		/* Is it a write?  */
276   unsigned independent_p : 1;	/* True if the reference is independent on
277 				   all other references inside the loop.  */
278   unsigned issue_prefetch_p : 1;	/* Should we really issue the prefetch?  */
279   unsigned storent_p : 1;	/* True if we changed the store to a
280 				   nontemporal one.  */
281 };
282 
283 /* Dumps information about memory reference */
284 static void
dump_mem_details(FILE * file,tree base,tree step,HOST_WIDE_INT delta,bool write_p)285 dump_mem_details (FILE *file, tree base, tree step,
286 	    HOST_WIDE_INT delta, bool write_p)
287 {
288   fprintf (file, "(base ");
289   print_generic_expr (file, base, TDF_SLIM);
290   fprintf (file, ", step ");
291   if (cst_and_fits_in_hwi (step))
292     fprintf (file, HOST_WIDE_INT_PRINT_DEC, int_cst_value (step));
293   else
294     print_generic_expr (file, step, TDF_SLIM);
295   fprintf (file, ")\n");
296   fprintf (file, "  delta " HOST_WIDE_INT_PRINT_DEC "\n", delta);
297   fprintf (file, "  %s\n\n", write_p ? "write" : "read");
298 }
299 
300 /* Dumps information about reference REF to FILE.  */
301 
302 static void
dump_mem_ref(FILE * file,struct mem_ref * ref)303 dump_mem_ref (FILE *file, struct mem_ref *ref)
304 {
305   fprintf (file, "reference %u:%u (", ref->group->uid, ref->uid);
306   print_generic_expr (file, ref->mem, TDF_SLIM);
307   fprintf (file, ")\n");
308 }
309 
310 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
311    exist.  */
312 
313 static struct mem_ref_group *
find_or_create_group(struct mem_ref_group ** groups,tree base,tree step)314 find_or_create_group (struct mem_ref_group **groups, tree base, tree step)
315 {
316   /* Global count for setting struct mem_ref_group->uid.  */
317   static unsigned int last_mem_ref_group_uid = 0;
318 
319   struct mem_ref_group *group;
320 
321   for (; *groups; groups = &(*groups)->next)
322     {
323       if (operand_equal_p ((*groups)->step, step, 0)
324 	  && operand_equal_p ((*groups)->base, base, 0))
325 	return *groups;
326 
327       /* If step is an integer constant, keep the list of groups sorted
328          by decreasing step.  */
329       if (cst_and_fits_in_hwi ((*groups)->step) && cst_and_fits_in_hwi (step)
330 	  && int_cst_value ((*groups)->step) < int_cst_value (step))
331 	break;
332     }
333 
334   group = XNEW (struct mem_ref_group);
335   group->base = base;
336   group->step = step;
337   group->refs = NULL;
338   group->uid = ++last_mem_ref_group_uid;
339   group->next = *groups;
340   *groups = group;
341 
342   return group;
343 }
344 
345 /* Records a memory reference MEM in GROUP with offset DELTA and write status
346    WRITE_P.  The reference occurs in statement STMT.  */
347 
348 static void
record_ref(struct mem_ref_group * group,gimple * stmt,tree mem,HOST_WIDE_INT delta,bool write_p)349 record_ref (struct mem_ref_group *group, gimple *stmt, tree mem,
350 	    HOST_WIDE_INT delta, bool write_p)
351 {
352   unsigned int last_mem_ref_uid = 0;
353   struct mem_ref **aref;
354 
355   /* Do not record the same address twice.  */
356   for (aref = &group->refs; *aref; aref = &(*aref)->next)
357     {
358       last_mem_ref_uid = (*aref)->uid;
359 
360       /* It does not have to be possible for write reference to reuse the read
361 	 prefetch, or vice versa.  */
362       if (!WRITE_CAN_USE_READ_PREFETCH
363 	  && write_p
364 	  && !(*aref)->write_p)
365 	continue;
366       if (!READ_CAN_USE_WRITE_PREFETCH
367 	  && !write_p
368 	  && (*aref)->write_p)
369 	continue;
370 
371       if ((*aref)->delta == delta)
372 	return;
373     }
374 
375   (*aref) = XNEW (struct mem_ref);
376   (*aref)->stmt = stmt;
377   (*aref)->mem = mem;
378   (*aref)->delta = delta;
379   (*aref)->write_p = write_p;
380   (*aref)->prefetch_before = PREFETCH_ALL;
381   (*aref)->prefetch_mod = 1;
382   (*aref)->reuse_distance = 0;
383   (*aref)->issue_prefetch_p = false;
384   (*aref)->group = group;
385   (*aref)->next = NULL;
386   (*aref)->independent_p = false;
387   (*aref)->storent_p = false;
388   (*aref)->uid = last_mem_ref_uid + 1;
389 
390   if (dump_file && (dump_flags & TDF_DETAILS))
391     {
392       dump_mem_ref (dump_file, *aref);
393 
394       fprintf (dump_file, "  group %u ", group->uid);
395       dump_mem_details (dump_file, group->base, group->step, delta,
396 			write_p);
397     }
398 }
399 
400 /* Release memory references in GROUPS.  */
401 
402 static void
release_mem_refs(struct mem_ref_group * groups)403 release_mem_refs (struct mem_ref_group *groups)
404 {
405   struct mem_ref_group *next_g;
406   struct mem_ref *ref, *next_r;
407 
408   for (; groups; groups = next_g)
409     {
410       next_g = groups->next;
411       for (ref = groups->refs; ref; ref = next_r)
412 	{
413 	  next_r = ref->next;
414 	  free (ref);
415 	}
416       free (groups);
417     }
418 }
419 
420 /* A structure used to pass arguments to idx_analyze_ref.  */
421 
422 struct ar_data
423 {
424   struct loop *loop;			/* Loop of the reference.  */
425   gimple *stmt;				/* Statement of the reference.  */
426   tree *step;				/* Step of the memory reference.  */
427   HOST_WIDE_INT *delta;			/* Offset of the memory reference.  */
428 };
429 
430 /* Analyzes a single INDEX of a memory reference to obtain information
431    described at analyze_ref.  Callback for for_each_index.  */
432 
433 static bool
idx_analyze_ref(tree base,tree * index,void * data)434 idx_analyze_ref (tree base, tree *index, void *data)
435 {
436   struct ar_data *ar_data = (struct ar_data *) data;
437   tree ibase, step, stepsize;
438   HOST_WIDE_INT idelta = 0, imult = 1;
439   affine_iv iv;
440 
441   if (!simple_iv (ar_data->loop, loop_containing_stmt (ar_data->stmt),
442 		  *index, &iv, true))
443     return false;
444   ibase = iv.base;
445   step = iv.step;
446 
447   if (TREE_CODE (ibase) == POINTER_PLUS_EXPR
448       && cst_and_fits_in_hwi (TREE_OPERAND (ibase, 1)))
449     {
450       idelta = int_cst_value (TREE_OPERAND (ibase, 1));
451       ibase = TREE_OPERAND (ibase, 0);
452     }
453   if (cst_and_fits_in_hwi (ibase))
454     {
455       idelta += int_cst_value (ibase);
456       ibase = build_int_cst (TREE_TYPE (ibase), 0);
457     }
458 
459   if (TREE_CODE (base) == ARRAY_REF)
460     {
461       stepsize = array_ref_element_size (base);
462       if (!cst_and_fits_in_hwi (stepsize))
463 	return false;
464       imult = int_cst_value (stepsize);
465       step = fold_build2 (MULT_EXPR, sizetype,
466 			  fold_convert (sizetype, step),
467 			  fold_convert (sizetype, stepsize));
468       idelta *= imult;
469     }
470 
471   if (*ar_data->step == NULL_TREE)
472     *ar_data->step = step;
473   else
474     *ar_data->step = fold_build2 (PLUS_EXPR, sizetype,
475 				  fold_convert (sizetype, *ar_data->step),
476 				  fold_convert (sizetype, step));
477   *ar_data->delta += idelta;
478   *index = ibase;
479 
480   return true;
481 }
482 
483 /* Tries to express REF_P in shape &BASE + STEP * iter + DELTA, where DELTA and
484    STEP are integer constants and iter is number of iterations of LOOP.  The
485    reference occurs in statement STMT.  Strips nonaddressable component
486    references from REF_P.  */
487 
488 static bool
analyze_ref(struct loop * loop,tree * ref_p,tree * base,tree * step,HOST_WIDE_INT * delta,gimple * stmt)489 analyze_ref (struct loop *loop, tree *ref_p, tree *base,
490 	     tree *step, HOST_WIDE_INT *delta,
491 	     gimple *stmt)
492 {
493   struct ar_data ar_data;
494   tree off;
495   HOST_WIDE_INT bit_offset;
496   tree ref = *ref_p;
497 
498   *step = NULL_TREE;
499   *delta = 0;
500 
501   /* First strip off the component references.  Ignore bitfields.
502      Also strip off the real and imagine parts of a complex, so that
503      they can have the same base.  */
504   if (TREE_CODE (ref) == REALPART_EXPR
505       || TREE_CODE (ref) == IMAGPART_EXPR
506       || (TREE_CODE (ref) == COMPONENT_REF
507           && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref, 1))))
508     {
509       if (TREE_CODE (ref) == IMAGPART_EXPR)
510         *delta += int_size_in_bytes (TREE_TYPE (ref));
511       ref = TREE_OPERAND (ref, 0);
512     }
513 
514   *ref_p = ref;
515 
516   for (; TREE_CODE (ref) == COMPONENT_REF; ref = TREE_OPERAND (ref, 0))
517     {
518       off = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1));
519       bit_offset = TREE_INT_CST_LOW (off);
520       gcc_assert (bit_offset % BITS_PER_UNIT == 0);
521 
522       *delta += bit_offset / BITS_PER_UNIT;
523     }
524 
525   *base = unshare_expr (ref);
526   ar_data.loop = loop;
527   ar_data.stmt = stmt;
528   ar_data.step = step;
529   ar_data.delta = delta;
530   return for_each_index (base, idx_analyze_ref, &ar_data);
531 }
532 
533 /* Record a memory reference REF to the list REFS.  The reference occurs in
534    LOOP in statement STMT and it is write if WRITE_P.  Returns true if the
535    reference was recorded, false otherwise.  */
536 
537 static bool
gather_memory_references_ref(struct loop * loop,struct mem_ref_group ** refs,tree ref,bool write_p,gimple * stmt)538 gather_memory_references_ref (struct loop *loop, struct mem_ref_group **refs,
539 			      tree ref, bool write_p, gimple *stmt)
540 {
541   tree base, step;
542   HOST_WIDE_INT delta;
543   struct mem_ref_group *agrp;
544 
545   if (get_base_address (ref) == NULL)
546     return false;
547 
548   if (!analyze_ref (loop, &ref, &base, &step, &delta, stmt))
549     return false;
550   /* If analyze_ref fails the default is a NULL_TREE.  We can stop here.  */
551   if (step == NULL_TREE)
552     return false;
553 
554   /* Stop if the address of BASE could not be taken.  */
555   if (may_be_nonaddressable_p (base))
556     return false;
557 
558   /* Limit non-constant step prefetching only to the innermost loops and
559      only when the step is loop invariant in the entire loop nest. */
560   if (!cst_and_fits_in_hwi (step))
561     {
562       if (loop->inner != NULL)
563         {
564           if (dump_file && (dump_flags & TDF_DETAILS))
565             {
566               fprintf (dump_file, "Memory expression %p\n",(void *) ref );
567 	      print_generic_expr (dump_file, ref, TDF_SLIM);
568 	      fprintf (dump_file,":");
569               dump_mem_details (dump_file, base, step, delta, write_p);
570               fprintf (dump_file,
571                        "Ignoring %p, non-constant step prefetching is "
572                        "limited to inner most loops \n",
573                        (void *) ref);
574             }
575             return false;
576          }
577       else
578         {
579           if (!expr_invariant_in_loop_p (loop_outermost (loop), step))
580           {
581             if (dump_file && (dump_flags & TDF_DETAILS))
582               {
583                 fprintf (dump_file, "Memory expression %p\n",(void *) ref );
584 		print_generic_expr (dump_file, ref, TDF_SLIM);
585                 fprintf (dump_file,":");
586                 dump_mem_details (dump_file, base, step, delta, write_p);
587                 fprintf (dump_file,
588                          "Not prefetching, ignoring %p due to "
589                          "loop variant step\n",
590                          (void *) ref);
591               }
592               return false;
593             }
594         }
595     }
596 
597   /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
598      are integer constants.  */
599   agrp = find_or_create_group (refs, base, step);
600   record_ref (agrp, stmt, ref, delta, write_p);
601 
602   return true;
603 }
604 
605 /* Record the suitable memory references in LOOP.  NO_OTHER_REFS is set to
606    true if there are no other memory references inside the loop.  */
607 
608 static struct mem_ref_group *
gather_memory_references(struct loop * loop,bool * no_other_refs,unsigned * ref_count)609 gather_memory_references (struct loop *loop, bool *no_other_refs, unsigned *ref_count)
610 {
611   basic_block *body = get_loop_body_in_dom_order (loop);
612   basic_block bb;
613   unsigned i;
614   gimple_stmt_iterator bsi;
615   gimple *stmt;
616   tree lhs, rhs;
617   struct mem_ref_group *refs = NULL;
618 
619   *no_other_refs = true;
620   *ref_count = 0;
621 
622   /* Scan the loop body in order, so that the former references precede the
623      later ones.  */
624   for (i = 0; i < loop->num_nodes; i++)
625     {
626       bb = body[i];
627       if (bb->loop_father != loop)
628 	continue;
629 
630       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
631 	{
632 	  stmt = gsi_stmt (bsi);
633 
634 	  if (gimple_code (stmt) != GIMPLE_ASSIGN)
635 	    {
636 	      if (gimple_vuse (stmt)
637 		  || (is_gimple_call (stmt)
638 		      && !(gimple_call_flags (stmt) & ECF_CONST)))
639 		*no_other_refs = false;
640 	      continue;
641 	    }
642 
643 	  if (! gimple_vuse (stmt))
644 	    continue;
645 
646 	  lhs = gimple_assign_lhs (stmt);
647 	  rhs = gimple_assign_rhs1 (stmt);
648 
649 	  if (REFERENCE_CLASS_P (rhs))
650 	    {
651 	    *no_other_refs &= gather_memory_references_ref (loop, &refs,
652 							    rhs, false, stmt);
653 	    *ref_count += 1;
654 	    }
655 	  if (REFERENCE_CLASS_P (lhs))
656 	    {
657 	    *no_other_refs &= gather_memory_references_ref (loop, &refs,
658 							    lhs, true, stmt);
659 	    *ref_count += 1;
660 	    }
661 	}
662     }
663   free (body);
664 
665   return refs;
666 }
667 
668 /* Prune the prefetch candidate REF using the self-reuse.  */
669 
670 static void
prune_ref_by_self_reuse(struct mem_ref * ref)671 prune_ref_by_self_reuse (struct mem_ref *ref)
672 {
673   HOST_WIDE_INT step;
674   bool backward;
675 
676   /* If the step size is non constant, we cannot calculate prefetch_mod.  */
677   if (!cst_and_fits_in_hwi (ref->group->step))
678     return;
679 
680   step = int_cst_value (ref->group->step);
681 
682   backward = step < 0;
683 
684   if (step == 0)
685     {
686       /* Prefetch references to invariant address just once.  */
687       ref->prefetch_before = 1;
688       return;
689     }
690 
691   if (backward)
692     step = -step;
693 
694   if (step > PREFETCH_BLOCK)
695     return;
696 
697   if ((backward && HAVE_BACKWARD_PREFETCH)
698       || (!backward && HAVE_FORWARD_PREFETCH))
699     {
700       ref->prefetch_before = 1;
701       return;
702     }
703 
704   ref->prefetch_mod = PREFETCH_BLOCK / step;
705 }
706 
707 /* Divides X by BY, rounding down.  */
708 
709 static HOST_WIDE_INT
ddown(HOST_WIDE_INT x,unsigned HOST_WIDE_INT by)710 ddown (HOST_WIDE_INT x, unsigned HOST_WIDE_INT by)
711 {
712   gcc_assert (by > 0);
713 
714   if (x >= 0)
715     return x / (HOST_WIDE_INT) by;
716   else
717     return (x + (HOST_WIDE_INT) by - 1) / (HOST_WIDE_INT) by;
718 }
719 
720 /* Given a CACHE_LINE_SIZE and two inductive memory references
721    with a common STEP greater than CACHE_LINE_SIZE and an address
722    difference DELTA, compute the probability that they will fall
723    in different cache lines.  Return true if the computed miss rate
724    is not greater than the ACCEPTABLE_MISS_RATE.  DISTINCT_ITERS is the
725    number of distinct iterations after which the pattern repeats itself.
726    ALIGN_UNIT is the unit of alignment in bytes.  */
727 
728 static bool
is_miss_rate_acceptable(unsigned HOST_WIDE_INT cache_line_size,HOST_WIDE_INT step,HOST_WIDE_INT delta,unsigned HOST_WIDE_INT distinct_iters,int align_unit)729 is_miss_rate_acceptable (unsigned HOST_WIDE_INT cache_line_size,
730 		   HOST_WIDE_INT step, HOST_WIDE_INT delta,
731 		   unsigned HOST_WIDE_INT distinct_iters,
732 		   int align_unit)
733 {
734   unsigned align, iter;
735   int total_positions, miss_positions, max_allowed_miss_positions;
736   int address1, address2, cache_line1, cache_line2;
737 
738   /* It always misses if delta is greater than or equal to the cache
739      line size.  */
740   if (delta >= (HOST_WIDE_INT) cache_line_size)
741     return false;
742 
743   miss_positions = 0;
744   total_positions = (cache_line_size / align_unit) * distinct_iters;
745   max_allowed_miss_positions = (ACCEPTABLE_MISS_RATE * total_positions) / 1000;
746 
747   /* Iterate through all possible alignments of the first
748      memory reference within its cache line.  */
749   for (align = 0; align < cache_line_size; align += align_unit)
750 
751     /* Iterate through all distinct iterations.  */
752     for (iter = 0; iter < distinct_iters; iter++)
753       {
754 	address1 = align + step * iter;
755 	address2 = address1 + delta;
756 	cache_line1 = address1 / cache_line_size;
757 	cache_line2 = address2 / cache_line_size;
758 	if (cache_line1 != cache_line2)
759 	  {
760 	    miss_positions += 1;
761             if (miss_positions > max_allowed_miss_positions)
762 	      return false;
763           }
764       }
765   return true;
766 }
767 
768 /* Prune the prefetch candidate REF using the reuse with BY.
769    If BY_IS_BEFORE is true, BY is before REF in the loop.  */
770 
771 static void
prune_ref_by_group_reuse(struct mem_ref * ref,struct mem_ref * by,bool by_is_before)772 prune_ref_by_group_reuse (struct mem_ref *ref, struct mem_ref *by,
773 			  bool by_is_before)
774 {
775   HOST_WIDE_INT step;
776   bool backward;
777   HOST_WIDE_INT delta_r = ref->delta, delta_b = by->delta;
778   HOST_WIDE_INT delta = delta_b - delta_r;
779   HOST_WIDE_INT hit_from;
780   unsigned HOST_WIDE_INT prefetch_before, prefetch_block;
781   HOST_WIDE_INT reduced_step;
782   unsigned HOST_WIDE_INT reduced_prefetch_block;
783   tree ref_type;
784   int align_unit;
785 
786   /* If the step is non constant we cannot calculate prefetch_before.  */
787   if (!cst_and_fits_in_hwi (ref->group->step)) {
788     return;
789   }
790 
791   step = int_cst_value (ref->group->step);
792 
793   backward = step < 0;
794 
795 
796   if (delta == 0)
797     {
798       /* If the references has the same address, only prefetch the
799 	 former.  */
800       if (by_is_before)
801 	ref->prefetch_before = 0;
802 
803       return;
804     }
805 
806   if (!step)
807     {
808       /* If the reference addresses are invariant and fall into the
809 	 same cache line, prefetch just the first one.  */
810       if (!by_is_before)
811 	return;
812 
813       if (ddown (ref->delta, PREFETCH_BLOCK)
814 	  != ddown (by->delta, PREFETCH_BLOCK))
815 	return;
816 
817       ref->prefetch_before = 0;
818       return;
819     }
820 
821   /* Only prune the reference that is behind in the array.  */
822   if (backward)
823     {
824       if (delta > 0)
825 	return;
826 
827       /* Transform the data so that we may assume that the accesses
828 	 are forward.  */
829       delta = - delta;
830       step = -step;
831       delta_r = PREFETCH_BLOCK - 1 - delta_r;
832       delta_b = PREFETCH_BLOCK - 1 - delta_b;
833     }
834   else
835     {
836       if (delta < 0)
837 	return;
838     }
839 
840   /* Check whether the two references are likely to hit the same cache
841      line, and how distant the iterations in that it occurs are from
842      each other.  */
843 
844   if (step <= PREFETCH_BLOCK)
845     {
846       /* The accesses are sure to meet.  Let us check when.  */
847       hit_from = ddown (delta_b, PREFETCH_BLOCK) * PREFETCH_BLOCK;
848       prefetch_before = (hit_from - delta_r + step - 1) / step;
849 
850       /* Do not reduce prefetch_before if we meet beyond cache size.  */
851       if (prefetch_before > absu_hwi (L2_CACHE_SIZE_BYTES / step))
852         prefetch_before = PREFETCH_ALL;
853       if (prefetch_before < ref->prefetch_before)
854 	ref->prefetch_before = prefetch_before;
855 
856       return;
857     }
858 
859   /* A more complicated case with step > prefetch_block.  First reduce
860      the ratio between the step and the cache line size to its simplest
861      terms.  The resulting denominator will then represent the number of
862      distinct iterations after which each address will go back to its
863      initial location within the cache line.  This computation assumes
864      that PREFETCH_BLOCK is a power of two.  */
865   prefetch_block = PREFETCH_BLOCK;
866   reduced_prefetch_block = prefetch_block;
867   reduced_step = step;
868   while ((reduced_step & 1) == 0
869 	 && reduced_prefetch_block > 1)
870     {
871       reduced_step >>= 1;
872       reduced_prefetch_block >>= 1;
873     }
874 
875   prefetch_before = delta / step;
876   delta %= step;
877   ref_type = TREE_TYPE (ref->mem);
878   align_unit = TYPE_ALIGN (ref_type) / 8;
879   if (is_miss_rate_acceptable (prefetch_block, step, delta,
880 			       reduced_prefetch_block, align_unit))
881     {
882       /* Do not reduce prefetch_before if we meet beyond cache size.  */
883       if (prefetch_before > L2_CACHE_SIZE_BYTES / PREFETCH_BLOCK)
884         prefetch_before = PREFETCH_ALL;
885       if (prefetch_before < ref->prefetch_before)
886 	ref->prefetch_before = prefetch_before;
887 
888       return;
889     }
890 
891   /* Try also the following iteration.  */
892   prefetch_before++;
893   delta = step - delta;
894   if (is_miss_rate_acceptable (prefetch_block, step, delta,
895 			       reduced_prefetch_block, align_unit))
896     {
897       if (prefetch_before < ref->prefetch_before)
898 	ref->prefetch_before = prefetch_before;
899 
900       return;
901     }
902 
903   /* The ref probably does not reuse by.  */
904   return;
905 }
906 
907 /* Prune the prefetch candidate REF using the reuses with other references
908    in REFS.  */
909 
910 static void
prune_ref_by_reuse(struct mem_ref * ref,struct mem_ref * refs)911 prune_ref_by_reuse (struct mem_ref *ref, struct mem_ref *refs)
912 {
913   struct mem_ref *prune_by;
914   bool before = true;
915 
916   prune_ref_by_self_reuse (ref);
917 
918   for (prune_by = refs; prune_by; prune_by = prune_by->next)
919     {
920       if (prune_by == ref)
921 	{
922 	  before = false;
923 	  continue;
924 	}
925 
926       if (!WRITE_CAN_USE_READ_PREFETCH
927 	  && ref->write_p
928 	  && !prune_by->write_p)
929 	continue;
930       if (!READ_CAN_USE_WRITE_PREFETCH
931 	  && !ref->write_p
932 	  && prune_by->write_p)
933 	continue;
934 
935       prune_ref_by_group_reuse (ref, prune_by, before);
936     }
937 }
938 
939 /* Prune the prefetch candidates in GROUP using the reuse analysis.  */
940 
941 static void
prune_group_by_reuse(struct mem_ref_group * group)942 prune_group_by_reuse (struct mem_ref_group *group)
943 {
944   struct mem_ref *ref_pruned;
945 
946   for (ref_pruned = group->refs; ref_pruned; ref_pruned = ref_pruned->next)
947     {
948       prune_ref_by_reuse (ref_pruned, group->refs);
949 
950       if (dump_file && (dump_flags & TDF_DETAILS))
951 	{
952 	  dump_mem_ref (dump_file, ref_pruned);
953 
954 	  if (ref_pruned->prefetch_before == PREFETCH_ALL
955 	      && ref_pruned->prefetch_mod == 1)
956 	    fprintf (dump_file, " no restrictions");
957 	  else if (ref_pruned->prefetch_before == 0)
958 	    fprintf (dump_file, " do not prefetch");
959 	  else if (ref_pruned->prefetch_before <= ref_pruned->prefetch_mod)
960 	    fprintf (dump_file, " prefetch once");
961 	  else
962 	    {
963 	      if (ref_pruned->prefetch_before != PREFETCH_ALL)
964 		{
965 		  fprintf (dump_file, " prefetch before ");
966 		  fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC,
967 			   ref_pruned->prefetch_before);
968 		}
969 	      if (ref_pruned->prefetch_mod != 1)
970 		{
971 		  fprintf (dump_file, " prefetch mod ");
972 		  fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC,
973 			   ref_pruned->prefetch_mod);
974 		}
975 	    }
976 	  fprintf (dump_file, "\n");
977 	}
978     }
979 }
980 
981 /* Prune the list of prefetch candidates GROUPS using the reuse analysis.  */
982 
983 static void
prune_by_reuse(struct mem_ref_group * groups)984 prune_by_reuse (struct mem_ref_group *groups)
985 {
986   for (; groups; groups = groups->next)
987     prune_group_by_reuse (groups);
988 }
989 
990 /* Returns true if we should issue prefetch for REF.  */
991 
992 static bool
should_issue_prefetch_p(struct mem_ref * ref)993 should_issue_prefetch_p (struct mem_ref *ref)
994 {
995   /* For now do not issue prefetches for only first few of the
996      iterations.  */
997   if (ref->prefetch_before != PREFETCH_ALL)
998     {
999       if (dump_file && (dump_flags & TDF_DETAILS))
1000         fprintf (dump_file, "Ignoring reference %u:%u due to prefetch_before\n",
1001 		 ref->group->uid, ref->uid);
1002       return false;
1003     }
1004 
1005   /* Do not prefetch nontemporal stores.  */
1006   if (ref->storent_p)
1007     {
1008       if (dump_file && (dump_flags & TDF_DETAILS))
1009         fprintf (dump_file, "Ignoring nontemporal store reference %u:%u\n", ref->group->uid, ref->uid);
1010       return false;
1011     }
1012 
1013   return true;
1014 }
1015 
1016 /* Decide which of the prefetch candidates in GROUPS to prefetch.
1017    AHEAD is the number of iterations to prefetch ahead (which corresponds
1018    to the number of simultaneous instances of one prefetch running at a
1019    time).  UNROLL_FACTOR is the factor by that the loop is going to be
1020    unrolled.  Returns true if there is anything to prefetch.  */
1021 
1022 static bool
schedule_prefetches(struct mem_ref_group * groups,unsigned unroll_factor,unsigned ahead)1023 schedule_prefetches (struct mem_ref_group *groups, unsigned unroll_factor,
1024 		     unsigned ahead)
1025 {
1026   unsigned remaining_prefetch_slots, n_prefetches, prefetch_slots;
1027   unsigned slots_per_prefetch;
1028   struct mem_ref *ref;
1029   bool any = false;
1030 
1031   /* At most SIMULTANEOUS_PREFETCHES should be running at the same time.  */
1032   remaining_prefetch_slots = SIMULTANEOUS_PREFETCHES;
1033 
1034   /* The prefetch will run for AHEAD iterations of the original loop, i.e.,
1035      AHEAD / UNROLL_FACTOR iterations of the unrolled loop.  In each iteration,
1036      it will need a prefetch slot.  */
1037   slots_per_prefetch = (ahead + unroll_factor / 2) / unroll_factor;
1038   if (dump_file && (dump_flags & TDF_DETAILS))
1039     fprintf (dump_file, "Each prefetch instruction takes %u prefetch slots.\n",
1040 	     slots_per_prefetch);
1041 
1042   /* For now we just take memory references one by one and issue
1043      prefetches for as many as possible.  The groups are sorted
1044      starting with the largest step, since the references with
1045      large step are more likely to cause many cache misses.  */
1046 
1047   for (; groups; groups = groups->next)
1048     for (ref = groups->refs; ref; ref = ref->next)
1049       {
1050 	if (!should_issue_prefetch_p (ref))
1051 	  continue;
1052 
1053         /* The loop is far from being sufficiently unrolled for this
1054            prefetch.  Do not generate prefetch to avoid many redudant
1055            prefetches.  */
1056         if (ref->prefetch_mod / unroll_factor > PREFETCH_MOD_TO_UNROLL_FACTOR_RATIO)
1057           continue;
1058 
1059 	/* If we need to prefetch the reference each PREFETCH_MOD iterations,
1060 	   and we unroll the loop UNROLL_FACTOR times, we need to insert
1061 	   ceil (UNROLL_FACTOR / PREFETCH_MOD) instructions in each
1062 	   iteration.  */
1063 	n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
1064 			/ ref->prefetch_mod);
1065 	prefetch_slots = n_prefetches * slots_per_prefetch;
1066 
1067 	/* If more than half of the prefetches would be lost anyway, do not
1068 	   issue the prefetch.  */
1069 	if (2 * remaining_prefetch_slots < prefetch_slots)
1070 	  continue;
1071 
1072 	/* Stop prefetching if debug counter is activated.  */
1073 	if (!dbg_cnt (prefetch))
1074 	  continue;
1075 
1076 	ref->issue_prefetch_p = true;
1077 	if (dump_file && (dump_flags & TDF_DETAILS))
1078 	  fprintf (dump_file, "Decided to issue prefetch for reference %u:%u\n",
1079 		   ref->group->uid, ref->uid);
1080 
1081 	if (remaining_prefetch_slots <= prefetch_slots)
1082 	  return true;
1083 	remaining_prefetch_slots -= prefetch_slots;
1084 	any = true;
1085       }
1086 
1087   return any;
1088 }
1089 
1090 /* Return TRUE if no prefetch is going to be generated in the given
1091    GROUPS.  */
1092 
1093 static bool
nothing_to_prefetch_p(struct mem_ref_group * groups)1094 nothing_to_prefetch_p (struct mem_ref_group *groups)
1095 {
1096   struct mem_ref *ref;
1097 
1098   for (; groups; groups = groups->next)
1099     for (ref = groups->refs; ref; ref = ref->next)
1100       if (should_issue_prefetch_p (ref))
1101 	return false;
1102 
1103   return true;
1104 }
1105 
1106 /* Estimate the number of prefetches in the given GROUPS.
1107    UNROLL_FACTOR is the factor by which LOOP was unrolled.  */
1108 
1109 static int
estimate_prefetch_count(struct mem_ref_group * groups,unsigned unroll_factor)1110 estimate_prefetch_count (struct mem_ref_group *groups, unsigned unroll_factor)
1111 {
1112   struct mem_ref *ref;
1113   unsigned n_prefetches;
1114   int prefetch_count = 0;
1115 
1116   for (; groups; groups = groups->next)
1117     for (ref = groups->refs; ref; ref = ref->next)
1118       if (should_issue_prefetch_p (ref))
1119 	{
1120 	  n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
1121 			  / ref->prefetch_mod);
1122 	  prefetch_count += n_prefetches;
1123 	}
1124 
1125   return prefetch_count;
1126 }
1127 
1128 /* Issue prefetches for the reference REF into loop as decided before.
1129    HEAD is the number of iterations to prefetch ahead.  UNROLL_FACTOR
1130    is the factor by which LOOP was unrolled.  */
1131 
1132 static void
issue_prefetch_ref(struct mem_ref * ref,unsigned unroll_factor,unsigned ahead)1133 issue_prefetch_ref (struct mem_ref *ref, unsigned unroll_factor, unsigned ahead)
1134 {
1135   HOST_WIDE_INT delta;
1136   tree addr, addr_base, write_p, local, forward;
1137   gcall *prefetch;
1138   gimple_stmt_iterator bsi;
1139   unsigned n_prefetches, ap;
1140   bool nontemporal = ref->reuse_distance >= L2_CACHE_SIZE_BYTES;
1141 
1142   if (dump_file && (dump_flags & TDF_DETAILS))
1143     fprintf (dump_file, "Issued%s prefetch for reference %u:%u.\n",
1144 	     nontemporal ? " nontemporal" : "",
1145 	     ref->group->uid, ref->uid);
1146 
1147   bsi = gsi_for_stmt (ref->stmt);
1148 
1149   n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
1150 		  / ref->prefetch_mod);
1151   addr_base = build_fold_addr_expr_with_type (ref->mem, ptr_type_node);
1152   addr_base = force_gimple_operand_gsi (&bsi, unshare_expr (addr_base),
1153 					true, NULL, true, GSI_SAME_STMT);
1154   write_p = ref->write_p ? integer_one_node : integer_zero_node;
1155   local = nontemporal ? integer_zero_node : integer_three_node;
1156 
1157   for (ap = 0; ap < n_prefetches; ap++)
1158     {
1159       if (cst_and_fits_in_hwi (ref->group->step))
1160         {
1161           /* Determine the address to prefetch.  */
1162           delta = (ahead + ap * ref->prefetch_mod) *
1163 		   int_cst_value (ref->group->step);
1164           addr = fold_build_pointer_plus_hwi (addr_base, delta);
1165           addr = force_gimple_operand_gsi (&bsi, unshare_expr (addr), true,
1166 					   NULL, true, GSI_SAME_STMT);
1167         }
1168       else
1169         {
1170           /* The step size is non-constant but loop-invariant.  We use the
1171              heuristic to simply prefetch ahead iterations ahead.  */
1172           forward = fold_build2 (MULT_EXPR, sizetype,
1173                                  fold_convert (sizetype, ref->group->step),
1174                                  fold_convert (sizetype, size_int (ahead)));
1175           addr = fold_build_pointer_plus (addr_base, forward);
1176           addr = force_gimple_operand_gsi (&bsi, unshare_expr (addr), true,
1177 					   NULL, true, GSI_SAME_STMT);
1178       }
1179 
1180       if (addr_base != addr
1181 	  && TREE_CODE (addr_base) == SSA_NAME
1182 	  && TREE_CODE (addr) == SSA_NAME)
1183 	{
1184 	  duplicate_ssa_name_ptr_info (addr, SSA_NAME_PTR_INFO (addr_base));
1185 	  /* As this isn't a plain copy we have to reset alignment
1186 	     information.  */
1187 	  if (SSA_NAME_PTR_INFO (addr))
1188 	    mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (addr));
1189 	}
1190 
1191       /* Create the prefetch instruction.  */
1192       prefetch = gimple_build_call (builtin_decl_explicit (BUILT_IN_PREFETCH),
1193 				    3, addr, write_p, local);
1194       gsi_insert_before (&bsi, prefetch, GSI_SAME_STMT);
1195     }
1196 }
1197 
1198 /* Issue prefetches for the references in GROUPS into loop as decided before.
1199    HEAD is the number of iterations to prefetch ahead.  UNROLL_FACTOR is the
1200    factor by that LOOP was unrolled.  */
1201 
1202 static void
issue_prefetches(struct mem_ref_group * groups,unsigned unroll_factor,unsigned ahead)1203 issue_prefetches (struct mem_ref_group *groups,
1204 		  unsigned unroll_factor, unsigned ahead)
1205 {
1206   struct mem_ref *ref;
1207 
1208   for (; groups; groups = groups->next)
1209     for (ref = groups->refs; ref; ref = ref->next)
1210       if (ref->issue_prefetch_p)
1211 	issue_prefetch_ref (ref, unroll_factor, ahead);
1212 }
1213 
1214 /* Returns true if REF is a memory write for that a nontemporal store insn
1215    can be used.  */
1216 
1217 static bool
nontemporal_store_p(struct mem_ref * ref)1218 nontemporal_store_p (struct mem_ref *ref)
1219 {
1220   machine_mode mode;
1221   enum insn_code code;
1222 
1223   /* REF must be a write that is not reused.  We require it to be independent
1224      on all other memory references in the loop, as the nontemporal stores may
1225      be reordered with respect to other memory references.  */
1226   if (!ref->write_p
1227       || !ref->independent_p
1228       || ref->reuse_distance < L2_CACHE_SIZE_BYTES)
1229     return false;
1230 
1231   /* Check that we have the storent instruction for the mode.  */
1232   mode = TYPE_MODE (TREE_TYPE (ref->mem));
1233   if (mode == BLKmode)
1234     return false;
1235 
1236   code = optab_handler (storent_optab, mode);
1237   return code != CODE_FOR_nothing;
1238 }
1239 
1240 /* If REF is a nontemporal store, we mark the corresponding modify statement
1241    and return true.  Otherwise, we return false.  */
1242 
1243 static bool
mark_nontemporal_store(struct mem_ref * ref)1244 mark_nontemporal_store (struct mem_ref *ref)
1245 {
1246   if (!nontemporal_store_p (ref))
1247     return false;
1248 
1249   if (dump_file && (dump_flags & TDF_DETAILS))
1250     fprintf (dump_file, "Marked reference %u:%u as a nontemporal store.\n",
1251 	     ref->group->uid, ref->uid);
1252 
1253   gimple_assign_set_nontemporal_move (ref->stmt, true);
1254   ref->storent_p = true;
1255 
1256   return true;
1257 }
1258 
1259 /* Issue a memory fence instruction after LOOP.  */
1260 
1261 static void
emit_mfence_after_loop(struct loop * loop)1262 emit_mfence_after_loop (struct loop *loop)
1263 {
1264   vec<edge> exits = get_loop_exit_edges (loop);
1265   edge exit;
1266   gcall *call;
1267   gimple_stmt_iterator bsi;
1268   unsigned i;
1269 
1270   FOR_EACH_VEC_ELT (exits, i, exit)
1271     {
1272       call = gimple_build_call (FENCE_FOLLOWING_MOVNT, 0);
1273 
1274       if (!single_pred_p (exit->dest)
1275 	  /* If possible, we prefer not to insert the fence on other paths
1276 	     in cfg.  */
1277 	  && !(exit->flags & EDGE_ABNORMAL))
1278 	split_loop_exit_edge (exit);
1279       bsi = gsi_after_labels (exit->dest);
1280 
1281       gsi_insert_before (&bsi, call, GSI_NEW_STMT);
1282     }
1283 
1284   exits.release ();
1285   update_ssa (TODO_update_ssa_only_virtuals);
1286 }
1287 
1288 /* Returns true if we can use storent in loop, false otherwise.  */
1289 
1290 static bool
may_use_storent_in_loop_p(struct loop * loop)1291 may_use_storent_in_loop_p (struct loop *loop)
1292 {
1293   bool ret = true;
1294 
1295   if (loop->inner != NULL)
1296     return false;
1297 
1298   /* If we must issue a mfence insn after using storent, check that there
1299      is a suitable place for it at each of the loop exits.  */
1300   if (FENCE_FOLLOWING_MOVNT != NULL_TREE)
1301     {
1302       vec<edge> exits = get_loop_exit_edges (loop);
1303       unsigned i;
1304       edge exit;
1305 
1306       FOR_EACH_VEC_ELT (exits, i, exit)
1307 	if ((exit->flags & EDGE_ABNORMAL)
1308 	    && exit->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1309 	  ret = false;
1310 
1311       exits.release ();
1312     }
1313 
1314   return ret;
1315 }
1316 
1317 /* Marks nontemporal stores in LOOP.  GROUPS contains the description of memory
1318    references in the loop.  */
1319 
1320 static void
mark_nontemporal_stores(struct loop * loop,struct mem_ref_group * groups)1321 mark_nontemporal_stores (struct loop *loop, struct mem_ref_group *groups)
1322 {
1323   struct mem_ref *ref;
1324   bool any = false;
1325 
1326   if (!may_use_storent_in_loop_p (loop))
1327     return;
1328 
1329   for (; groups; groups = groups->next)
1330     for (ref = groups->refs; ref; ref = ref->next)
1331       any |= mark_nontemporal_store (ref);
1332 
1333   if (any && FENCE_FOLLOWING_MOVNT != NULL_TREE)
1334     emit_mfence_after_loop (loop);
1335 }
1336 
1337 /* Determines whether we can profitably unroll LOOP FACTOR times, and if
1338    this is the case, fill in DESC by the description of number of
1339    iterations.  */
1340 
1341 static bool
should_unroll_loop_p(struct loop * loop,struct tree_niter_desc * desc,unsigned factor)1342 should_unroll_loop_p (struct loop *loop, struct tree_niter_desc *desc,
1343 		      unsigned factor)
1344 {
1345   if (!can_unroll_loop_p (loop, factor, desc))
1346     return false;
1347 
1348   /* We only consider loops without control flow for unrolling.  This is not
1349      a hard restriction -- tree_unroll_loop works with arbitrary loops
1350      as well; but the unrolling/prefetching is usually more profitable for
1351      loops consisting of a single basic block, and we want to limit the
1352      code growth.  */
1353   if (loop->num_nodes > 2)
1354     return false;
1355 
1356   return true;
1357 }
1358 
1359 /* Determine the coefficient by that unroll LOOP, from the information
1360    contained in the list of memory references REFS.  Description of
1361    number of iterations of LOOP is stored to DESC.  NINSNS is the number of
1362    insns of the LOOP.  EST_NITER is the estimated number of iterations of
1363    the loop, or -1 if no estimate is available.  */
1364 
1365 static unsigned
determine_unroll_factor(struct loop * loop,struct mem_ref_group * refs,unsigned ninsns,struct tree_niter_desc * desc,HOST_WIDE_INT est_niter)1366 determine_unroll_factor (struct loop *loop, struct mem_ref_group *refs,
1367 			 unsigned ninsns, struct tree_niter_desc *desc,
1368 			 HOST_WIDE_INT est_niter)
1369 {
1370   unsigned upper_bound;
1371   unsigned nfactor, factor, mod_constraint;
1372   struct mem_ref_group *agp;
1373   struct mem_ref *ref;
1374 
1375   /* First check whether the loop is not too large to unroll.  We ignore
1376      PARAM_MAX_UNROLL_TIMES, because for small loops, it prevented us
1377      from unrolling them enough to make exactly one cache line covered by each
1378      iteration.  Also, the goal of PARAM_MAX_UNROLL_TIMES is to prevent
1379      us from unrolling the loops too many times in cases where we only expect
1380      gains from better scheduling and decreasing loop overhead, which is not
1381      the case here.  */
1382   upper_bound = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / ninsns;
1383 
1384   /* If we unrolled the loop more times than it iterates, the unrolled version
1385      of the loop would be never entered.  */
1386   if (est_niter >= 0 && est_niter < (HOST_WIDE_INT) upper_bound)
1387     upper_bound = est_niter;
1388 
1389   if (upper_bound <= 1)
1390     return 1;
1391 
1392   /* Choose the factor so that we may prefetch each cache just once,
1393      but bound the unrolling by UPPER_BOUND.  */
1394   factor = 1;
1395   for (agp = refs; agp; agp = agp->next)
1396     for (ref = agp->refs; ref; ref = ref->next)
1397       if (should_issue_prefetch_p (ref))
1398 	{
1399 	  mod_constraint = ref->prefetch_mod;
1400 	  nfactor = least_common_multiple (mod_constraint, factor);
1401 	  if (nfactor <= upper_bound)
1402 	    factor = nfactor;
1403 	}
1404 
1405   if (!should_unroll_loop_p (loop, desc, factor))
1406     return 1;
1407 
1408   return factor;
1409 }
1410 
1411 /* Returns the total volume of the memory references REFS, taking into account
1412    reuses in the innermost loop and cache line size.  TODO -- we should also
1413    take into account reuses across the iterations of the loops in the loop
1414    nest.  */
1415 
1416 static unsigned
volume_of_references(struct mem_ref_group * refs)1417 volume_of_references (struct mem_ref_group *refs)
1418 {
1419   unsigned volume = 0;
1420   struct mem_ref_group *gr;
1421   struct mem_ref *ref;
1422 
1423   for (gr = refs; gr; gr = gr->next)
1424     for (ref = gr->refs; ref; ref = ref->next)
1425       {
1426 	/* Almost always reuses another value?  */
1427 	if (ref->prefetch_before != PREFETCH_ALL)
1428 	  continue;
1429 
1430 	/* If several iterations access the same cache line, use the size of
1431 	   the line divided by this number.  Otherwise, a cache line is
1432 	   accessed in each iteration.  TODO -- in the latter case, we should
1433 	   take the size of the reference into account, rounding it up on cache
1434 	   line size multiple.  */
1435 	volume += L1_CACHE_LINE_SIZE / ref->prefetch_mod;
1436       }
1437   return volume;
1438 }
1439 
1440 /* Returns the volume of memory references accessed across VEC iterations of
1441    loops, whose sizes are described in the LOOP_SIZES array.  N is the number
1442    of the loops in the nest (length of VEC and LOOP_SIZES vectors).  */
1443 
1444 static unsigned
volume_of_dist_vector(lambda_vector vec,unsigned * loop_sizes,unsigned n)1445 volume_of_dist_vector (lambda_vector vec, unsigned *loop_sizes, unsigned n)
1446 {
1447   unsigned i;
1448 
1449   for (i = 0; i < n; i++)
1450     if (vec[i] != 0)
1451       break;
1452 
1453   if (i == n)
1454     return 0;
1455 
1456   gcc_assert (vec[i] > 0);
1457 
1458   /* We ignore the parts of the distance vector in subloops, since usually
1459      the numbers of iterations are much smaller.  */
1460   return loop_sizes[i] * vec[i];
1461 }
1462 
1463 /* Add the steps of ACCESS_FN multiplied by STRIDE to the array STRIDE
1464    at the position corresponding to the loop of the step.  N is the depth
1465    of the considered loop nest, and, LOOP is its innermost loop.  */
1466 
1467 static void
add_subscript_strides(tree access_fn,unsigned stride,HOST_WIDE_INT * strides,unsigned n,struct loop * loop)1468 add_subscript_strides (tree access_fn, unsigned stride,
1469 		       HOST_WIDE_INT *strides, unsigned n, struct loop *loop)
1470 {
1471   struct loop *aloop;
1472   tree step;
1473   HOST_WIDE_INT astep;
1474   unsigned min_depth = loop_depth (loop) - n;
1475 
1476   while (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
1477     {
1478       aloop = get_chrec_loop (access_fn);
1479       step = CHREC_RIGHT (access_fn);
1480       access_fn = CHREC_LEFT (access_fn);
1481 
1482       if ((unsigned) loop_depth (aloop) <= min_depth)
1483 	continue;
1484 
1485       if (tree_fits_shwi_p (step))
1486 	astep = tree_to_shwi (step);
1487       else
1488 	astep = L1_CACHE_LINE_SIZE;
1489 
1490       strides[n - 1 - loop_depth (loop) + loop_depth (aloop)] += astep * stride;
1491 
1492     }
1493 }
1494 
1495 /* Returns the volume of memory references accessed between two consecutive
1496    self-reuses of the reference DR.  We consider the subscripts of DR in N
1497    loops, and LOOP_SIZES contains the volumes of accesses in each of the
1498    loops.  LOOP is the innermost loop of the current loop nest.  */
1499 
1500 static unsigned
self_reuse_distance(data_reference_p dr,unsigned * loop_sizes,unsigned n,struct loop * loop)1501 self_reuse_distance (data_reference_p dr, unsigned *loop_sizes, unsigned n,
1502 		     struct loop *loop)
1503 {
1504   tree stride, access_fn;
1505   HOST_WIDE_INT *strides, astride;
1506   vec<tree> access_fns;
1507   tree ref = DR_REF (dr);
1508   unsigned i, ret = ~0u;
1509 
1510   /* In the following example:
1511 
1512      for (i = 0; i < N; i++)
1513        for (j = 0; j < N; j++)
1514          use (a[j][i]);
1515      the same cache line is accessed each N steps (except if the change from
1516      i to i + 1 crosses the boundary of the cache line).  Thus, for self-reuse,
1517      we cannot rely purely on the results of the data dependence analysis.
1518 
1519      Instead, we compute the stride of the reference in each loop, and consider
1520      the innermost loop in that the stride is less than cache size.  */
1521 
1522   strides = XCNEWVEC (HOST_WIDE_INT, n);
1523   access_fns = DR_ACCESS_FNS (dr);
1524 
1525   FOR_EACH_VEC_ELT (access_fns, i, access_fn)
1526     {
1527       /* Keep track of the reference corresponding to the subscript, so that we
1528 	 know its stride.  */
1529       while (handled_component_p (ref) && TREE_CODE (ref) != ARRAY_REF)
1530 	ref = TREE_OPERAND (ref, 0);
1531 
1532       if (TREE_CODE (ref) == ARRAY_REF)
1533 	{
1534 	  stride = TYPE_SIZE_UNIT (TREE_TYPE (ref));
1535 	  if (tree_fits_uhwi_p (stride))
1536 	    astride = tree_to_uhwi (stride);
1537 	  else
1538 	    astride = L1_CACHE_LINE_SIZE;
1539 
1540 	  ref = TREE_OPERAND (ref, 0);
1541 	}
1542       else
1543 	astride = 1;
1544 
1545       add_subscript_strides (access_fn, astride, strides, n, loop);
1546     }
1547 
1548   for (i = n; i-- > 0; )
1549     {
1550       unsigned HOST_WIDE_INT s;
1551 
1552       s = strides[i] < 0 ?  -strides[i] : strides[i];
1553 
1554       if (s < (unsigned) L1_CACHE_LINE_SIZE
1555 	  && (loop_sizes[i]
1556 	      > (unsigned) (L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION)))
1557 	{
1558 	  ret = loop_sizes[i];
1559 	  break;
1560 	}
1561     }
1562 
1563   free (strides);
1564   return ret;
1565 }
1566 
1567 /* Determines the distance till the first reuse of each reference in REFS
1568    in the loop nest of LOOP.  NO_OTHER_REFS is true if there are no other
1569    memory references in the loop.  Return false if the analysis fails.  */
1570 
1571 static bool
determine_loop_nest_reuse(struct loop * loop,struct mem_ref_group * refs,bool no_other_refs)1572 determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs,
1573 			   bool no_other_refs)
1574 {
1575   struct loop *nest, *aloop;
1576   vec<data_reference_p> datarefs = vNULL;
1577   vec<ddr_p> dependences = vNULL;
1578   struct mem_ref_group *gr;
1579   struct mem_ref *ref, *refb;
1580   auto_vec<loop_p> vloops;
1581   unsigned *loop_data_size;
1582   unsigned i, j, n;
1583   unsigned volume, dist, adist;
1584   HOST_WIDE_INT vol;
1585   data_reference_p dr;
1586   ddr_p dep;
1587 
1588   if (loop->inner)
1589     return true;
1590 
1591   /* Find the outermost loop of the loop nest of loop (we require that
1592      there are no sibling loops inside the nest).  */
1593   nest = loop;
1594   while (1)
1595     {
1596       aloop = loop_outer (nest);
1597 
1598       if (aloop == current_loops->tree_root
1599 	  || aloop->inner->next)
1600 	break;
1601 
1602       nest = aloop;
1603     }
1604 
1605   /* For each loop, determine the amount of data accessed in each iteration.
1606      We use this to estimate whether the reference is evicted from the
1607      cache before its reuse.  */
1608   find_loop_nest (nest, &vloops);
1609   n = vloops.length ();
1610   loop_data_size = XNEWVEC (unsigned, n);
1611   volume = volume_of_references (refs);
1612   i = n;
1613   while (i-- != 0)
1614     {
1615       loop_data_size[i] = volume;
1616       /* Bound the volume by the L2 cache size, since above this bound,
1617 	 all dependence distances are equivalent.  */
1618       if (volume > L2_CACHE_SIZE_BYTES)
1619 	continue;
1620 
1621       aloop = vloops[i];
1622       vol = estimated_stmt_executions_int (aloop);
1623       if (vol == -1)
1624 	vol = expected_loop_iterations (aloop);
1625       volume *= vol;
1626     }
1627 
1628   /* Prepare the references in the form suitable for data dependence
1629      analysis.  We ignore unanalyzable data references (the results
1630      are used just as a heuristics to estimate temporality of the
1631      references, hence we do not need to worry about correctness).  */
1632   for (gr = refs; gr; gr = gr->next)
1633     for (ref = gr->refs; ref; ref = ref->next)
1634       {
1635 	dr = create_data_ref (loop_preheader_edge (nest),
1636 			      loop_containing_stmt (ref->stmt),
1637 			      ref->mem, ref->stmt, !ref->write_p, false);
1638 
1639 	if (dr)
1640 	  {
1641 	    ref->reuse_distance = volume;
1642 	    dr->aux = ref;
1643 	    datarefs.safe_push (dr);
1644 	  }
1645 	else
1646 	  no_other_refs = false;
1647       }
1648 
1649   FOR_EACH_VEC_ELT (datarefs, i, dr)
1650     {
1651       dist = self_reuse_distance (dr, loop_data_size, n, loop);
1652       ref = (struct mem_ref *) dr->aux;
1653       if (ref->reuse_distance > dist)
1654 	ref->reuse_distance = dist;
1655 
1656       if (no_other_refs)
1657 	ref->independent_p = true;
1658     }
1659 
1660   if (!compute_all_dependences (datarefs, &dependences, vloops, true))
1661     return false;
1662 
1663   FOR_EACH_VEC_ELT (dependences, i, dep)
1664     {
1665       if (DDR_ARE_DEPENDENT (dep) == chrec_known)
1666 	continue;
1667 
1668       ref = (struct mem_ref *) DDR_A (dep)->aux;
1669       refb = (struct mem_ref *) DDR_B (dep)->aux;
1670 
1671       if (DDR_ARE_DEPENDENT (dep) == chrec_dont_know
1672 	  || DDR_COULD_BE_INDEPENDENT_P (dep)
1673 	  || DDR_NUM_DIST_VECTS (dep) == 0)
1674 	{
1675 	  /* If the dependence cannot be analyzed, assume that there might be
1676 	     a reuse.  */
1677 	  dist = 0;
1678 
1679 	  ref->independent_p = false;
1680 	  refb->independent_p = false;
1681 	}
1682       else
1683 	{
1684 	  /* The distance vectors are normalized to be always lexicographically
1685 	     positive, hence we cannot tell just from them whether DDR_A comes
1686 	     before DDR_B or vice versa.  However, it is not important,
1687 	     anyway -- if DDR_A is close to DDR_B, then it is either reused in
1688 	     DDR_B (and it is not nontemporal), or it reuses the value of DDR_B
1689 	     in cache (and marking it as nontemporal would not affect
1690 	     anything).  */
1691 
1692 	  dist = volume;
1693 	  for (j = 0; j < DDR_NUM_DIST_VECTS (dep); j++)
1694 	    {
1695 	      adist = volume_of_dist_vector (DDR_DIST_VECT (dep, j),
1696 					     loop_data_size, n);
1697 
1698 	      /* If this is a dependence in the innermost loop (i.e., the
1699 		 distances in all superloops are zero) and it is not
1700 		 the trivial self-dependence with distance zero, record that
1701 		 the references are not completely independent.  */
1702 	      if (lambda_vector_zerop (DDR_DIST_VECT (dep, j), n - 1)
1703 		  && (ref != refb
1704 		      || DDR_DIST_VECT (dep, j)[n-1] != 0))
1705 		{
1706 		  ref->independent_p = false;
1707 		  refb->independent_p = false;
1708 		}
1709 
1710 	      /* Ignore accesses closer than
1711 		 L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION,
1712 	      	 so that we use nontemporal prefetches e.g. if single memory
1713 		 location is accessed several times in a single iteration of
1714 		 the loop.  */
1715 	      if (adist < L1_CACHE_SIZE_BYTES / NONTEMPORAL_FRACTION)
1716 		continue;
1717 
1718 	      if (adist < dist)
1719 		dist = adist;
1720 	    }
1721 	}
1722 
1723       if (ref->reuse_distance > dist)
1724 	ref->reuse_distance = dist;
1725       if (refb->reuse_distance > dist)
1726 	refb->reuse_distance = dist;
1727     }
1728 
1729   free_dependence_relations (dependences);
1730   free_data_refs (datarefs);
1731   free (loop_data_size);
1732 
1733   if (dump_file && (dump_flags & TDF_DETAILS))
1734     {
1735       fprintf (dump_file, "Reuse distances:\n");
1736       for (gr = refs; gr; gr = gr->next)
1737 	for (ref = gr->refs; ref; ref = ref->next)
1738 	  fprintf (dump_file, " reference %u:%u distance %u\n",
1739 		   ref->group->uid, ref->uid, ref->reuse_distance);
1740     }
1741 
1742   return true;
1743 }
1744 
1745 /* Determine whether or not the trip count to ahead ratio is too small based
1746    on prefitablility consideration.
1747    AHEAD: the iteration ahead distance,
1748    EST_NITER: the estimated trip count.  */
1749 
1750 static bool
trip_count_to_ahead_ratio_too_small_p(unsigned ahead,HOST_WIDE_INT est_niter)1751 trip_count_to_ahead_ratio_too_small_p (unsigned ahead, HOST_WIDE_INT est_niter)
1752 {
1753   /* Assume trip count to ahead ratio is big enough if the trip count could not
1754      be estimated at compile time.  */
1755   if (est_niter < 0)
1756     return false;
1757 
1758   if (est_niter < (HOST_WIDE_INT) (TRIP_COUNT_TO_AHEAD_RATIO * ahead))
1759     {
1760       if (dump_file && (dump_flags & TDF_DETAILS))
1761 	fprintf (dump_file,
1762 		 "Not prefetching -- loop estimated to roll only %d times\n",
1763 		 (int) est_niter);
1764       return true;
1765     }
1766 
1767   return false;
1768 }
1769 
1770 /* Determine whether or not the number of memory references in the loop is
1771    reasonable based on the profitablity and compilation time considerations.
1772    NINSNS: estimated number of instructions in the loop,
1773    MEM_REF_COUNT: total number of memory references in the loop.  */
1774 
1775 static bool
mem_ref_count_reasonable_p(unsigned ninsns,unsigned mem_ref_count)1776 mem_ref_count_reasonable_p (unsigned ninsns, unsigned mem_ref_count)
1777 {
1778   int insn_to_mem_ratio;
1779 
1780   if (mem_ref_count == 0)
1781     return false;
1782 
1783   /* Miss rate computation (is_miss_rate_acceptable) and dependence analysis
1784      (compute_all_dependences) have high costs based on quadratic complexity.
1785      To avoid huge compilation time, we give up prefetching if mem_ref_count
1786      is too large.  */
1787   if (mem_ref_count > PREFETCH_MAX_MEM_REFS_PER_LOOP)
1788     return false;
1789 
1790   /* Prefetching improves performance by overlapping cache missing
1791      memory accesses with CPU operations.  If the loop does not have
1792      enough CPU operations to overlap with memory operations, prefetching
1793      won't give a significant benefit.  One approximate way of checking
1794      this is to require the ratio of instructions to memory references to
1795      be above a certain limit.  This approximation works well in practice.
1796      TODO: Implement a more precise computation by estimating the time
1797      for each CPU or memory op in the loop. Time estimates for memory ops
1798      should account for cache misses.  */
1799   insn_to_mem_ratio = ninsns / mem_ref_count;
1800 
1801   if (insn_to_mem_ratio < PREFETCH_MIN_INSN_TO_MEM_RATIO)
1802     {
1803       if (dump_file && (dump_flags & TDF_DETAILS))
1804         fprintf (dump_file,
1805 		 "Not prefetching -- instruction to memory reference ratio (%d) too small\n",
1806 		 insn_to_mem_ratio);
1807       return false;
1808     }
1809 
1810   return true;
1811 }
1812 
1813 /* Determine whether or not the instruction to prefetch ratio in the loop is
1814    too small based on the profitablity consideration.
1815    NINSNS: estimated number of instructions in the loop,
1816    PREFETCH_COUNT: an estimate of the number of prefetches,
1817    UNROLL_FACTOR:  the factor to unroll the loop if prefetching.  */
1818 
1819 static bool
insn_to_prefetch_ratio_too_small_p(unsigned ninsns,unsigned prefetch_count,unsigned unroll_factor)1820 insn_to_prefetch_ratio_too_small_p (unsigned ninsns, unsigned prefetch_count,
1821                                      unsigned unroll_factor)
1822 {
1823   int insn_to_prefetch_ratio;
1824 
1825   /* Prefetching most likely causes performance degradation when the instruction
1826      to prefetch ratio is too small.  Too many prefetch instructions in a loop
1827      may reduce the I-cache performance.
1828      (unroll_factor * ninsns) is used to estimate the number of instructions in
1829      the unrolled loop.  This implementation is a bit simplistic -- the number
1830      of issued prefetch instructions is also affected by unrolling.  So,
1831      prefetch_mod and the unroll factor should be taken into account when
1832      determining prefetch_count.  Also, the number of insns of the unrolled
1833      loop will usually be significantly smaller than the number of insns of the
1834      original loop * unroll_factor (at least the induction variable increases
1835      and the exit branches will get eliminated), so it might be better to use
1836      tree_estimate_loop_size + estimated_unrolled_size.  */
1837   insn_to_prefetch_ratio = (unroll_factor * ninsns) / prefetch_count;
1838   if (insn_to_prefetch_ratio < MIN_INSN_TO_PREFETCH_RATIO)
1839     {
1840       if (dump_file && (dump_flags & TDF_DETAILS))
1841         fprintf (dump_file,
1842 		 "Not prefetching -- instruction to prefetch ratio (%d) too small\n",
1843 		 insn_to_prefetch_ratio);
1844       return true;
1845     }
1846 
1847   return false;
1848 }
1849 
1850 
1851 /* Issue prefetch instructions for array references in LOOP.  Returns
1852    true if the LOOP was unrolled.  */
1853 
1854 static bool
loop_prefetch_arrays(struct loop * loop)1855 loop_prefetch_arrays (struct loop *loop)
1856 {
1857   struct mem_ref_group *refs;
1858   unsigned ahead, ninsns, time, unroll_factor;
1859   HOST_WIDE_INT est_niter;
1860   struct tree_niter_desc desc;
1861   bool unrolled = false, no_other_refs;
1862   unsigned prefetch_count;
1863   unsigned mem_ref_count;
1864 
1865   if (optimize_loop_nest_for_size_p (loop))
1866     {
1867       if (dump_file && (dump_flags & TDF_DETAILS))
1868 	fprintf (dump_file, "  ignored (cold area)\n");
1869       return false;
1870     }
1871 
1872   /* FIXME: the time should be weighted by the probabilities of the blocks in
1873      the loop body.  */
1874   time = tree_num_loop_insns (loop, &eni_time_weights);
1875   if (time == 0)
1876     return false;
1877 
1878   ahead = (PREFETCH_LATENCY + time - 1) / time;
1879   est_niter = estimated_stmt_executions_int (loop);
1880   if (est_niter == -1)
1881     est_niter = likely_max_stmt_executions_int (loop);
1882 
1883   /* Prefetching is not likely to be profitable if the trip count to ahead
1884      ratio is too small.  */
1885   if (trip_count_to_ahead_ratio_too_small_p (ahead, est_niter))
1886     return false;
1887 
1888   ninsns = tree_num_loop_insns (loop, &eni_size_weights);
1889 
1890   /* Step 1: gather the memory references.  */
1891   refs = gather_memory_references (loop, &no_other_refs, &mem_ref_count);
1892 
1893   /* Give up prefetching if the number of memory references in the
1894      loop is not reasonable based on profitablity and compilation time
1895      considerations.  */
1896   if (!mem_ref_count_reasonable_p (ninsns, mem_ref_count))
1897     goto fail;
1898 
1899   /* Step 2: estimate the reuse effects.  */
1900   prune_by_reuse (refs);
1901 
1902   if (nothing_to_prefetch_p (refs))
1903     goto fail;
1904 
1905   if (!determine_loop_nest_reuse (loop, refs, no_other_refs))
1906     goto fail;
1907 
1908   /* Step 3: determine unroll factor.  */
1909   unroll_factor = determine_unroll_factor (loop, refs, ninsns, &desc,
1910 					   est_niter);
1911 
1912   /* Estimate prefetch count for the unrolled loop.  */
1913   prefetch_count = estimate_prefetch_count (refs, unroll_factor);
1914   if (prefetch_count == 0)
1915     goto fail;
1916 
1917   if (dump_file && (dump_flags & TDF_DETAILS))
1918     fprintf (dump_file, "Ahead %d, unroll factor %d, trip count "
1919 	     HOST_WIDE_INT_PRINT_DEC "\n"
1920 	     "insn count %d, mem ref count %d, prefetch count %d\n",
1921 	     ahead, unroll_factor, est_niter,
1922 	     ninsns, mem_ref_count, prefetch_count);
1923 
1924   /* Prefetching is not likely to be profitable if the instruction to prefetch
1925      ratio is too small.  */
1926   if (insn_to_prefetch_ratio_too_small_p (ninsns, prefetch_count,
1927 					  unroll_factor))
1928     goto fail;
1929 
1930   mark_nontemporal_stores (loop, refs);
1931 
1932   /* Step 4: what to prefetch?  */
1933   if (!schedule_prefetches (refs, unroll_factor, ahead))
1934     goto fail;
1935 
1936   /* Step 5: unroll the loop.  TODO -- peeling of first and last few
1937      iterations so that we do not issue superfluous prefetches.  */
1938   if (unroll_factor != 1)
1939     {
1940       tree_unroll_loop (loop, unroll_factor,
1941 			single_dom_exit (loop), &desc);
1942       unrolled = true;
1943     }
1944 
1945   /* Step 6: issue the prefetches.  */
1946   issue_prefetches (refs, unroll_factor, ahead);
1947 
1948 fail:
1949   release_mem_refs (refs);
1950   return unrolled;
1951 }
1952 
1953 /* Issue prefetch instructions for array references in loops.  */
1954 
1955 unsigned int
tree_ssa_prefetch_arrays(void)1956 tree_ssa_prefetch_arrays (void)
1957 {
1958   struct loop *loop;
1959   bool unrolled = false;
1960   int todo_flags = 0;
1961 
1962   if (!targetm.have_prefetch ()
1963       /* It is possible to ask compiler for say -mtune=i486 -march=pentium4.
1964 	 -mtune=i486 causes us having PREFETCH_BLOCK 0, since this is part
1965 	 of processor costs and i486 does not have prefetch, but
1966 	 -march=pentium4 causes targetm.have_prefetch to be true.  Ugh.  */
1967       || PREFETCH_BLOCK == 0)
1968     return 0;
1969 
1970   if (dump_file && (dump_flags & TDF_DETAILS))
1971     {
1972       fprintf (dump_file, "Prefetching parameters:\n");
1973       fprintf (dump_file, "    simultaneous prefetches: %d\n",
1974 	       SIMULTANEOUS_PREFETCHES);
1975       fprintf (dump_file, "    prefetch latency: %d\n", PREFETCH_LATENCY);
1976       fprintf (dump_file, "    prefetch block size: %d\n", PREFETCH_BLOCK);
1977       fprintf (dump_file, "    L1 cache size: %d lines, %d kB\n",
1978 	       L1_CACHE_SIZE_BYTES / L1_CACHE_LINE_SIZE, L1_CACHE_SIZE);
1979       fprintf (dump_file, "    L1 cache line size: %d\n", L1_CACHE_LINE_SIZE);
1980       fprintf (dump_file, "    L2 cache size: %d kB\n", L2_CACHE_SIZE);
1981       fprintf (dump_file, "    min insn-to-prefetch ratio: %d \n",
1982 	       MIN_INSN_TO_PREFETCH_RATIO);
1983       fprintf (dump_file, "    min insn-to-mem ratio: %d \n",
1984 	       PREFETCH_MIN_INSN_TO_MEM_RATIO);
1985       fprintf (dump_file, "\n");
1986     }
1987 
1988   initialize_original_copy_tables ();
1989 
1990   if (!builtin_decl_explicit_p (BUILT_IN_PREFETCH))
1991     {
1992       tree type = build_function_type_list (void_type_node,
1993 					    const_ptr_type_node, NULL_TREE);
1994       tree decl = add_builtin_function ("__builtin_prefetch", type,
1995 					BUILT_IN_PREFETCH, BUILT_IN_NORMAL,
1996 					NULL, NULL_TREE);
1997       DECL_IS_NOVOPS (decl) = true;
1998       set_builtin_decl (BUILT_IN_PREFETCH, decl, false);
1999     }
2000 
2001   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
2002     {
2003       if (dump_file && (dump_flags & TDF_DETAILS))
2004 	fprintf (dump_file, "Processing loop %d:\n", loop->num);
2005 
2006       unrolled |= loop_prefetch_arrays (loop);
2007 
2008       if (dump_file && (dump_flags & TDF_DETAILS))
2009 	fprintf (dump_file, "\n\n");
2010     }
2011 
2012   if (unrolled)
2013     {
2014       scev_reset ();
2015       todo_flags |= TODO_cleanup_cfg;
2016     }
2017 
2018   free_original_copy_tables ();
2019   return todo_flags;
2020 }
2021 
2022 /* Prefetching.  */
2023 
2024 namespace {
2025 
2026 const pass_data pass_data_loop_prefetch =
2027 {
2028   GIMPLE_PASS, /* type */
2029   "aprefetch", /* name */
2030   OPTGROUP_LOOP, /* optinfo_flags */
2031   TV_TREE_PREFETCH, /* tv_id */
2032   ( PROP_cfg | PROP_ssa ), /* properties_required */
2033   0, /* properties_provided */
2034   0, /* properties_destroyed */
2035   0, /* todo_flags_start */
2036   0, /* todo_flags_finish */
2037 };
2038 
2039 class pass_loop_prefetch : public gimple_opt_pass
2040 {
2041 public:
pass_loop_prefetch(gcc::context * ctxt)2042   pass_loop_prefetch (gcc::context *ctxt)
2043     : gimple_opt_pass (pass_data_loop_prefetch, ctxt)
2044   {}
2045 
2046   /* opt_pass methods: */
gate(function *)2047   virtual bool gate (function *) { return flag_prefetch_loop_arrays > 0; }
2048   virtual unsigned int execute (function *);
2049 
2050 }; // class pass_loop_prefetch
2051 
2052 unsigned int
execute(function * fun)2053 pass_loop_prefetch::execute (function *fun)
2054 {
2055   if (number_of_loops (fun) <= 1)
2056     return 0;
2057 
2058   if ((PREFETCH_BLOCK & (PREFETCH_BLOCK - 1)) != 0)
2059     {
2060       static bool warned = false;
2061 
2062       if (!warned)
2063 	{
2064 	  warning (OPT_Wdisabled_optimization,
2065 		   "%<l1-cache-size%> parameter is not a power of two %d",
2066 		   PREFETCH_BLOCK);
2067 	  warned = true;
2068 	}
2069       return 0;
2070     }
2071 
2072   return tree_ssa_prefetch_arrays ();
2073 }
2074 
2075 } // anon namespace
2076 
2077 gimple_opt_pass *
make_pass_loop_prefetch(gcc::context * ctxt)2078 make_pass_loop_prefetch (gcc::context *ctxt)
2079 {
2080   return new pass_loop_prefetch (ctxt);
2081 }
2082 
2083 
2084