OSDN Git Service

* config/rs6000/spe.md (SPE_ACC_REGNO): Delete definition.
[pf3gnuchains/gcc-fork.git] / gcc / sched-ebb.c
1 /* Instruction scheduling pass.
2    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3    1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
4    Free Software Foundation, Inc.
5    Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
6    and currently maintained by, Jim Wilson (wilson@cygnus.com)
7
8 This file is part of GCC.
9
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 2, or (at your option) any later
13 version.
14
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
18 for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING.  If not, write to the Free
22 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 02110-1301, USA.  */
24 \f
25 #include "config.h"
26 #include "system.h"
27 #include "coretypes.h"
28 #include "tm.h"
29 #include "toplev.h"
30 #include "rtl.h"
31 #include "tm_p.h"
32 #include "hard-reg-set.h"
33 #include "regs.h"
34 #include "function.h"
35 #include "flags.h"
36 #include "insn-config.h"
37 #include "insn-attr.h"
38 #include "except.h"
39 #include "toplev.h"
40 #include "recog.h"
41 #include "cfglayout.h"
42 #include "params.h"
43 #include "sched-int.h"
44 #include "target.h"
45 #include "output.h"
46
47 \f
48 /* The number of insns scheduled so far.  */
49 static int sched_n_insns;
50
51 /* The number of insns to be scheduled in total.  */
52 static int n_insns;
53
54 /* Set of blocks, that already have their dependencies calculated.  */
55 static bitmap_head dont_calc_deps;
56
57 /* Last basic block in current ebb.  */
58 static basic_block last_bb;
59
60 /* Implementations of the sched_info functions for region scheduling.  */
61 static void init_ready_list (void);
62 static void begin_schedule_ready (rtx, rtx);
63 static int schedule_more_p (void);
64 static const char *ebb_print_insn (rtx, int);
65 static int rank (rtx, rtx);
66 static int contributes_to_priority (rtx, rtx);
67 static void compute_jump_reg_dependencies (rtx, regset, regset, regset);
68 static basic_block earliest_block_with_similiar_load (basic_block, rtx);
69 static void add_deps_for_risky_insns (rtx, rtx);
70 static basic_block schedule_ebb (rtx, rtx);
71
72 static void add_remove_insn (rtx, int);
73 static void add_block1 (basic_block, basic_block);
74 static basic_block advance_target_bb (basic_block, rtx);
75 static void fix_recovery_cfg (int, int, int);
76
77 /* Return nonzero if there are more insns that should be scheduled.  */
78
79 static int
80 schedule_more_p (void)
81 {
82   return sched_n_insns < n_insns;
83 }
84
85 /* Print dependency information about ebb between HEAD and TAIL.  */
86 static void
87 debug_ebb_dependencies (rtx head, rtx tail)
88 {
89   fprintf (sched_dump,
90            ";;   --------------- forward dependences: ------------ \n");
91
92   fprintf (sched_dump, "\n;;   --- EBB Dependences --- from bb%d to bb%d \n",
93            BLOCK_NUM (head), BLOCK_NUM (tail));
94
95   debug_dependencies (head, tail);
96 }
97
98 /* Add all insns that are initially ready to the ready list READY.  Called
99    once before scheduling a set of insns.  */
100
101 static void
102 init_ready_list (void)
103 {
104   int n = 0;
105   rtx prev_head = current_sched_info->prev_head;
106   rtx next_tail = current_sched_info->next_tail;
107   rtx insn;
108
109   sched_n_insns = 0;
110
111   /* Print debugging information.  */
112   if (sched_verbose >= 5)
113     debug_ebb_dependencies (NEXT_INSN (prev_head), PREV_INSN (next_tail));
114
115   /* Initialize ready list with all 'ready' insns in target block.
116      Count number of insns in the target block being scheduled.  */
117   for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
118     {
119       try_ready (insn);
120       n++;
121     }
122
123   gcc_assert (n == n_insns);
124 }
125
126 /* INSN is being scheduled after LAST.  Update counters.  */
127 static void
128 begin_schedule_ready (rtx insn, rtx last)
129 {
130   sched_n_insns++;
131
132   if (BLOCK_FOR_INSN (insn) == last_bb
133       /* INSN is a jump in the last block, ...  */
134       && control_flow_insn_p (insn)
135       /* that is going to be moved over some instructions.  */
136       && last != PREV_INSN (insn))
137     {
138       edge e;
139       edge_iterator ei;
140       basic_block bb;
141
142       /* An obscure special case, where we do have partially dead
143          instruction scheduled after last control flow instruction.
144          In this case we can create new basic block.  It is
145          always exactly one basic block last in the sequence.  */
146       
147       FOR_EACH_EDGE (e, ei, last_bb->succs)
148         if (e->flags & EDGE_FALLTHRU)
149           break;
150
151 #ifdef ENABLE_CHECKING
152       gcc_assert (!e || !(e->flags & EDGE_COMPLEX));        
153
154       gcc_assert (BLOCK_FOR_INSN (insn) == last_bb
155                   && !IS_SPECULATION_CHECK_P (insn)
156                   && BB_HEAD (last_bb) != insn
157                   && BB_END (last_bb) == insn);
158
159       {
160         rtx x;
161
162         x = NEXT_INSN (insn);
163         if (e)
164           gcc_assert (NOTE_P (x) || LABEL_P (x));
165         else
166           gcc_assert (BARRIER_P (x));
167       }
168 #endif
169
170       if (e)
171         {
172           bb = split_edge (e);
173           gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_END (bb)));
174         }
175       else
176         /* Create an empty unreachable block after the INSN.  */
177         bb = create_basic_block (NEXT_INSN (insn), NULL_RTX, last_bb);
178       
179       /* split_edge () creates BB before E->DEST.  Keep in mind, that
180          this operation extends scheduling region till the end of BB.
181          Hence, we need to shift NEXT_TAIL, so haifa-sched.c won't go out
182          of the scheduling region.  */
183       current_sched_info->next_tail = NEXT_INSN (BB_END (bb));
184       gcc_assert (current_sched_info->next_tail);
185
186       add_block (bb, last_bb);
187       gcc_assert (last_bb == bb);
188     }
189 }
190
191 /* Return a string that contains the insn uid and optionally anything else
192    necessary to identify this insn in an output.  It's valid to use a
193    static buffer for this.  The ALIGNED parameter should cause the string
194    to be formatted so that multiple output lines will line up nicely.  */
195
196 static const char *
197 ebb_print_insn (rtx insn, int aligned ATTRIBUTE_UNUSED)
198 {
199   static char tmp[80];
200
201   sprintf (tmp, "%4d", INSN_UID (insn));
202   return tmp;
203 }
204
205 /* Compare priority of two insns.  Return a positive number if the second
206    insn is to be preferred for scheduling, and a negative one if the first
207    is to be preferred.  Zero if they are equally good.  */
208
209 static int
210 rank (rtx insn1, rtx insn2)
211 {
212   basic_block bb1 = BLOCK_FOR_INSN (insn1);
213   basic_block bb2 = BLOCK_FOR_INSN (insn2);
214
215   if (bb1->count > bb2->count
216       || bb1->frequency > bb2->frequency)
217     return -1;
218   if (bb1->count < bb2->count
219       || bb1->frequency < bb2->frequency)
220     return 1;
221   return 0;
222 }
223
224 /* NEXT is an instruction that depends on INSN (a backward dependence);
225    return nonzero if we should include this dependence in priority
226    calculations.  */
227
228 static int
229 contributes_to_priority (rtx next ATTRIBUTE_UNUSED,
230                          rtx insn ATTRIBUTE_UNUSED)
231 {
232   return 1;
233 }
234
235  /* INSN is a JUMP_INSN, COND_SET is the set of registers that are
236     conditionally set before INSN.  Store the set of registers that
237     must be considered as used by this jump in USED and that of
238     registers that must be considered as set in SET.  */
239
240 static void
241 compute_jump_reg_dependencies (rtx insn, regset cond_set, regset used,
242                                regset set)
243 {
244   basic_block b = BLOCK_FOR_INSN (insn);
245   edge e;
246   edge_iterator ei;
247
248   FOR_EACH_EDGE (e, ei, b->succs)
249     if (e->flags & EDGE_FALLTHRU)
250       /* The jump may be a by-product of a branch that has been merged
251          in the main codepath after being conditionalized.  Therefore
252          it may guard the fallthrough block from using a value that has
253          conditionally overwritten that of the main codepath.  So we
254          consider that it restores the value of the main codepath.  */
255       bitmap_and (set, df_get_live_in (e->dest), cond_set);
256     else
257       bitmap_ior_into (used, df_get_live_in (e->dest));
258 }
259
260 /* Used in schedule_insns to initialize current_sched_info for scheduling
261    regions (or single basic blocks).  */
262
263 static struct sched_info ebb_sched_info =
264 {
265   init_ready_list,
266   NULL,
267   schedule_more_p,
268   NULL,
269   rank,
270   ebb_print_insn,
271   contributes_to_priority,
272   compute_jump_reg_dependencies,
273
274   NULL, NULL,
275   NULL, NULL,
276   0, 1, 0,
277
278   add_remove_insn,
279   begin_schedule_ready,
280   add_block1,
281   advance_target_bb,
282   fix_recovery_cfg,
283   SCHED_EBB
284   /* We can create new blocks in begin_schedule_ready ().  */
285   | NEW_BBS
286 };
287 \f
288 /* Returns the earliest block in EBB currently being processed where a
289    "similar load" 'insn2' is found, and hence LOAD_INSN can move
290    speculatively into the found block.  All the following must hold:
291
292    (1) both loads have 1 base register (PFREE_CANDIDATEs).
293    (2) load_insn and load2 have a def-use dependence upon
294    the same insn 'insn1'.
295
296    From all these we can conclude that the two loads access memory
297    addresses that differ at most by a constant, and hence if moving
298    load_insn would cause an exception, it would have been caused by
299    load2 anyhow.
300
301    The function uses list (given by LAST_BLOCK) of already processed
302    blocks in EBB.  The list is formed in `add_deps_for_risky_insns'.  */
303
304 static basic_block
305 earliest_block_with_similiar_load (basic_block last_block, rtx load_insn)
306 {
307   dep_link_t back_link;
308   basic_block bb, earliest_block = NULL;
309
310   FOR_EACH_DEP_LINK (back_link, INSN_BACK_DEPS (load_insn))
311     {
312       rtx insn1 = DEP_LINK_PRO (back_link);
313
314       if (DEP_LINK_KIND (back_link) == REG_DEP_TRUE)
315         {
316           /* Found a DEF-USE dependence (insn1, load_insn).  */
317           dep_link_t fore_link;
318
319           FOR_EACH_DEP_LINK (fore_link, INSN_FORW_DEPS (insn1))
320             {
321               rtx insn2 = DEP_LINK_CON (fore_link);
322               basic_block insn2_block = BLOCK_FOR_INSN (insn2);
323
324               if (DEP_LINK_KIND (fore_link) == REG_DEP_TRUE)
325                 {
326                   if (earliest_block != NULL
327                       && earliest_block->index < insn2_block->index)
328                     continue;
329
330                   /* Found a DEF-USE dependence (insn1, insn2).  */
331                   if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
332                     /* insn2 not guaranteed to be a 1 base reg load.  */
333                     continue;
334
335                   for (bb = last_block; bb; bb = bb->aux)
336                     if (insn2_block == bb)
337                       break;
338
339                   if (!bb)
340                     /* insn2 is the similar load.  */
341                     earliest_block = insn2_block;
342                 }
343             }
344         }
345     }
346
347   return earliest_block;
348 }
349
350 /* The following function adds dependencies between jumps and risky
351    insns in given ebb.  */
352
353 static void
354 add_deps_for_risky_insns (rtx head, rtx tail)
355 {
356   rtx insn, prev;
357   int class;
358   rtx last_jump = NULL_RTX;
359   rtx next_tail = NEXT_INSN (tail);
360   basic_block last_block = NULL, bb;
361
362   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
363     if (control_flow_insn_p (insn))
364       {
365         bb = BLOCK_FOR_INSN (insn);
366         bb->aux = last_block;
367         last_block = bb;
368         last_jump = insn;
369       }
370     else if (INSN_P (insn) && last_jump != NULL_RTX)
371       {
372         class = haifa_classify_insn (insn);
373         prev = last_jump;
374         switch (class)
375           {
376           case PFREE_CANDIDATE:
377             if (flag_schedule_speculative_load)
378               {
379                 bb = earliest_block_with_similiar_load (last_block, insn);
380                 if (bb)
381                   {
382                     bb = bb->aux;
383                     if (!bb)
384                       break;
385                     prev = BB_END (bb);
386                   }
387               }
388             /* Fall through.  */
389           case TRAP_RISKY:
390           case IRISKY:
391           case PRISKY_CANDIDATE:
392             /* ??? We could implement better checking PRISKY_CANDIDATEs
393                analogous to sched-rgn.c.  */
394             /* We can not change the mode of the backward
395                dependency because REG_DEP_ANTI has the lowest
396                rank.  */
397             if (! sched_insns_conditions_mutex_p (insn, prev))
398               {
399                 if (!(current_sched_info->flags & DO_SPECULATION))
400                   {
401                     enum DEPS_ADJUST_RESULT res;
402                     
403                     res = add_or_update_back_dep (insn, prev,
404                                                   REG_DEP_ANTI, DEP_ANTI);
405
406                     if (res == DEP_CREATED)
407                       add_forw_dep (DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)));
408                     else
409                       gcc_assert (res != DEP_CHANGED);
410                   }
411                 else
412                   add_or_update_back_forw_dep (insn, prev, REG_DEP_ANTI,
413                                                set_dep_weak (DEP_ANTI,
414                                                              BEGIN_CONTROL,
415                                                              MAX_DEP_WEAK));
416               }
417
418             break;
419
420           default:
421             break;
422           }
423       }
424   /* Maintain the invariant that bb->aux is clear after use.  */
425   while (last_block)
426     {
427       bb = last_block->aux;
428       last_block->aux = NULL;
429       last_block = bb;
430     }
431 }
432
433 /* Schedule a single extended basic block, defined by the boundaries HEAD
434    and TAIL.  */
435
436 static basic_block
437 schedule_ebb (rtx head, rtx tail)
438 {
439   basic_block first_bb, target_bb;
440   struct deps tmp_deps;
441   
442   first_bb = BLOCK_FOR_INSN (head);
443   last_bb = BLOCK_FOR_INSN (tail);
444
445   if (no_real_insns_p (head, tail))
446     return BLOCK_FOR_INSN (tail);
447
448   gcc_assert (INSN_P (head) && INSN_P (tail));
449
450   if (!bitmap_bit_p (&dont_calc_deps, first_bb->index))
451     {
452       init_deps_global ();
453
454       /* Compute backward dependencies.  */
455       init_deps (&tmp_deps);
456       sched_analyze (&tmp_deps, head, tail);
457       free_deps (&tmp_deps);
458
459       /* Compute forward dependencies.  */
460       compute_forward_dependences (head, tail);
461
462       add_deps_for_risky_insns (head, tail);
463
464       if (targetm.sched.dependencies_evaluation_hook)
465         targetm.sched.dependencies_evaluation_hook (head, tail);
466
467       finish_deps_global ();
468     }
469   else
470     /* Only recovery blocks can have their dependencies already calculated,
471        and they always are single block ebbs.  */       
472     gcc_assert (first_bb == last_bb);
473
474   /* Set priorities.  */
475   current_sched_info->sched_max_insns_priority = 0;
476   n_insns = set_priorities (head, tail);
477   current_sched_info->sched_max_insns_priority++;
478
479   current_sched_info->prev_head = PREV_INSN (head);
480   current_sched_info->next_tail = NEXT_INSN (tail);
481
482   /* rm_other_notes only removes notes which are _inside_ the
483      block---that is, it won't remove notes before the first real insn
484      or after the last real insn of the block.  So if the first insn
485      has a REG_SAVE_NOTE which would otherwise be emitted before the
486      insn, it is redundant with the note before the start of the
487      block, and so we have to take it out.  */
488   if (INSN_P (head))
489     {
490       rtx note;
491
492       for (note = REG_NOTES (head); note; note = XEXP (note, 1))
493         if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
494           remove_note (head, note);
495     }
496
497   /* Remove remaining note insns from the block, save them in
498      note_list.  These notes are restored at the end of
499      schedule_block ().  */
500   rm_other_notes (head, tail);
501
502   unlink_bb_notes (first_bb, last_bb);
503
504   current_sched_info->queue_must_finish_empty = 1;
505
506   target_bb = first_bb;
507   schedule_block (&target_bb, n_insns);
508
509   /* We might pack all instructions into fewer blocks,
510      so we may made some of them empty.  Can't assert (b == last_bb).  */
511   
512   /* Sanity check: verify that all region insns were scheduled.  */
513   gcc_assert (sched_n_insns == n_insns);
514   head = current_sched_info->head;
515   tail = current_sched_info->tail;
516
517   if (EDGE_COUNT (last_bb->preds) == 0)
518     /* LAST_BB is unreachable.  */
519     {
520       gcc_assert (first_bb != last_bb
521                   && EDGE_COUNT (last_bb->succs) == 0);
522       last_bb = last_bb->prev_bb;
523       delete_basic_block (last_bb->next_bb);
524     }
525
526   return last_bb;
527 }
528
529 /* The one entry point in this file.  */
530
531 void
532 schedule_ebbs (void)
533 {
534   basic_block bb;
535   int probability_cutoff;
536   rtx tail;
537
538   if (profile_info && flag_branch_probabilities)
539     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
540   else
541     probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
542   probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
543
544   /* Taking care of this degenerate case makes the rest of
545      this code simpler.  */
546   if (n_basic_blocks == NUM_FIXED_BLOCKS)
547     return;
548
549   /* We need current_sched_info in init_dependency_caches, which is
550      invoked via sched_init.  */
551   current_sched_info = &ebb_sched_info;
552
553   df_set_flags (DF_LR_RUN_DCE);
554   df_note_add_problem ();
555   df_analyze ();
556   df_clear_flags (DF_LR_RUN_DCE);
557   regstat_compute_calls_crossed ();
558   sched_init ();
559
560   compute_bb_for_insn ();
561
562   /* Initialize DONT_CALC_DEPS and ebb-{start, end} markers.  */
563   bitmap_initialize (&dont_calc_deps, 0);
564   bitmap_clear (&dont_calc_deps);
565
566   /* Schedule every region in the subroutine.  */
567   FOR_EACH_BB (bb)
568     {
569       rtx head = BB_HEAD (bb);
570
571       for (;;)
572         {
573           edge e;
574           edge_iterator ei;
575           tail = BB_END (bb);
576           if (bb->next_bb == EXIT_BLOCK_PTR
577               || LABEL_P (BB_HEAD (bb->next_bb)))
578             break;
579           FOR_EACH_EDGE (e, ei, bb->succs)
580             if ((e->flags & EDGE_FALLTHRU) != 0)
581               break;
582           if (! e)
583             break;
584           if (e->probability <= probability_cutoff)
585             break;
586           bb = bb->next_bb;
587         }
588
589       /* Blah.  We should fix the rest of the code not to get confused by
590          a note or two.  */
591       while (head != tail)
592         {
593           if (NOTE_P (head))
594             head = NEXT_INSN (head);
595           else if (NOTE_P (tail))
596             tail = PREV_INSN (tail);
597           else if (LABEL_P (head))
598             head = NEXT_INSN (head);
599           else
600             break;
601         }
602
603       bb = schedule_ebb (head, tail);
604     }
605   bitmap_clear (&dont_calc_deps);
606
607   /* Reposition the prologue and epilogue notes in case we moved the
608      prologue/epilogue insns.  */
609   if (reload_completed)
610     reposition_prologue_and_epilogue_notes ();
611
612   sched_finish ();
613   regstat_free_calls_crossed ();
614 }
615
616 /* INSN has been added to/removed from current ebb.  */
617 static void
618 add_remove_insn (rtx insn ATTRIBUTE_UNUSED, int remove_p)
619 {
620   if (!remove_p)
621     n_insns++;
622   else
623     n_insns--;
624 }
625
626 /* BB was added to ebb after AFTER.  */
627 static void
628 add_block1 (basic_block bb, basic_block after)
629 {
630   /* Recovery blocks are always bounded by BARRIERS, 
631      therefore, they always form single block EBB,
632      therefore, we can use rec->index to identify such EBBs.  */
633   if (after == EXIT_BLOCK_PTR)
634     bitmap_set_bit (&dont_calc_deps, bb->index);
635   else if (after == last_bb)
636     last_bb = bb;
637 }
638
639 /* Return next block in ebb chain.  For parameter meaning please refer to
640    sched-int.h: struct sched_info: advance_target_bb.  */
641 static basic_block
642 advance_target_bb (basic_block bb, rtx insn)
643 {
644   if (insn)
645     {
646       if (BLOCK_FOR_INSN (insn) != bb
647           && control_flow_insn_p (insn)
648           /* We handle interblock movement of the speculation check
649              or over a speculation check in
650              haifa-sched.c: move_block_after_check ().  */
651           && !IS_SPECULATION_BRANCHY_CHECK_P (insn)
652           && !IS_SPECULATION_BRANCHY_CHECK_P (BB_END (bb)))
653         {
654           /* Assert that we don't move jumps across blocks.  */
655           gcc_assert (!control_flow_insn_p (BB_END (bb))
656                       && NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (bb->next_bb)));
657           return bb;
658         }
659       else
660         return 0;
661     }
662   else
663     /* Return next non empty block.  */
664     {
665       do
666         {
667           gcc_assert (bb != last_bb);
668
669           bb = bb->next_bb;
670         }
671       while (bb_note (bb) == BB_END (bb));
672
673       return bb;
674     }
675 }
676
677 /* Fix internal data after interblock movement of jump instruction.
678    For parameter meaning please refer to
679    sched-int.h: struct sched_info: fix_recovery_cfg.  */
680 static void
681 fix_recovery_cfg (int bbi ATTRIBUTE_UNUSED, int jump_bbi, int jump_bb_nexti)
682 {
683   gcc_assert (last_bb->index != bbi);
684
685   if (jump_bb_nexti == last_bb->index)
686     last_bb = BASIC_BLOCK (jump_bbi);
687 }