OSDN Git Service

* builtins.c, c-pragma.h, c-typeck.c, cgraph.c, cgraphunit.c,
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-loop-prefetch.c
1 /* Array prefetching.
2    Copyright (C) 2005 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 2, 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 COPYING.  If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
19 02111-1307, USA.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
30 #include "output.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
34 #include "timevar.h"
35 #include "cfgloop.h"
36 #include "varray.h"
37 #include "expr.h"
38 #include "tree-pass.h"
39 #include "ggc.h"
40 #include "insn-config.h"
41 #include "recog.h"
42 #include "hashtab.h"
43 #include "tree-chrec.h"
44 #include "tree-scalar-evolution.h"
45 #include "toplev.h"
46 #include "params.h"
47 #include "langhooks.h"
48
49 /* This pass inserts prefetch instructions to optimize cache usage during
50    accesses to arrays in loops.  It processes loops sequentially and:
51
52    1) Gathers all memory references in the single loop.
53    2) For each of the references it decides when it is profitable to prefetch
54       it.  To do it, we evaluate the reuse among the accesses, and determines
55       two values: PREFETCH_BEFORE (meaning that it only makes sense to do
56       prefetching in the first PREFETCH_BEFORE iterations of the loop) and
57       PREFETCH_MOD (meaning that it only makes sense to prefetch in the
58       iterations of the loop that are zero modulo PREFETCH_MOD).  For example
59       (assuming cache line size is 64 bytes, char has size 1 byte and there
60       is no hardware sequential prefetch):
61
62       char *a;
63       for (i = 0; i < max; i++)
64         {
65           a[255] = ...;         (0)
66           a[i] = ...;           (1)
67           a[i + 64] = ...;      (2)
68           a[16*i] = ...;        (3)
69           a[187*i] = ...;       (4)
70           a[187*i + 50] = ...;  (5)
71         }
72
73        (0) obviously has PREFETCH_BEFORE 1
74        (1) has PREFETCH_BEFORE 64, since (2) accesses the same memory
75            location 64 iterations before it, and PREFETCH_MOD 64 (since
76            it hits the same cache line otherwise).
77        (2) has PREFETCH_MOD 64
78        (3) has PREFETCH_MOD 4
79        (4) has PREFETCH_MOD 1.  We do not set PREFETCH_BEFORE here, since
80            the cache line accessed by (4) is the same with probability only
81            7/32.
82        (5) has PREFETCH_MOD 1 as well.
83
84    3) We determine how much ahead we need to prefetch.  The number of
85       iterations needed is time to fetch / time spent in one iteration of
86       the loop.  The problem is that we do not know either of these values,
87       so we just make a heuristic guess based on a magic (possibly)
88       target-specific constant and size of the loop.
89
90    4) Determine which of the references we prefetch.  We take into account
91       that there is a maximum number of simultaneous prefetches (provided
92       by machine description).  We prefetch as many prefetches as possible
93       while still within this bound (starting with those with lowest
94       prefetch_mod, since they are responsible for most of the cache
95       misses).
96       
97    5) We unroll and peel loops so that we are able to satisfy PREFETCH_MOD
98       and PREFETCH_BEFORE requirements (within some bounds), and to avoid
99       prefetching nonaccessed memory.
100       TODO -- actually implement peeling.
101       
102    6) We actually emit the prefetch instructions.  ??? Perhaps emit the
103       prefetch instructions with guards in cases where 5) was not sufficient
104       to satisfy the constraints?
105
106    Some other TODO:
107       -- write and use more general reuse analysis (that could be also used
108          in other cache aimed loop optimizations)
109       -- make it behave sanely together with the prefetches given by user
110          (now we just ignore them; at the very least we should avoid
111          optimizing loops in that user put his own prefetches)
112       -- we assume cache line size alignment of arrays; this could be
113          improved.  */
114
115 /* Magic constants follow.  These should be replaced by machine specific
116    numbers.  */
117
118 /* A number that should roughly correspond to the number of instructions
119    executed before the prefetch is completed.  */
120
121 #ifndef PREFETCH_LATENCY
122 #define PREFETCH_LATENCY 200
123 #endif
124
125 /* Number of prefetches that can run at the same time.  */
126
127 #ifndef SIMULTANEOUS_PREFETCHES
128 #define SIMULTANEOUS_PREFETCHES 3
129 #endif
130
131 /* True if write can be prefetched by a read prefetch.  */
132
133 #ifndef WRITE_CAN_USE_READ_PREFETCH
134 #define WRITE_CAN_USE_READ_PREFETCH 1
135 #endif
136
137 /* True if read can be prefetched by a write prefetch. */
138
139 #ifndef READ_CAN_USE_WRITE_PREFETCH
140 #define READ_CAN_USE_WRITE_PREFETCH 0
141 #endif
142
143 /* Cache line size.  Assumed to be a power of two.  */
144
145 #ifndef PREFETCH_BLOCK
146 #define PREFETCH_BLOCK 32
147 #endif
148
149 /* Do we have a forward hardware sequential prefetching?  */
150
151 #ifndef HAVE_FORWARD_PREFETCH
152 #define HAVE_FORWARD_PREFETCH 0
153 #endif
154
155 /* Do we have a backward hardware sequential prefetching?  */
156
157 #ifndef HAVE_BACKWARD_PREFETCH
158 #define HAVE_BACKWARD_PREFETCH 0
159 #endif
160
161 /* In some cases we are only able to determine that there is a certain
162    probability that the two accesses hit the same cache line.  In this
163    case, we issue the prefetches for both of them if this probability
164    is less then (1000 - ACCEPTABLE_MISS_RATE) promile.  */
165
166 #ifndef ACCEPTABLE_MISS_RATE
167 #define ACCEPTABLE_MISS_RATE 50
168 #endif
169
170 #ifndef HAVE_prefetch
171 #define HAVE_prefetch 0
172 #endif
173
174 /* The group of references between that reuse may occur.  */
175
176 struct mem_ref_group
177 {
178   tree base;                    /* Base of the reference.  */
179   HOST_WIDE_INT step;           /* Step of the reference.  */
180   struct mem_ref *refs;         /* References in the group.  */
181   struct mem_ref_group *next;   /* Next group of references.  */
182 };
183
184 /* Assigned to PREFETCH_BEFORE when all iterations are to be prefetched.  */
185
186 #define PREFETCH_ALL            (~(unsigned HOST_WIDE_INT) 0)
187
188 /* The memory reference.  */
189
190 struct mem_ref
191 {
192   tree stmt;                    /* Statement in that the reference appears.  */
193   tree mem;                     /* The reference.  */
194   HOST_WIDE_INT delta;          /* Constant offset of the reference.  */
195   bool write_p;                 /* Is it a write?  */
196   struct mem_ref_group *group;  /* The group of references it belongs to.  */
197   unsigned HOST_WIDE_INT prefetch_mod;
198                                 /* Prefetch only each PREFETCH_MOD-th
199                                    iteration.  */
200   unsigned HOST_WIDE_INT prefetch_before;
201                                 /* Prefetch only first PREFETCH_BEFORE
202                                    iterations.  */
203   bool issue_prefetch_p;        /* Should we really issue the prefetch?  */
204   struct mem_ref *next;         /* The next reference in the group.  */
205 };
206
207 /* Dumps information obout reference REF to FILE.  */
208
209 static void
210 dump_mem_ref (FILE *file, struct mem_ref *ref)
211 {
212   fprintf (file, "Reference %p:\n", (void *) ref);
213
214   fprintf (file, "  group %p (base ", (void *) ref->group);
215   print_generic_expr (file, ref->group->base, TDF_SLIM);
216   fprintf (file, ", step ");
217   fprintf (file, HOST_WIDE_INT_PRINT_DEC, ref->group->step);
218   fprintf (file, ")\n");
219
220   fprintf (dump_file, "  delta ");
221   fprintf (file, HOST_WIDE_INT_PRINT_DEC, ref->delta);
222   fprintf (file, "\n");
223
224   fprintf (file, "  %s\n", ref->write_p ? "write" : "read");
225
226   fprintf (file, "\n");
227 }
228
229 /* Finds a group with BASE and STEP in GROUPS, or creates one if it does not
230    exist.  */
231
232 static struct mem_ref_group *
233 find_or_create_group (struct mem_ref_group **groups, tree base,
234                       HOST_WIDE_INT step)
235 {
236   struct mem_ref_group *group;
237
238   for (; *groups; groups = &(*groups)->next)
239     {
240       if ((*groups)->step == step
241           && operand_equal_p ((*groups)->base, base, 0))
242         return *groups;
243
244       /* Keep the list of groups sorted by decreasing step.  */
245       if ((*groups)->step < step)
246         break;
247     }
248
249   group = xcalloc (1, sizeof (struct mem_ref_group));
250   group->base = base;
251   group->step = step;
252   group->refs = NULL;
253   group->next = *groups;
254   *groups = group;
255
256   return group;
257 }
258
259 /* Records a memory reference MEM in GROUP with offset DELTA and write status
260    WRITE_P.  The reference occurs in statement STMT.  */
261
262 static void
263 record_ref (struct mem_ref_group *group, tree stmt, tree mem,
264             HOST_WIDE_INT delta, bool write_p)
265 {
266   struct mem_ref **aref;
267
268   /* Do not record the same address twice.  */
269   for (aref = &group->refs; *aref; aref = &(*aref)->next)
270     {
271       /* It does not have to be possible for write reference to reuse the read
272          prefetch, or vice versa.  */
273       if (!WRITE_CAN_USE_READ_PREFETCH
274           && write_p
275           && !(*aref)->write_p)
276         continue;
277       if (!READ_CAN_USE_WRITE_PREFETCH
278           && !write_p
279           && (*aref)->write_p)
280         continue;
281
282       if ((*aref)->delta == delta)
283         return;
284     }
285
286   (*aref) = xcalloc (1, sizeof (struct mem_ref));
287   (*aref)->stmt = stmt;
288   (*aref)->mem = mem;
289   (*aref)->delta = delta;
290   (*aref)->write_p = write_p;
291   (*aref)->prefetch_before = PREFETCH_ALL;
292   (*aref)->prefetch_mod = 1;
293   (*aref)->issue_prefetch_p = false;
294   (*aref)->group = group;
295   (*aref)->next = NULL;
296
297   if (dump_file && (dump_flags & TDF_DETAILS))
298     dump_mem_ref (dump_file, *aref);
299 }
300
301 /* Release memory references in GROUPS.  */
302
303 static void
304 release_mem_refs (struct mem_ref_group *groups)
305 {
306   struct mem_ref_group *next_g;
307   struct mem_ref *ref, *next_r;
308
309   for (; groups; groups = next_g)
310     {
311       next_g = groups->next;
312       for (ref = groups->refs; ref; ref = next_r)
313         {
314           next_r = ref->next;
315           free (ref);
316         }
317       free (groups);
318     }
319 }
320
321 /* A structure used to pass arguments to idx_analyze_ref.  */
322
323 struct ar_data
324 {
325   struct loop *loop;                    /* Loop of the reference.  */
326   tree stmt;                            /* Statement of the reference.  */
327   HOST_WIDE_INT *step;                  /* Step of the memory reference.  */
328   HOST_WIDE_INT *delta;                 /* Offset of the memory reference.  */
329 };
330
331 /* Analyzes a single INDEX of a memory reference to obtain information
332    described at analyze_ref.  Callback for for_each_index.  */
333
334 static bool
335 idx_analyze_ref (tree base, tree *index, void *data)
336 {
337   struct ar_data *ar_data = data;
338   tree ibase, step, stepsize;
339   HOST_WIDE_INT istep, idelta = 0, imult = 1;
340   affine_iv iv;
341
342   if (TREE_CODE (base) == MISALIGNED_INDIRECT_REF
343       || TREE_CODE (base) == ALIGN_INDIRECT_REF)
344     return false;
345
346   if (!simple_iv (ar_data->loop, ar_data->stmt, *index, &iv, false))
347     return false;
348   ibase = iv.base;
349   step = iv.step;
350
351   if (zero_p (step))
352     istep = 0;
353   else
354     {
355       if (!cst_and_fits_in_hwi (step))
356         return false;
357       istep = int_cst_value (step);
358     }
359
360   if (TREE_CODE (ibase) == PLUS_EXPR
361       && cst_and_fits_in_hwi (TREE_OPERAND (ibase, 1)))
362     {
363       idelta = int_cst_value (TREE_OPERAND (ibase, 1));
364       ibase = TREE_OPERAND (ibase, 0);
365     }
366   if (cst_and_fits_in_hwi (ibase))
367     {
368       idelta += int_cst_value (ibase);
369       ibase = build_int_cst_type (TREE_TYPE (ibase), 0);
370     }
371
372   if (TREE_CODE (base) == ARRAY_REF)
373     {
374       stepsize = array_ref_element_size (base);
375       if (!cst_and_fits_in_hwi (stepsize))
376         return false;
377       imult = int_cst_value (stepsize);
378
379       istep *= imult;
380       idelta *= imult;
381     }
382
383   *ar_data->step += istep;
384   *ar_data->delta += idelta;
385   *index = ibase;
386
387   return true;
388 }
389
390 /* Tries to express REF in shape &BASE + STEP * iter + DELTA, where DELTA and
391    STEP are integer constants and iter is number of iterations of LOOP.  The
392    reference occurs in statement STMT.  */
393
394 static bool
395 analyze_ref (struct loop *loop, tree ref, tree *base,
396              HOST_WIDE_INT *step, HOST_WIDE_INT *delta,
397              tree stmt)
398 {
399   struct ar_data ar_data;
400   tree off;
401   HOST_WIDE_INT bit_offset;
402
403   *step = 0;
404   *delta = 0;
405
406   /* First strip off the component references.  Ignore bitfields.  */
407   if (TREE_CODE (ref) == COMPONENT_REF
408       && DECL_NONADDRESSABLE_P (TREE_OPERAND (ref, 1)))
409     ref = TREE_OPERAND (ref, 0);
410
411   for (; TREE_CODE (ref) == COMPONENT_REF; ref = TREE_OPERAND (ref, 0))
412     {
413       off = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1));
414       bit_offset = TREE_INT_CST_LOW (off);
415       gcc_assert (bit_offset % BITS_PER_UNIT == 0);
416       
417       *delta += bit_offset / BITS_PER_UNIT;
418     }
419
420   *base = unshare_expr (ref);
421   ar_data.loop = loop;
422   ar_data.stmt = stmt;
423   ar_data.step = step;
424   ar_data.delta = delta;
425   return for_each_index (base, idx_analyze_ref, &ar_data);
426 }
427
428 /* Record a memory reference REF to the list REFS.  The reference occurs in
429    LOOP in statement STMT and it is write if WRITE_P.  */
430
431 static void
432 gather_memory_references_ref (struct loop *loop, struct mem_ref_group **refs,
433                               tree ref, bool write_p, tree stmt)
434 {
435   tree base;
436   HOST_WIDE_INT step, delta;
437   struct mem_ref_group *agrp;
438
439   if (!analyze_ref (loop, ref, &base, &step, &delta, stmt))
440     return;
441
442   /* Now we know that REF = &BASE + STEP * iter + DELTA, where DELTA and STEP
443      are integer constants.  */
444   agrp = find_or_create_group (refs, base, step);
445   record_ref (agrp, stmt, ref, delta, write_p);
446 }
447
448 /* Record the suitable memory references in LOOP.  */
449
450 static struct mem_ref_group *
451 gather_memory_references (struct loop *loop)
452 {
453   basic_block *body = get_loop_body_in_dom_order (loop);
454   basic_block bb;
455   unsigned i;
456   block_stmt_iterator bsi;
457   tree stmt, lhs, rhs;
458   struct mem_ref_group *refs = NULL;
459
460   /* Scan the loop body in order, so that the former references precede the
461      later ones.  */
462   for (i = 0; i < loop->num_nodes; i++)
463     {
464       bb = body[i];
465       if (bb->loop_father != loop)
466         continue;
467
468       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
469         {
470           stmt = bsi_stmt (bsi);
471           if (TREE_CODE (stmt) != MODIFY_EXPR)
472             continue;
473
474           lhs = TREE_OPERAND (stmt, 0);
475           rhs = TREE_OPERAND (stmt, 1);
476
477           if (REFERENCE_CLASS_P (rhs))
478             gather_memory_references_ref (loop, &refs, rhs, false, stmt);
479           if (REFERENCE_CLASS_P (lhs))
480             gather_memory_references_ref (loop, &refs, lhs, true, stmt);
481         }
482     }
483   free (body);
484
485   return refs;
486 }
487
488 /* Prune the prefetch candidate REF using the self-reuse.  */
489
490 static void
491 prune_ref_by_self_reuse (struct mem_ref *ref)
492 {
493   HOST_WIDE_INT step = ref->group->step;
494   bool backward = step < 0;
495
496   if (step == 0)
497     {
498       /* Prefetch references to invariant address just once.  */
499       ref->prefetch_before = 1;
500       return;
501     }
502
503   if (backward)
504     step = -step;
505
506   if (step > PREFETCH_BLOCK)
507     return;
508
509   if ((backward && HAVE_BACKWARD_PREFETCH)
510       || (!backward && HAVE_FORWARD_PREFETCH))
511     {
512       ref->prefetch_before = 1;
513       return;
514     }
515
516   ref->prefetch_mod = PREFETCH_BLOCK / step;
517 }
518
519 /* Divides X by BY, rounding down.  */
520
521 static HOST_WIDE_INT
522 ddown (HOST_WIDE_INT x, unsigned HOST_WIDE_INT by)
523 {
524   gcc_assert (by > 0);
525
526   if (x >= 0)
527     return x / by;
528   else
529     return (x + by - 1) / by;
530 }
531
532 /* Prune the prefetch candidate REF using the reuse with BY.
533    If BY_IS_BEFORE is true, BY is before REF in the loop.  */
534
535 static void
536 prune_ref_by_group_reuse (struct mem_ref *ref, struct mem_ref *by,
537                           bool by_is_before)
538 {
539   HOST_WIDE_INT step = ref->group->step;
540   bool backward = step < 0;
541   HOST_WIDE_INT delta_r = ref->delta, delta_b = by->delta;
542   HOST_WIDE_INT delta = delta_b - delta_r;
543   HOST_WIDE_INT hit_from;
544   unsigned HOST_WIDE_INT prefetch_before, prefetch_block;
545
546   if (delta == 0)
547     {
548       /* If the references has the same address, only prefetch the
549          former.  */
550       if (by_is_before)
551         ref->prefetch_before = 0;
552       
553       return;
554     }
555
556   if (!step)
557     {
558       /* If the reference addresses are invariant and fall into the
559          same cache line, prefetch just the first one.  */
560       if (!by_is_before)
561         return;
562
563       if (ddown (ref->delta, PREFETCH_BLOCK)
564           != ddown (by->delta, PREFETCH_BLOCK))
565         return;
566
567       ref->prefetch_before = 0;
568       return;
569     }
570
571   /* Only prune the reference that is behind in the array.  */
572   if (backward)
573     {
574       if (delta > 0)
575         return;
576
577       /* Transform the data so that we may assume that the accesses
578          are forward.  */
579       delta = - delta;
580       step = -step;
581       delta_r = PREFETCH_BLOCK - 1 - delta_r;
582       delta_b = PREFETCH_BLOCK - 1 - delta_b;
583     }
584   else
585     {
586       if (delta < 0)
587         return;
588     }
589
590   /* Check whether the two references are likely to hit the same cache
591      line, and how distant the iterations in that it occurs are from
592      each other.  */
593
594   if (step <= PREFETCH_BLOCK)
595     {
596       /* The accesses are sure to meet.  Let us check when.  */
597       hit_from = ddown (delta_b, PREFETCH_BLOCK) * PREFETCH_BLOCK;
598       prefetch_before = (hit_from - delta_r + step - 1) / step;
599
600       if (prefetch_before < ref->prefetch_before)
601         ref->prefetch_before = prefetch_before;
602
603       return;
604     }
605
606   /* A more complicated case.  First let us ensure that size of cache line
607      and step are coprime (here we assume that PREFETCH_BLOCK is a power
608      of two.  */
609   prefetch_block = PREFETCH_BLOCK;
610   while ((step & 1) == 0
611          && prefetch_block > 1)
612     {
613       step >>= 1;
614       prefetch_block >>= 1;
615       delta >>= 1;
616     }
617
618   /* Now step > prefetch_block, and step and prefetch_block are coprime.
619      Determine the probability that the accesses hit the same cache line.  */
620
621   prefetch_before = delta / step;
622   delta %= step;
623   if ((unsigned HOST_WIDE_INT) delta
624       <= (prefetch_block * ACCEPTABLE_MISS_RATE / 1000))
625     {
626       if (prefetch_before < ref->prefetch_before)
627         ref->prefetch_before = prefetch_before;
628
629       return;
630     }
631
632   /* Try also the following iteration.  */
633   prefetch_before++;
634   delta = step - delta;
635   if ((unsigned HOST_WIDE_INT) delta
636       <= (prefetch_block * ACCEPTABLE_MISS_RATE / 1000))
637     {
638       if (prefetch_before < ref->prefetch_before)
639         ref->prefetch_before = prefetch_before;
640
641       return;
642     }
643
644   /* The ref probably does not reuse by.  */
645   return;
646 }
647
648 /* Prune the prefetch candidate REF using the reuses with other references
649    in REFS.  */
650
651 static void
652 prune_ref_by_reuse (struct mem_ref *ref, struct mem_ref *refs)
653 {
654   struct mem_ref *prune_by;
655   bool before = true;
656
657   prune_ref_by_self_reuse (ref);
658
659   for (prune_by = refs; prune_by; prune_by = prune_by->next)
660     {
661       if (prune_by == ref)
662         {
663           before = false;
664           continue;
665         }
666
667       if (!WRITE_CAN_USE_READ_PREFETCH
668           && ref->write_p
669           && !prune_by->write_p)
670         continue;
671       if (!READ_CAN_USE_WRITE_PREFETCH
672           && !ref->write_p
673           && prune_by->write_p)
674         continue;
675
676       prune_ref_by_group_reuse (ref, prune_by, before);
677     }
678 }
679
680 /* Prune the prefetch candidates in GROUP using the reuse analysis.  */
681
682 static void
683 prune_group_by_reuse (struct mem_ref_group *group)
684 {
685   struct mem_ref *ref_pruned;
686
687   for (ref_pruned = group->refs; ref_pruned; ref_pruned = ref_pruned->next)
688     {
689       prune_ref_by_reuse (ref_pruned, group->refs);
690
691       if (dump_file && (dump_flags & TDF_DETAILS))
692         {
693           fprintf (dump_file, "Reference %p:", (void *) ref_pruned);
694
695           if (ref_pruned->prefetch_before == PREFETCH_ALL
696               && ref_pruned->prefetch_mod == 1)
697             fprintf (dump_file, " no restrictions");
698           else if (ref_pruned->prefetch_before == 0)
699             fprintf (dump_file, " do not prefetch");
700           else if (ref_pruned->prefetch_before <= ref_pruned->prefetch_mod)
701             fprintf (dump_file, " prefetch once");
702           else
703             {
704               if (ref_pruned->prefetch_before != PREFETCH_ALL)
705                 {
706                   fprintf (dump_file, " prefetch before ");
707                   fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC,
708                            ref_pruned->prefetch_before);
709                 }
710               if (ref_pruned->prefetch_mod != 1)
711                 {
712                   fprintf (dump_file, " prefetch mod ");
713                   fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC,
714                            ref_pruned->prefetch_mod);
715                 }
716             }
717           fprintf (dump_file, "\n");
718         }
719     }
720 }
721
722 /* Prune the list of prefetch candidates GROUPS using the reuse analysis.  */
723
724 static void
725 prune_by_reuse (struct mem_ref_group *groups)
726 {
727   for (; groups; groups = groups->next)
728     prune_group_by_reuse (groups);
729 }
730
731 /* Returns true if we should issue prefetch for REF.  */
732
733 static bool
734 should_issue_prefetch_p (struct mem_ref *ref)
735 {
736   /* For now do not issue prefetches for only first few of the
737      iterations.  */
738   if (ref->prefetch_before != PREFETCH_ALL)
739     return false;
740
741   return true;
742 }
743
744 /* Decide which of the prefetch candidates in GROUPS to prefetch.
745    AHEAD is the number of iterations to prefetch ahead (which corresponds
746    to the number of simultaneous instances of one prefetch running at a
747    time).  UNROLL_FACTOR is the factor by that the loop is going to be
748    unrolled.  Returns true if there is anything to prefetch.  */
749
750 static bool
751 schedule_prefetches (struct mem_ref_group *groups, unsigned unroll_factor,
752                      unsigned ahead)
753 {
754   unsigned max_prefetches, n_prefetches;
755   struct mem_ref *ref;
756   bool any = false;
757
758   max_prefetches = (SIMULTANEOUS_PREFETCHES * unroll_factor) / ahead;
759   if (max_prefetches > (unsigned) SIMULTANEOUS_PREFETCHES)
760     max_prefetches = SIMULTANEOUS_PREFETCHES;
761
762   if (dump_file && (dump_flags & TDF_DETAILS))
763     fprintf (dump_file, "Max prefetches to issue: %d.\n", max_prefetches);
764
765   if (!max_prefetches)
766     return false;
767
768   /* For now we just take memory references one by one and issue
769      prefetches for as many as possible.  The groups are sorted
770      starting with the largest step, since the references with
771      large step are more likely to cause many cache misses.  */
772
773   for (; groups; groups = groups->next)
774     for (ref = groups->refs; ref; ref = ref->next)
775       {
776         if (!should_issue_prefetch_p (ref))
777           continue;
778
779         ref->issue_prefetch_p = true;
780
781         /* If prefetch_mod is less then unroll_factor, we need to insert
782            several prefetches for the reference.  */
783         n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
784                         / ref->prefetch_mod);
785         if (max_prefetches <= n_prefetches)
786           return true;
787
788         max_prefetches -= n_prefetches;
789         any = true;
790       }
791
792   return any;
793 }
794
795 /* Determine whether there is any reference suitable for prefetching
796    in GROUPS.  */
797
798 static bool
799 anything_to_prefetch_p (struct mem_ref_group *groups)
800 {
801   struct mem_ref *ref;
802
803   for (; groups; groups = groups->next)
804     for (ref = groups->refs; ref; ref = ref->next)
805       if (should_issue_prefetch_p (ref))
806         return true;
807
808   return false;
809 }
810
811 /* Issue prefetches for the reference REF into loop as decided before.
812    HEAD is the number of iterations to prefetch ahead.  UNROLL_FACTOR
813    is the factor by thet LOOP was unrolled.  */
814
815 static void
816 issue_prefetch_ref (struct mem_ref *ref, unsigned unroll_factor, unsigned ahead)
817 {
818   HOST_WIDE_INT delta;
819   tree addr, addr_base, prefetch, params, write_p;
820   block_stmt_iterator bsi;
821   unsigned n_prefetches, ap;
822
823   if (dump_file && (dump_flags & TDF_DETAILS))
824     fprintf (dump_file, "Issued prefetch for %p.\n", (void *) ref);
825
826   bsi = bsi_for_stmt (ref->stmt);
827
828   n_prefetches = ((unroll_factor + ref->prefetch_mod - 1)
829                   / ref->prefetch_mod);
830   addr_base = build_fold_addr_expr_with_type (ref->mem, ptr_type_node);
831   addr_base = force_gimple_operand_bsi (&bsi, unshare_expr (addr_base), true, NULL);
832
833   for (ap = 0; ap < n_prefetches; ap++)
834     {
835       /* Determine the address to prefetch.  */
836       delta = (ahead + ap * ref->prefetch_mod) * ref->group->step;
837       addr = fold_build2 (PLUS_EXPR, ptr_type_node,
838                           addr_base, build_int_cst (ptr_type_node, delta));
839       addr = force_gimple_operand_bsi (&bsi, unshare_expr (addr), true, NULL);
840
841       /* Create the prefetch instruction.  */
842       write_p = ref->write_p ? integer_one_node : integer_zero_node;
843       params = tree_cons (NULL_TREE, addr,
844                           tree_cons (NULL_TREE, write_p, NULL_TREE));
845                                  
846       prefetch = build_function_call_expr (built_in_decls[BUILT_IN_PREFETCH],
847                                            params);
848       bsi_insert_before (&bsi, prefetch, BSI_SAME_STMT);
849     }
850 }
851
852 /* Issue prefetches for the references in GROUPS into loop as decided before.
853    HEAD is the number of iterations to prefetch ahead.  UNROLL_FACTOR is the
854    factor by that LOOP was unrolled.  */
855
856 static void
857 issue_prefetches (struct mem_ref_group *groups,
858                   unsigned unroll_factor, unsigned ahead)
859 {
860   struct mem_ref *ref;
861
862   for (; groups; groups = groups->next)
863     for (ref = groups->refs; ref; ref = ref->next)
864       if (ref->issue_prefetch_p)
865         issue_prefetch_ref (ref, unroll_factor, ahead);
866 }
867
868 /* Determines whether we can profitably unroll LOOP FACTOR times, and if
869    this is the case, fill in DESC by the description of number of
870    iterations.  */
871
872 static bool
873 should_unroll_loop_p (struct loop *loop, struct tree_niter_desc *desc,
874                       unsigned factor)
875 {
876   if (!can_unroll_loop_p (loop, factor, desc))
877     return false;
878
879   /* We only consider loops without control flow for unrolling.  This is not
880      a hard restriction -- tree_unroll_loop works with arbitrary loops
881      as well; but the unrolling/prefetching is usually more profitable for
882      loops consisting of a single basic block, and we want to limit the
883      code growth.  */
884   if (loop->num_nodes > 2)
885     return false;
886
887   return true;
888 }
889
890 /* Determine the coefficient by that unroll LOOP, from the information
891    contained in the list of memory references REFS.  Description of
892    umber of iterations of LOOP is stored to DESC.  AHEAD is the number
893    of iterations ahead that we need to prefetch.  NINSNS is number of
894    insns of the LOOP.  */
895
896 static unsigned
897 determine_unroll_factor (struct loop *loop, struct mem_ref_group *refs,
898                          unsigned ahead, unsigned ninsns,
899                          struct tree_niter_desc *desc)
900 {
901   unsigned upper_bound, size_factor, constraint_factor;
902   unsigned factor, max_mod_constraint, ahead_factor;
903   struct mem_ref_group *agp;
904   struct mem_ref *ref;
905
906   upper_bound = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
907
908   /* First check whether the loop is not too large to unroll.  */
909   size_factor = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / ninsns;
910   if (size_factor <= 1)
911     return 1;
912
913   if (size_factor < upper_bound)
914     upper_bound = size_factor;
915
916   max_mod_constraint = 1;
917   for (agp = refs; agp; agp = agp->next)
918     for (ref = agp->refs; ref; ref = ref->next)
919       if (should_issue_prefetch_p (ref)
920           && ref->prefetch_mod > max_mod_constraint)
921         max_mod_constraint = ref->prefetch_mod;
922
923   /* Set constraint_factor as large as needed to be able to satisfy the
924      largest modulo constraint.  */
925   constraint_factor = max_mod_constraint;
926
927   /* If ahead is too large in comparison with the number of available
928      prefetches, unroll the loop as much as needed to be able to prefetch
929      at least partially some of the references in the loop.  */
930   ahead_factor = ((ahead + SIMULTANEOUS_PREFETCHES - 1)
931                   / SIMULTANEOUS_PREFETCHES);
932
933   /* Unroll as much as useful, but bound the code size growth.  */
934   if (constraint_factor < ahead_factor)
935     factor = ahead_factor;
936   else
937     factor = constraint_factor;
938   if (factor > upper_bound)
939     factor = upper_bound;
940
941   if (!should_unroll_loop_p (loop, desc, factor))
942     return 1;
943
944   return factor;
945 }
946
947 /* Issue prefetch instructions for array references in LOOP.  Returns
948    true if the LOOP was unrolled.  LOOPS is the array containing all
949    loops.  */
950
951 static bool
952 loop_prefetch_arrays (struct loops *loops, struct loop *loop)
953 {
954   struct mem_ref_group *refs;
955   unsigned ahead, ninsns, unroll_factor;
956   struct tree_niter_desc desc;
957   bool unrolled = false;
958
959   /* Step 1: gather the memory references.  */
960   refs = gather_memory_references (loop);
961
962   /* Step 2: estimate the reuse effects.  */
963   prune_by_reuse (refs);
964
965   if (!anything_to_prefetch_p (refs))
966     goto fail;
967
968   /* Step 3: determine the ahead and unroll factor.  */
969
970   /* FIXME: We should use not size of the loop, but the average number of
971      instructions executed per iteration of the loop.  */
972   ninsns = tree_num_loop_insns (loop);
973   ahead = (PREFETCH_LATENCY + ninsns - 1) / ninsns;
974   unroll_factor = determine_unroll_factor (loop, refs, ahead, ninsns,
975                                            &desc);
976   if (dump_file && (dump_flags & TDF_DETAILS))
977     fprintf (dump_file, "Ahead %d, unroll factor %d\n", ahead, unroll_factor);
978
979   /* If the loop rolls less than the required unroll factor, prefetching
980      is useless.  */
981   if (unroll_factor > 1
982       && cst_and_fits_in_hwi (desc.niter)
983       && (unsigned HOST_WIDE_INT) int_cst_value (desc.niter) < unroll_factor)
984     goto fail;
985
986   /* Step 4: what to prefetch?  */
987   if (!schedule_prefetches (refs, unroll_factor, ahead))
988     goto fail;
989
990   /* Step 5: unroll the loop.  TODO -- peeling of first and last few
991      iterations so that we do not issue superfluous prefetches.  */
992   if (unroll_factor != 1)
993     {
994       tree_unroll_loop (loops, loop, unroll_factor,
995                         single_dom_exit (loop), &desc);
996       unrolled = true;
997     }
998
999   /* Step 6: issue the prefetches.  */
1000   issue_prefetches (refs, unroll_factor, ahead);
1001
1002 fail:
1003   release_mem_refs (refs);
1004   return unrolled;
1005 }
1006
1007 /* Issue prefetch instructions for array references in LOOPS.  */
1008
1009 void
1010 tree_ssa_prefetch_arrays (struct loops *loops)
1011 {
1012   unsigned i;
1013   struct loop *loop;
1014   bool unrolled = false;
1015
1016   if (!HAVE_prefetch
1017       /* It is possible to ask compiler for say -mtune=i486 -march=pentium4.
1018          -mtune=i486 causes us having PREFETCH_BLOCK 0, since this is part
1019          of processor costs and i486 does not have prefetch, but
1020          -march=pentium4 causes HAVE_prefetch to be true.  Ugh.  */
1021       || PREFETCH_BLOCK == 0)
1022     return;
1023
1024   initialize_original_copy_tables ();
1025
1026   if (!built_in_decls[BUILT_IN_PREFETCH])
1027     {
1028       tree type = build_function_type (void_type_node,
1029                                        tree_cons (NULL_TREE,
1030                                                   const_ptr_type_node,
1031                                                   NULL_TREE));
1032       tree decl = lang_hooks.builtin_function ("__builtin_prefetch", type,
1033                         BUILT_IN_PREFETCH, BUILT_IN_NORMAL,
1034                         NULL, NULL_TREE);
1035       DECL_IS_NOVOPS (decl) = true;
1036       built_in_decls[BUILT_IN_PREFETCH] = decl;
1037     }
1038
1039   /* We assume that size of cache line is a power of two, so verify this
1040      here.  */
1041   gcc_assert ((PREFETCH_BLOCK & (PREFETCH_BLOCK - 1)) == 0);
1042
1043   for (i = loops->num - 1; i > 0; i--)
1044     {
1045       loop = loops->parray[i];
1046
1047       if (dump_file && (dump_flags & TDF_DETAILS))
1048         fprintf (dump_file, "Processing loop %d:\n", loop->num);
1049
1050       if (loop)
1051         unrolled |= loop_prefetch_arrays (loops, loop);
1052
1053       if (dump_file && (dump_flags & TDF_DETAILS))
1054         fprintf (dump_file, "\n\n");
1055     }
1056
1057   if (unrolled)
1058     {
1059       scev_reset ();
1060       cleanup_tree_cfg_loop ();
1061     }
1062
1063   free_original_copy_tables ();
1064 }