OSDN Git Service

3ac7fbd6034d81858f54d052dbf38f57b4904e8e
[pf3gnuchains/gcc-fork.git] / gcc / bb-reorder.c
1 /* Basic block reordering routines for the GNU compiler.
2    Copyright (C) 2000, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010, 2011
3    Free Software Foundation, Inc.
4
5    This file is part of GCC.
6
7    GCC is free software; you can redistribute it and/or modify it
8    under the terms of the GNU General Public License as published by
9    the Free Software Foundation; either version 3, or (at your option)
10    any later version.
11
12    GCC is distributed in the hope that it will be useful, but WITHOUT
13    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
15    License for more details.
16
17    You should have received a copy of the GNU General Public License
18    along with GCC; see the file COPYING3.  If not see
19    <http://www.gnu.org/licenses/>.  */
20
21 /* This (greedy) algorithm constructs traces in several rounds.
22    The construction starts from "seeds".  The seed for the first round
23    is the entry point of function.  When there are more than one seed
24    that one is selected first that has the lowest key in the heap
25    (see function bb_to_key).  Then the algorithm repeatedly adds the most
26    probable successor to the end of a trace.  Finally it connects the traces.
27
28    There are two parameters: Branch Threshold and Exec Threshold.
29    If the edge to a successor of the actual basic block is lower than
30    Branch Threshold or the frequency of the successor is lower than
31    Exec Threshold the successor will be the seed in one of the next rounds.
32    Each round has these parameters lower than the previous one.
33    The last round has to have these parameters set to zero
34    so that the remaining blocks are picked up.
35
36    The algorithm selects the most probable successor from all unvisited
37    successors and successors that have been added to this trace.
38    The other successors (that has not been "sent" to the next round) will be
39    other seeds for this round and the secondary traces will start in them.
40    If the successor has not been visited in this trace it is added to the trace
41    (however, there is some heuristic for simple branches).
42    If the successor has been visited in this trace the loop has been found.
43    If the loop has many iterations the loop is rotated so that the
44    source block of the most probable edge going out from the loop
45    is the last block of the trace.
46    If the loop has few iterations and there is no edge from the last block of
47    the loop going out from loop the loop header is duplicated.
48    Finally, the construction of the trace is terminated.
49
50    When connecting traces it first checks whether there is an edge from the
51    last block of one trace to the first block of another trace.
52    When there are still some unconnected traces it checks whether there exists
53    a basic block BB such that BB is a successor of the last bb of one trace
54    and BB is a predecessor of the first block of another trace. In this case,
55    BB is duplicated and the traces are connected through this duplicate.
56    The rest of traces are simply connected so there will be a jump to the
57    beginning of the rest of trace.
58
59
60    References:
61
62    "Software Trace Cache"
63    A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999
64    http://citeseer.nj.nec.com/15361.html
65
66 */
67
68 #include "config.h"
69 #include "system.h"
70 #include "coretypes.h"
71 #include "tm.h"
72 #include "rtl.h"
73 #include "regs.h"
74 #include "flags.h"
75 #include "timevar.h"
76 #include "output.h"
77 #include "cfglayout.h"
78 #include "fibheap.h"
79 #include "target.h"
80 #include "function.h"
81 #include "tm_p.h"
82 #include "obstack.h"
83 #include "expr.h"
84 #include "params.h"
85 #include "diagnostic-core.h"
86 #include "toplev.h" /* user_defined_section_attribute */
87 #include "tree-pass.h"
88 #include "df.h"
89 #include "bb-reorder.h"
90 #include "except.h"
91
92 /* The number of rounds.  In most cases there will only be 4 rounds, but
93    when partitioning hot and cold basic blocks into separate sections of
94    the .o file there will be an extra round.*/
95 #define N_ROUNDS 5
96
97 /* Stubs in case we don't have a return insn.
98    We have to check at runtime too, not only compiletime.  */
99
100 #ifndef HAVE_return
101 #define HAVE_return 0
102 #define gen_return() NULL_RTX
103 #endif
104
105
106 struct target_bb_reorder default_target_bb_reorder;
107 #if SWITCHABLE_TARGET
108 struct target_bb_reorder *this_target_bb_reorder = &default_target_bb_reorder;
109 #endif
110
111 #define uncond_jump_length \
112   (this_target_bb_reorder->x_uncond_jump_length)
113
114 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE.  */
115 static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0};
116
117 /* Exec thresholds in thousandths (per mille) of the frequency of bb 0.  */
118 static int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0};
119
120 /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
121    block the edge destination is not duplicated while connecting traces.  */
122 #define DUPLICATION_THRESHOLD 100
123
124 /* Structure to hold needed information for each basic block.  */
125 typedef struct bbro_basic_block_data_def
126 {
127   /* Which trace is the bb start of (-1 means it is not a start of a trace).  */
128   int start_of_trace;
129
130   /* Which trace is the bb end of (-1 means it is not an end of a trace).  */
131   int end_of_trace;
132
133   /* Which trace is the bb in?  */
134   int in_trace;
135
136   /* Which heap is BB in (if any)?  */
137   fibheap_t heap;
138
139   /* Which heap node is BB in (if any)?  */
140   fibnode_t node;
141 } bbro_basic_block_data;
142
143 /* The current size of the following dynamic array.  */
144 static int array_size;
145
146 /* The array which holds needed information for basic blocks.  */
147 static bbro_basic_block_data *bbd;
148
149 /* To avoid frequent reallocation the size of arrays is greater than needed,
150    the number of elements is (not less than) 1.25 * size_wanted.  */
151 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
152
153 /* Free the memory and set the pointer to NULL.  */
154 #define FREE(P) (gcc_assert (P), free (P), P = 0)
155
156 /* Structure for holding information about a trace.  */
157 struct trace
158 {
159   /* First and last basic block of the trace.  */
160   basic_block first, last;
161
162   /* The round of the STC creation which this trace was found in.  */
163   int round;
164
165   /* The length (i.e. the number of basic blocks) of the trace.  */
166   int length;
167 };
168
169 /* Maximum frequency and count of one of the entry blocks.  */
170 static int max_entry_frequency;
171 static gcov_type max_entry_count;
172
173 /* Local function prototypes.  */
174 static void find_traces (int *, struct trace *);
175 static basic_block rotate_loop (edge, struct trace *, int);
176 static void mark_bb_visited (basic_block, int);
177 static void find_traces_1_round (int, int, gcov_type, struct trace *, int *,
178                                  int, fibheap_t *, int);
179 static basic_block copy_bb (basic_block, edge, basic_block, int);
180 static fibheapkey_t bb_to_key (basic_block);
181 static bool better_edge_p (const_basic_block, const_edge, int, int, int, int, const_edge);
182 static void connect_traces (int, struct trace *);
183 static bool copy_bb_p (const_basic_block, int);
184 static int get_uncond_jump_length (void);
185 static bool push_to_next_round_p (const_basic_block, int, int, int, gcov_type);
186 \f
187 /* Check to see if bb should be pushed into the next round of trace
188    collections or not.  Reasons for pushing the block forward are 1).
189    If the block is cold, we are doing partitioning, and there will be
190    another round (cold partition blocks are not supposed to be
191    collected into traces until the very last round); or 2). There will
192    be another round, and the basic block is not "hot enough" for the
193    current round of trace collection.  */
194
195 static bool
196 push_to_next_round_p (const_basic_block bb, int round, int number_of_rounds,
197                       int exec_th, gcov_type count_th)
198 {
199   bool there_exists_another_round;
200   bool block_not_hot_enough;
201
202   there_exists_another_round = round < number_of_rounds - 1;
203
204   block_not_hot_enough = (bb->frequency < exec_th
205                           || bb->count < count_th
206                           || probably_never_executed_bb_p (bb));
207
208   if (there_exists_another_round
209       && block_not_hot_enough)
210     return true;
211   else
212     return false;
213 }
214
215 /* Find the traces for Software Trace Cache.  Chain each trace through
216    RBI()->next.  Store the number of traces to N_TRACES and description of
217    traces to TRACES.  */
218
219 static void
220 find_traces (int *n_traces, struct trace *traces)
221 {
222   int i;
223   int number_of_rounds;
224   edge e;
225   edge_iterator ei;
226   fibheap_t heap;
227
228   /* Add one extra round of trace collection when partitioning hot/cold
229      basic blocks into separate sections.  The last round is for all the
230      cold blocks (and ONLY the cold blocks).  */
231
232   number_of_rounds = N_ROUNDS - 1;
233
234   /* Insert entry points of function into heap.  */
235   heap = fibheap_new ();
236   max_entry_frequency = 0;
237   max_entry_count = 0;
238   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
239     {
240       bbd[e->dest->index].heap = heap;
241       bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest),
242                                                     e->dest);
243       if (e->dest->frequency > max_entry_frequency)
244         max_entry_frequency = e->dest->frequency;
245       if (e->dest->count > max_entry_count)
246         max_entry_count = e->dest->count;
247     }
248
249   /* Find the traces.  */
250   for (i = 0; i < number_of_rounds; i++)
251     {
252       gcov_type count_threshold;
253
254       if (dump_file)
255         fprintf (dump_file, "STC - round %d\n", i + 1);
256
257       if (max_entry_count < INT_MAX / 1000)
258         count_threshold = max_entry_count * exec_threshold[i] / 1000;
259       else
260         count_threshold = max_entry_count / 1000 * exec_threshold[i];
261
262       find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
263                            max_entry_frequency * exec_threshold[i] / 1000,
264                            count_threshold, traces, n_traces, i, &heap,
265                            number_of_rounds);
266     }
267   fibheap_delete (heap);
268
269   if (dump_file)
270     {
271       for (i = 0; i < *n_traces; i++)
272         {
273           basic_block bb;
274           fprintf (dump_file, "Trace %d (round %d):  ", i + 1,
275                    traces[i].round + 1);
276           for (bb = traces[i].first; bb != traces[i].last; bb = (basic_block) bb->aux)
277             fprintf (dump_file, "%d [%d] ", bb->index, bb->frequency);
278           fprintf (dump_file, "%d [%d]\n", bb->index, bb->frequency);
279         }
280       fflush (dump_file);
281     }
282 }
283
284 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
285    (with sequential number TRACE_N).  */
286
287 static basic_block
288 rotate_loop (edge back_edge, struct trace *trace, int trace_n)
289 {
290   basic_block bb;
291
292   /* Information about the best end (end after rotation) of the loop.  */
293   basic_block best_bb = NULL;
294   edge best_edge = NULL;
295   int best_freq = -1;
296   gcov_type best_count = -1;
297   /* The best edge is preferred when its destination is not visited yet
298      or is a start block of some trace.  */
299   bool is_preferred = false;
300
301   /* Find the most frequent edge that goes out from current trace.  */
302   bb = back_edge->dest;
303   do
304     {
305       edge e;
306       edge_iterator ei;
307
308       FOR_EACH_EDGE (e, ei, bb->succs)
309         if (e->dest != EXIT_BLOCK_PTR
310             && e->dest->il.rtl->visited != trace_n
311             && (e->flags & EDGE_CAN_FALLTHRU)
312             && !(e->flags & EDGE_COMPLEX))
313         {
314           if (is_preferred)
315             {
316               /* The best edge is preferred.  */
317               if (!e->dest->il.rtl->visited
318                   || bbd[e->dest->index].start_of_trace >= 0)
319                 {
320                   /* The current edge E is also preferred.  */
321                   int freq = EDGE_FREQUENCY (e);
322                   if (freq > best_freq || e->count > best_count)
323                     {
324                       best_freq = freq;
325                       best_count = e->count;
326                       best_edge = e;
327                       best_bb = bb;
328                     }
329                 }
330             }
331           else
332             {
333               if (!e->dest->il.rtl->visited
334                   || bbd[e->dest->index].start_of_trace >= 0)
335                 {
336                   /* The current edge E is preferred.  */
337                   is_preferred = true;
338                   best_freq = EDGE_FREQUENCY (e);
339                   best_count = e->count;
340                   best_edge = e;
341                   best_bb = bb;
342                 }
343               else
344                 {
345                   int freq = EDGE_FREQUENCY (e);
346                   if (!best_edge || freq > best_freq || e->count > best_count)
347                     {
348                       best_freq = freq;
349                       best_count = e->count;
350                       best_edge = e;
351                       best_bb = bb;
352                     }
353                 }
354             }
355         }
356       bb = (basic_block) bb->aux;
357     }
358   while (bb != back_edge->dest);
359
360   if (best_bb)
361     {
362       /* Rotate the loop so that the BEST_EDGE goes out from the last block of
363          the trace.  */
364       if (back_edge->dest == trace->first)
365         {
366           trace->first = (basic_block) best_bb->aux;
367         }
368       else
369         {
370           basic_block prev_bb;
371
372           for (prev_bb = trace->first;
373                prev_bb->aux != back_edge->dest;
374                prev_bb = (basic_block) prev_bb->aux)
375             ;
376           prev_bb->aux = best_bb->aux;
377
378           /* Try to get rid of uncond jump to cond jump.  */
379           if (single_succ_p (prev_bb))
380             {
381               basic_block header = single_succ (prev_bb);
382
383               /* Duplicate HEADER if it is a small block containing cond jump
384                  in the end.  */
385               if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0)
386                   && !find_reg_note (BB_END (header), REG_CROSSING_JUMP,
387                                      NULL_RTX))
388                 copy_bb (header, single_succ_edge (prev_bb), prev_bb, trace_n);
389             }
390         }
391     }
392   else
393     {
394       /* We have not found suitable loop tail so do no rotation.  */
395       best_bb = back_edge->src;
396     }
397   best_bb->aux = NULL;
398   return best_bb;
399 }
400
401 /* This function marks BB that it was visited in trace number TRACE.  */
402
403 static void
404 mark_bb_visited (basic_block bb, int trace)
405 {
406   bb->il.rtl->visited = trace;
407   if (bbd[bb->index].heap)
408     {
409       fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
410       bbd[bb->index].heap = NULL;
411       bbd[bb->index].node = NULL;
412     }
413 }
414
415 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
416    not include basic blocks their probability is lower than BRANCH_TH or their
417    frequency is lower than EXEC_TH into traces (or count is lower than
418    COUNT_TH).  It stores the new traces into TRACES and modifies the number of
419    traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
420    expects that starting basic blocks are in *HEAP and at the end it deletes
421    *HEAP and stores starting points for the next round into new *HEAP.  */
422
423 static void
424 find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
425                      struct trace *traces, int *n_traces, int round,
426                      fibheap_t *heap, int number_of_rounds)
427 {
428   /* Heap for discarded basic blocks which are possible starting points for
429      the next round.  */
430   fibheap_t new_heap = fibheap_new ();
431
432   while (!fibheap_empty (*heap))
433     {
434       basic_block bb;
435       struct trace *trace;
436       edge best_edge, e;
437       fibheapkey_t key;
438       edge_iterator ei;
439
440       bb = (basic_block) fibheap_extract_min (*heap);
441       bbd[bb->index].heap = NULL;
442       bbd[bb->index].node = NULL;
443
444       if (dump_file)
445         fprintf (dump_file, "Getting bb %d\n", bb->index);
446
447       /* If the BB's frequency is too low send BB to the next round.  When
448          partitioning hot/cold blocks into separate sections, make sure all
449          the cold blocks (and ONLY the cold blocks) go into the (extra) final
450          round.  */
451
452       if (push_to_next_round_p (bb, round, number_of_rounds, exec_th,
453                                 count_th))
454         {
455           int key = bb_to_key (bb);
456           bbd[bb->index].heap = new_heap;
457           bbd[bb->index].node = fibheap_insert (new_heap, key, bb);
458
459           if (dump_file)
460             fprintf (dump_file,
461                      "  Possible start point of next round: %d (key: %d)\n",
462                      bb->index, key);
463           continue;
464         }
465
466       trace = traces + *n_traces;
467       trace->first = bb;
468       trace->round = round;
469       trace->length = 0;
470       bbd[bb->index].in_trace = *n_traces;
471       (*n_traces)++;
472
473       do
474         {
475           int prob, freq;
476           bool ends_in_call;
477
478           /* The probability and frequency of the best edge.  */
479           int best_prob = INT_MIN / 2;
480           int best_freq = INT_MIN / 2;
481
482           best_edge = NULL;
483           mark_bb_visited (bb, *n_traces);
484           trace->length++;
485
486           if (dump_file)
487             fprintf (dump_file, "Basic block %d was visited in trace %d\n",
488                      bb->index, *n_traces - 1);
489
490           ends_in_call = block_ends_with_call_p (bb);
491
492           /* Select the successor that will be placed after BB.  */
493           FOR_EACH_EDGE (e, ei, bb->succs)
494             {
495               gcc_assert (!(e->flags & EDGE_FAKE));
496
497               if (e->dest == EXIT_BLOCK_PTR)
498                 continue;
499
500               if (e->dest->il.rtl->visited
501                   && e->dest->il.rtl->visited != *n_traces)
502                 continue;
503
504               if (BB_PARTITION (e->dest) != BB_PARTITION (bb))
505                 continue;
506
507               prob = e->probability;
508               freq = e->dest->frequency;
509
510               /* The only sensible preference for a call instruction is the
511                  fallthru edge.  Don't bother selecting anything else.  */
512               if (ends_in_call)
513                 {
514                   if (e->flags & EDGE_CAN_FALLTHRU)
515                     {
516                       best_edge = e;
517                       best_prob = prob;
518                       best_freq = freq;
519                     }
520                   continue;
521                 }
522
523               /* Edge that cannot be fallthru or improbable or infrequent
524                  successor (i.e. it is unsuitable successor).  */
525               if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
526                   || prob < branch_th || EDGE_FREQUENCY (e) < exec_th
527                   || e->count < count_th)
528                 continue;
529
530               /* If partitioning hot/cold basic blocks, don't consider edges
531                  that cross section boundaries.  */
532
533               if (better_edge_p (bb, e, prob, freq, best_prob, best_freq,
534                                  best_edge))
535                 {
536                   best_edge = e;
537                   best_prob = prob;
538                   best_freq = freq;
539                 }
540             }
541
542           /* If the best destination has multiple predecessors, and can be
543              duplicated cheaper than a jump, don't allow it to be added
544              to a trace.  We'll duplicate it when connecting traces.  */
545           if (best_edge && EDGE_COUNT (best_edge->dest->preds) >= 2
546               && copy_bb_p (best_edge->dest, 0))
547             best_edge = NULL;
548
549           /* Add all non-selected successors to the heaps.  */
550           FOR_EACH_EDGE (e, ei, bb->succs)
551             {
552               if (e == best_edge
553                   || e->dest == EXIT_BLOCK_PTR
554                   || e->dest->il.rtl->visited)
555                 continue;
556
557               key = bb_to_key (e->dest);
558
559               if (bbd[e->dest->index].heap)
560                 {
561                   /* E->DEST is already in some heap.  */
562                   if (key != bbd[e->dest->index].node->key)
563                     {
564                       if (dump_file)
565                         {
566                           fprintf (dump_file,
567                                    "Changing key for bb %d from %ld to %ld.\n",
568                                    e->dest->index,
569                                    (long) bbd[e->dest->index].node->key,
570                                    key);
571                         }
572                       fibheap_replace_key (bbd[e->dest->index].heap,
573                                            bbd[e->dest->index].node, key);
574                     }
575                 }
576               else
577                 {
578                   fibheap_t which_heap = *heap;
579
580                   prob = e->probability;
581                   freq = EDGE_FREQUENCY (e);
582
583                   if (!(e->flags & EDGE_CAN_FALLTHRU)
584                       || (e->flags & EDGE_COMPLEX)
585                       || prob < branch_th || freq < exec_th
586                       || e->count < count_th)
587                     {
588                       /* When partitioning hot/cold basic blocks, make sure
589                          the cold blocks (and only the cold blocks) all get
590                          pushed to the last round of trace collection.  */
591
592                       if (push_to_next_round_p (e->dest, round,
593                                                 number_of_rounds,
594                                                 exec_th, count_th))
595                         which_heap = new_heap;
596                     }
597
598                   bbd[e->dest->index].heap = which_heap;
599                   bbd[e->dest->index].node = fibheap_insert (which_heap,
600                                                                 key, e->dest);
601
602                   if (dump_file)
603                     {
604                       fprintf (dump_file,
605                                "  Possible start of %s round: %d (key: %ld)\n",
606                                (which_heap == new_heap) ? "next" : "this",
607                                e->dest->index, (long) key);
608                     }
609
610                 }
611             }
612
613           if (best_edge) /* Suitable successor was found.  */
614             {
615               if (best_edge->dest->il.rtl->visited == *n_traces)
616                 {
617                   /* We do nothing with one basic block loops.  */
618                   if (best_edge->dest != bb)
619                     {
620                       if (EDGE_FREQUENCY (best_edge)
621                           > 4 * best_edge->dest->frequency / 5)
622                         {
623                           /* The loop has at least 4 iterations.  If the loop
624                              header is not the first block of the function
625                              we can rotate the loop.  */
626
627                           if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb)
628                             {
629                               if (dump_file)
630                                 {
631                                   fprintf (dump_file,
632                                            "Rotating loop %d - %d\n",
633                                            best_edge->dest->index, bb->index);
634                                 }
635                               bb->aux = best_edge->dest;
636                               bbd[best_edge->dest->index].in_trace =
637                                                              (*n_traces) - 1;
638                               bb = rotate_loop (best_edge, trace, *n_traces);
639                             }
640                         }
641                       else
642                         {
643                           /* The loop has less than 4 iterations.  */
644
645                           if (single_succ_p (bb)
646                               && copy_bb_p (best_edge->dest,
647                                             optimize_edge_for_speed_p (best_edge)))
648                             {
649                               bb = copy_bb (best_edge->dest, best_edge, bb,
650                                             *n_traces);
651                               trace->length++;
652                             }
653                         }
654                     }
655
656                   /* Terminate the trace.  */
657                   break;
658                 }
659               else
660                 {
661                   /* Check for a situation
662
663                     A
664                    /|
665                   B |
666                    \|
667                     C
668
669                   where
670                   EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
671                     >= EDGE_FREQUENCY (AC).
672                   (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
673                   Best ordering is then A B C.
674
675                   This situation is created for example by:
676
677                   if (A) B;
678                   C;
679
680                   */
681
682                   FOR_EACH_EDGE (e, ei, bb->succs)
683                     if (e != best_edge
684                         && (e->flags & EDGE_CAN_FALLTHRU)
685                         && !(e->flags & EDGE_COMPLEX)
686                         && !e->dest->il.rtl->visited
687                         && single_pred_p (e->dest)
688                         && !(e->flags & EDGE_CROSSING)
689                         && single_succ_p (e->dest)
690                         && (single_succ_edge (e->dest)->flags
691                             & EDGE_CAN_FALLTHRU)
692                         && !(single_succ_edge (e->dest)->flags & EDGE_COMPLEX)
693                         && single_succ (e->dest) == best_edge->dest
694                         && 2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge))
695                       {
696                         best_edge = e;
697                         if (dump_file)
698                           fprintf (dump_file, "Selecting BB %d\n",
699                                    best_edge->dest->index);
700                         break;
701                       }
702
703                   bb->aux = best_edge->dest;
704                   bbd[best_edge->dest->index].in_trace = (*n_traces) - 1;
705                   bb = best_edge->dest;
706                 }
707             }
708         }
709       while (best_edge);
710       trace->last = bb;
711       bbd[trace->first->index].start_of_trace = *n_traces - 1;
712       bbd[trace->last->index].end_of_trace = *n_traces - 1;
713
714       /* The trace is terminated so we have to recount the keys in heap
715          (some block can have a lower key because now one of its predecessors
716          is an end of the trace).  */
717       FOR_EACH_EDGE (e, ei, bb->succs)
718         {
719           if (e->dest == EXIT_BLOCK_PTR
720               || e->dest->il.rtl->visited)
721             continue;
722
723           if (bbd[e->dest->index].heap)
724             {
725               key = bb_to_key (e->dest);
726               if (key != bbd[e->dest->index].node->key)
727                 {
728                   if (dump_file)
729                     {
730                       fprintf (dump_file,
731                                "Changing key for bb %d from %ld to %ld.\n",
732                                e->dest->index,
733                                (long) bbd[e->dest->index].node->key, key);
734                     }
735                   fibheap_replace_key (bbd[e->dest->index].heap,
736                                        bbd[e->dest->index].node,
737                                        key);
738                 }
739             }
740         }
741     }
742
743   fibheap_delete (*heap);
744
745   /* "Return" the new heap.  */
746   *heap = new_heap;
747 }
748
749 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
750    it to trace after BB, mark OLD_BB visited and update pass' data structures
751    (TRACE is a number of trace which OLD_BB is duplicated to).  */
752
753 static basic_block
754 copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
755 {
756   basic_block new_bb;
757
758   new_bb = duplicate_block (old_bb, e, bb);
759   BB_COPY_PARTITION (new_bb, old_bb);
760
761   gcc_assert (e->dest == new_bb);
762   gcc_assert (!e->dest->il.rtl->visited);
763
764   if (dump_file)
765     fprintf (dump_file,
766              "Duplicated bb %d (created bb %d)\n",
767              old_bb->index, new_bb->index);
768   new_bb->il.rtl->visited = trace;
769   new_bb->aux = bb->aux;
770   bb->aux = new_bb;
771
772   if (new_bb->index >= array_size || last_basic_block > array_size)
773     {
774       int i;
775       int new_size;
776
777       new_size = MAX (last_basic_block, new_bb->index + 1);
778       new_size = GET_ARRAY_SIZE (new_size);
779       bbd = XRESIZEVEC (bbro_basic_block_data, bbd, new_size);
780       for (i = array_size; i < new_size; i++)
781         {
782           bbd[i].start_of_trace = -1;
783           bbd[i].in_trace = -1;
784           bbd[i].end_of_trace = -1;
785           bbd[i].heap = NULL;
786           bbd[i].node = NULL;
787         }
788       array_size = new_size;
789
790       if (dump_file)
791         {
792           fprintf (dump_file,
793                    "Growing the dynamic array to %d elements.\n",
794                    array_size);
795         }
796     }
797
798   bbd[new_bb->index].in_trace = trace;
799
800   return new_bb;
801 }
802
803 /* Compute and return the key (for the heap) of the basic block BB.  */
804
805 static fibheapkey_t
806 bb_to_key (basic_block bb)
807 {
808   edge e;
809   edge_iterator ei;
810   int priority = 0;
811
812   /* Do not start in probably never executed blocks.  */
813
814   if (BB_PARTITION (bb) == BB_COLD_PARTITION
815       || probably_never_executed_bb_p (bb))
816     return BB_FREQ_MAX;
817
818   /* Prefer blocks whose predecessor is an end of some trace
819      or whose predecessor edge is EDGE_DFS_BACK.  */
820   FOR_EACH_EDGE (e, ei, bb->preds)
821     {
822       if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0)
823           || (e->flags & EDGE_DFS_BACK))
824         {
825           int edge_freq = EDGE_FREQUENCY (e);
826
827           if (edge_freq > priority)
828             priority = edge_freq;
829         }
830     }
831
832   if (priority)
833     /* The block with priority should have significantly lower key.  */
834     return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency);
835   return -bb->frequency;
836 }
837
838 /* Return true when the edge E from basic block BB is better than the temporary
839    best edge (details are in function).  The probability of edge E is PROB. The
840    frequency of the successor is FREQ.  The current best probability is
841    BEST_PROB, the best frequency is BEST_FREQ.
842    The edge is considered to be equivalent when PROB does not differ much from
843    BEST_PROB; similarly for frequency.  */
844
845 static bool
846 better_edge_p (const_basic_block bb, const_edge e, int prob, int freq, int best_prob,
847                int best_freq, const_edge cur_best_edge)
848 {
849   bool is_better_edge;
850
851   /* The BEST_* values do not have to be best, but can be a bit smaller than
852      maximum values.  */
853   int diff_prob = best_prob / 10;
854   int diff_freq = best_freq / 10;
855
856   if (prob > best_prob + diff_prob)
857     /* The edge has higher probability than the temporary best edge.  */
858     is_better_edge = true;
859   else if (prob < best_prob - diff_prob)
860     /* The edge has lower probability than the temporary best edge.  */
861     is_better_edge = false;
862   else if (freq < best_freq - diff_freq)
863     /* The edge and the temporary best edge  have almost equivalent
864        probabilities.  The higher frequency of a successor now means
865        that there is another edge going into that successor.
866        This successor has lower frequency so it is better.  */
867     is_better_edge = true;
868   else if (freq > best_freq + diff_freq)
869     /* This successor has higher frequency so it is worse.  */
870     is_better_edge = false;
871   else if (e->dest->prev_bb == bb)
872     /* The edges have equivalent probabilities and the successors
873        have equivalent frequencies.  Select the previous successor.  */
874     is_better_edge = true;
875   else
876     is_better_edge = false;
877
878   /* If we are doing hot/cold partitioning, make sure that we always favor
879      non-crossing edges over crossing edges.  */
880
881   if (!is_better_edge
882       && flag_reorder_blocks_and_partition
883       && cur_best_edge
884       && (cur_best_edge->flags & EDGE_CROSSING)
885       && !(e->flags & EDGE_CROSSING))
886     is_better_edge = true;
887
888   return is_better_edge;
889 }
890
891 /* Connect traces in array TRACES, N_TRACES is the count of traces.  */
892
893 static void
894 connect_traces (int n_traces, struct trace *traces)
895 {
896   int i;
897   bool *connected;
898   bool two_passes;
899   int last_trace;
900   int current_pass;
901   int current_partition;
902   int freq_threshold;
903   gcov_type count_threshold;
904
905   freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000;
906   if (max_entry_count < INT_MAX / 1000)
907     count_threshold = max_entry_count * DUPLICATION_THRESHOLD / 1000;
908   else
909     count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD;
910
911   connected = XCNEWVEC (bool, n_traces);
912   last_trace = -1;
913   current_pass = 1;
914   current_partition = BB_PARTITION (traces[0].first);
915   two_passes = false;
916
917   if (flag_reorder_blocks_and_partition)
918     for (i = 0; i < n_traces && !two_passes; i++)
919       if (BB_PARTITION (traces[0].first)
920           != BB_PARTITION (traces[i].first))
921         two_passes = true;
922
923   for (i = 0; i < n_traces || (two_passes && current_pass == 1) ; i++)
924     {
925       int t = i;
926       int t2;
927       edge e, best;
928       int best_len;
929
930       if (i >= n_traces)
931         {
932           gcc_assert (two_passes && current_pass == 1);
933           i = 0;
934           t = i;
935           current_pass = 2;
936           if (current_partition == BB_HOT_PARTITION)
937             current_partition = BB_COLD_PARTITION;
938           else
939             current_partition = BB_HOT_PARTITION;
940         }
941
942       if (connected[t])
943         continue;
944
945       if (two_passes
946           && BB_PARTITION (traces[t].first) != current_partition)
947         continue;
948
949       connected[t] = true;
950
951       /* Find the predecessor traces.  */
952       for (t2 = t; t2 > 0;)
953         {
954           edge_iterator ei;
955           best = NULL;
956           best_len = 0;
957           FOR_EACH_EDGE (e, ei, traces[t2].first->preds)
958             {
959               int si = e->src->index;
960
961               if (e->src != ENTRY_BLOCK_PTR
962                   && (e->flags & EDGE_CAN_FALLTHRU)
963                   && !(e->flags & EDGE_COMPLEX)
964                   && bbd[si].end_of_trace >= 0
965                   && !connected[bbd[si].end_of_trace]
966                   && (BB_PARTITION (e->src) == current_partition)
967                   && (!best
968                       || e->probability > best->probability
969                       || (e->probability == best->probability
970                           && traces[bbd[si].end_of_trace].length > best_len)))
971                 {
972                   best = e;
973                   best_len = traces[bbd[si].end_of_trace].length;
974                 }
975             }
976           if (best)
977             {
978               best->src->aux = best->dest;
979               t2 = bbd[best->src->index].end_of_trace;
980               connected[t2] = true;
981
982               if (dump_file)
983                 {
984                   fprintf (dump_file, "Connection: %d %d\n",
985                            best->src->index, best->dest->index);
986                 }
987             }
988           else
989             break;
990         }
991
992       if (last_trace >= 0)
993         traces[last_trace].last->aux = traces[t2].first;
994       last_trace = t;
995
996       /* Find the successor traces.  */
997       while (1)
998         {
999           /* Find the continuation of the chain.  */
1000           edge_iterator ei;
1001           best = NULL;
1002           best_len = 0;
1003           FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1004             {
1005               int di = e->dest->index;
1006
1007               if (e->dest != EXIT_BLOCK_PTR
1008                   && (e->flags & EDGE_CAN_FALLTHRU)
1009                   && !(e->flags & EDGE_COMPLEX)
1010                   && bbd[di].start_of_trace >= 0
1011                   && !connected[bbd[di].start_of_trace]
1012                   && (BB_PARTITION (e->dest) == current_partition)
1013                   && (!best
1014                       || e->probability > best->probability
1015                       || (e->probability == best->probability
1016                           && traces[bbd[di].start_of_trace].length > best_len)))
1017                 {
1018                   best = e;
1019                   best_len = traces[bbd[di].start_of_trace].length;
1020                 }
1021             }
1022
1023           if (best)
1024             {
1025               if (dump_file)
1026                 {
1027                   fprintf (dump_file, "Connection: %d %d\n",
1028                            best->src->index, best->dest->index);
1029                 }
1030               t = bbd[best->dest->index].start_of_trace;
1031               traces[last_trace].last->aux = traces[t].first;
1032               connected[t] = true;
1033               last_trace = t;
1034             }
1035           else
1036             {
1037               /* Try to connect the traces by duplication of 1 block.  */
1038               edge e2;
1039               basic_block next_bb = NULL;
1040               bool try_copy = false;
1041
1042               FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1043                 if (e->dest != EXIT_BLOCK_PTR
1044                     && (e->flags & EDGE_CAN_FALLTHRU)
1045                     && !(e->flags & EDGE_COMPLEX)
1046                     && (!best || e->probability > best->probability))
1047                   {
1048                     edge_iterator ei;
1049                     edge best2 = NULL;
1050                     int best2_len = 0;
1051
1052                     /* If the destination is a start of a trace which is only
1053                        one block long, then no need to search the successor
1054                        blocks of the trace.  Accept it.  */
1055                     if (bbd[e->dest->index].start_of_trace >= 0
1056                         && traces[bbd[e->dest->index].start_of_trace].length
1057                            == 1)
1058                       {
1059                         best = e;
1060                         try_copy = true;
1061                         continue;
1062                       }
1063
1064                     FOR_EACH_EDGE (e2, ei, e->dest->succs)
1065                       {
1066                         int di = e2->dest->index;
1067
1068                         if (e2->dest == EXIT_BLOCK_PTR
1069                             || ((e2->flags & EDGE_CAN_FALLTHRU)
1070                                 && !(e2->flags & EDGE_COMPLEX)
1071                                 && bbd[di].start_of_trace >= 0
1072                                 && !connected[bbd[di].start_of_trace]
1073                                 && (BB_PARTITION (e2->dest) == current_partition)
1074                                 && (EDGE_FREQUENCY (e2) >= freq_threshold)
1075                                 && (e2->count >= count_threshold)
1076                                 && (!best2
1077                                     || e2->probability > best2->probability
1078                                     || (e2->probability == best2->probability
1079                                         && traces[bbd[di].start_of_trace].length
1080                                            > best2_len))))
1081                           {
1082                             best = e;
1083                             best2 = e2;
1084                             if (e2->dest != EXIT_BLOCK_PTR)
1085                               best2_len = traces[bbd[di].start_of_trace].length;
1086                             else
1087                               best2_len = INT_MAX;
1088                             next_bb = e2->dest;
1089                             try_copy = true;
1090                           }
1091                       }
1092                   }
1093
1094               if (flag_reorder_blocks_and_partition)
1095                 try_copy = false;
1096
1097               /* Copy tiny blocks always; copy larger blocks only when the
1098                  edge is traversed frequently enough.  */
1099               if (try_copy
1100                   && copy_bb_p (best->dest,
1101                                 optimize_edge_for_speed_p (best)
1102                                 && EDGE_FREQUENCY (best) >= freq_threshold
1103                                 && best->count >= count_threshold))
1104                 {
1105                   basic_block new_bb;
1106
1107                   if (dump_file)
1108                     {
1109                       fprintf (dump_file, "Connection: %d %d ",
1110                                traces[t].last->index, best->dest->index);
1111                       if (!next_bb)
1112                         fputc ('\n', dump_file);
1113                       else if (next_bb == EXIT_BLOCK_PTR)
1114                         fprintf (dump_file, "exit\n");
1115                       else
1116                         fprintf (dump_file, "%d\n", next_bb->index);
1117                     }
1118
1119                   new_bb = copy_bb (best->dest, best, traces[t].last, t);
1120                   traces[t].last = new_bb;
1121                   if (next_bb && next_bb != EXIT_BLOCK_PTR)
1122                     {
1123                       t = bbd[next_bb->index].start_of_trace;
1124                       traces[last_trace].last->aux = traces[t].first;
1125                       connected[t] = true;
1126                       last_trace = t;
1127                     }
1128                   else
1129                     break;      /* Stop finding the successor traces.  */
1130                 }
1131               else
1132                 break;  /* Stop finding the successor traces.  */
1133             }
1134         }
1135     }
1136
1137   if (dump_file)
1138     {
1139       basic_block bb;
1140
1141       fprintf (dump_file, "Final order:\n");
1142       for (bb = traces[0].first; bb; bb = (basic_block) bb->aux)
1143         fprintf (dump_file, "%d ", bb->index);
1144       fprintf (dump_file, "\n");
1145       fflush (dump_file);
1146     }
1147
1148   FREE (connected);
1149 }
1150
1151 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
1152    when code size is allowed to grow by duplication.  */
1153
1154 static bool
1155 copy_bb_p (const_basic_block bb, int code_may_grow)
1156 {
1157   int size = 0;
1158   int max_size = uncond_jump_length;
1159   rtx insn;
1160
1161   if (!bb->frequency)
1162     return false;
1163   if (EDGE_COUNT (bb->preds) < 2)
1164     return false;
1165   if (!can_duplicate_block_p (bb))
1166     return false;
1167
1168   /* Avoid duplicating blocks which have many successors (PR/13430).  */
1169   if (EDGE_COUNT (bb->succs) > 8)
1170     return false;
1171
1172   if (code_may_grow && optimize_bb_for_speed_p (bb))
1173     max_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS);
1174
1175   FOR_BB_INSNS (bb, insn)
1176     {
1177       if (INSN_P (insn))
1178         size += get_attr_min_length (insn);
1179     }
1180
1181   if (size <= max_size)
1182     return true;
1183
1184   if (dump_file)
1185     {
1186       fprintf (dump_file,
1187                "Block %d can't be copied because its size = %d.\n",
1188                bb->index, size);
1189     }
1190
1191   return false;
1192 }
1193
1194 /* Return the length of unconditional jump instruction.  */
1195
1196 static int
1197 get_uncond_jump_length (void)
1198 {
1199   rtx label, jump;
1200   int length;
1201
1202   label = emit_label_before (gen_label_rtx (), get_insns ());
1203   jump = emit_jump_insn (gen_jump (label));
1204
1205   length = get_attr_min_length (jump);
1206
1207   delete_insn (jump);
1208   delete_insn (label);
1209   return length;
1210 }
1211
1212 /* Emit a barrier into the footer of BB.  */
1213
1214 static void
1215 emit_barrier_after_bb (basic_block bb)
1216 {
1217   rtx barrier = emit_barrier_after (BB_END (bb));
1218   bb->il.rtl->footer = unlink_insn_chain (barrier, barrier);
1219 }
1220
1221 /* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions.
1222    Duplicate the landing pad and split the edges so that no EH edge
1223    crosses partitions.  */
1224
1225 static void
1226 fix_up_crossing_landing_pad (eh_landing_pad old_lp, basic_block old_bb)
1227 {
1228   eh_landing_pad new_lp;
1229   basic_block new_bb, last_bb, post_bb;
1230   rtx new_label, jump, post_label;
1231   unsigned new_partition;
1232   edge_iterator ei;
1233   edge e;
1234
1235   /* Generate the new landing-pad structure.  */
1236   new_lp = gen_eh_landing_pad (old_lp->region);
1237   new_lp->post_landing_pad = old_lp->post_landing_pad;
1238   new_lp->landing_pad = gen_label_rtx ();
1239   LABEL_PRESERVE_P (new_lp->landing_pad) = 1;
1240
1241   /* Put appropriate instructions in new bb.  */
1242   new_label = emit_label (new_lp->landing_pad);
1243
1244   expand_dw2_landing_pad_for_region (old_lp->region);
1245
1246   post_bb = BLOCK_FOR_INSN (old_lp->landing_pad);
1247   post_bb = single_succ (post_bb);
1248   post_label = block_label (post_bb);
1249   jump = emit_jump_insn (gen_jump (post_label));
1250   JUMP_LABEL (jump) = post_label;
1251
1252   /* Create new basic block to be dest for lp.  */
1253   last_bb = EXIT_BLOCK_PTR->prev_bb;
1254   new_bb = create_basic_block (new_label, jump, last_bb);
1255   new_bb->aux = last_bb->aux;
1256   last_bb->aux = new_bb;
1257
1258   emit_barrier_after_bb (new_bb);
1259
1260   make_edge (new_bb, post_bb, 0);
1261
1262   /* Make sure new bb is in the other partition.  */
1263   new_partition = BB_PARTITION (old_bb);
1264   new_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
1265   BB_SET_PARTITION (new_bb, new_partition);
1266
1267   /* Fix up the edges.  */
1268   for (ei = ei_start (old_bb->preds); (e = ei_safe_edge (ei)) != NULL; )
1269     if (BB_PARTITION (e->src) == new_partition)
1270       {
1271         rtx insn = BB_END (e->src);
1272         rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1273
1274         gcc_assert (note != NULL);
1275         gcc_checking_assert (INTVAL (XEXP (note, 0)) == old_lp->index);
1276         XEXP (note, 0) = GEN_INT (new_lp->index);
1277
1278         /* Adjust the edge to the new destination.  */
1279         redirect_edge_succ (e, new_bb);
1280       }
1281     else
1282       ei_next (&ei);
1283 }
1284
1285 /* Find the basic blocks that are rarely executed and need to be moved to
1286    a separate section of the .o file (to cut down on paging and improve
1287    cache locality).  Return a vector of all edges that cross.  */
1288
1289 static VEC(edge, heap) *
1290 find_rarely_executed_basic_blocks_and_crossing_edges (void)
1291 {
1292   VEC(edge, heap) *crossing_edges = NULL;
1293   basic_block bb;
1294   edge e;
1295   edge_iterator ei;
1296
1297   /* Mark which partition (hot/cold) each basic block belongs in.  */
1298   FOR_EACH_BB (bb)
1299     {
1300       if (probably_never_executed_bb_p (bb))
1301         BB_SET_PARTITION (bb, BB_COLD_PARTITION);
1302       else
1303         BB_SET_PARTITION (bb, BB_HOT_PARTITION);
1304     }
1305
1306   /* The format of .gcc_except_table does not allow landing pads to
1307      be in a different partition as the throw.  Fix this by either
1308      moving or duplicating the landing pads.  */
1309   if (cfun->eh->lp_array)
1310     {
1311       unsigned i;
1312       eh_landing_pad lp;
1313
1314       FOR_EACH_VEC_ELT (eh_landing_pad, cfun->eh->lp_array, i, lp)
1315         {
1316           bool all_same, all_diff;
1317
1318           if (lp == NULL
1319               || lp->landing_pad == NULL_RTX
1320               || !LABEL_P (lp->landing_pad))
1321             continue;
1322
1323           all_same = all_diff = true;
1324           bb = BLOCK_FOR_INSN (lp->landing_pad);
1325           FOR_EACH_EDGE (e, ei, bb->preds)
1326             {
1327               gcc_assert (e->flags & EDGE_EH);
1328               if (BB_PARTITION (bb) == BB_PARTITION (e->src))
1329                 all_diff = false;
1330               else
1331                 all_same = false;
1332             }
1333
1334           if (all_same)
1335             ;
1336           else if (all_diff)
1337             {
1338               int which = BB_PARTITION (bb);
1339               which ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
1340               BB_SET_PARTITION (bb, which);
1341             }
1342           else
1343             fix_up_crossing_landing_pad (lp, bb);
1344         }
1345     }
1346
1347   /* Mark every edge that crosses between sections.  */
1348
1349   FOR_EACH_BB (bb)
1350     FOR_EACH_EDGE (e, ei, bb->succs)
1351       {
1352         unsigned int flags = e->flags;
1353       
1354         /* We should never have EDGE_CROSSING set yet.  */
1355         gcc_checking_assert ((flags & EDGE_CROSSING) == 0);
1356
1357         if (e->src != ENTRY_BLOCK_PTR
1358             && e->dest != EXIT_BLOCK_PTR
1359             && BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1360           {
1361             VEC_safe_push (edge, heap, crossing_edges, e);
1362             flags |= EDGE_CROSSING;
1363           }
1364
1365         /* Now that we've split eh edges as appropriate, allow landing pads
1366            to be merged with the post-landing pads.  */
1367         flags &= ~EDGE_PRESERVE;
1368
1369         e->flags = flags;
1370       }
1371
1372   return crossing_edges;
1373 }
1374
1375 /* If any destination of a crossing edge does not have a label, add label;
1376    Convert any easy fall-through crossing edges to unconditional jumps.  */
1377
1378 static void
1379 add_labels_and_missing_jumps (VEC(edge, heap) *crossing_edges)
1380 {
1381   size_t i;
1382   edge e;
1383
1384   FOR_EACH_VEC_ELT (edge, crossing_edges, i, e)
1385     {
1386       basic_block src = e->src;
1387       basic_block dest = e->dest;
1388       rtx label, new_jump;
1389
1390       if (dest == EXIT_BLOCK_PTR)
1391         continue;
1392
1393       /* Make sure dest has a label.  */
1394       label = block_label (dest);
1395
1396       /* Nothing to do for non-fallthru edges.  */
1397       if (src == ENTRY_BLOCK_PTR)
1398         continue;
1399       if ((e->flags & EDGE_FALLTHRU) == 0)
1400         continue;
1401
1402       /* If the block does not end with a control flow insn, then we
1403          can trivially add a jump to the end to fixup the crossing.
1404          Otherwise the jump will have to go in a new bb, which will
1405          be handled by fix_up_fall_thru_edges function.  */
1406       if (control_flow_insn_p (BB_END (src)))
1407         continue;
1408
1409       /* Make sure there's only one successor.  */
1410       gcc_assert (single_succ_p (src));
1411
1412       new_jump = emit_jump_insn_after (gen_jump (label), BB_END (src));
1413       BB_END (src) = new_jump;
1414       JUMP_LABEL (new_jump) = label;
1415       LABEL_NUSES (label) += 1;
1416
1417       emit_barrier_after_bb (src);
1418
1419       /* Mark edge as non-fallthru.  */
1420       e->flags &= ~EDGE_FALLTHRU;
1421     }
1422 }
1423
1424 /* Find any bb's where the fall-through edge is a crossing edge (note that
1425    these bb's must also contain a conditional jump or end with a call
1426    instruction; we've already dealt with fall-through edges for blocks
1427    that didn't have a conditional jump or didn't end with call instruction
1428    in the call to add_labels_and_missing_jumps).  Convert the fall-through
1429    edge to non-crossing edge by inserting a new bb to fall-through into.
1430    The new bb will contain an unconditional jump (crossing edge) to the
1431    original fall through destination.  */
1432
1433 static void
1434 fix_up_fall_thru_edges (void)
1435 {
1436   basic_block cur_bb;
1437   basic_block new_bb;
1438   edge succ1;
1439   edge succ2;
1440   edge fall_thru;
1441   edge cond_jump = NULL;
1442   edge e;
1443   bool cond_jump_crosses;
1444   int invert_worked;
1445   rtx old_jump;
1446   rtx fall_thru_label;
1447
1448   FOR_EACH_BB (cur_bb)
1449     {
1450       fall_thru = NULL;
1451       if (EDGE_COUNT (cur_bb->succs) > 0)
1452         succ1 = EDGE_SUCC (cur_bb, 0);
1453       else
1454         succ1 = NULL;
1455
1456       if (EDGE_COUNT (cur_bb->succs) > 1)
1457         succ2 = EDGE_SUCC (cur_bb, 1);
1458       else
1459         succ2 = NULL;
1460
1461       /* Find the fall-through edge.  */
1462
1463       if (succ1
1464           && (succ1->flags & EDGE_FALLTHRU))
1465         {
1466           fall_thru = succ1;
1467           cond_jump = succ2;
1468         }
1469       else if (succ2
1470                && (succ2->flags & EDGE_FALLTHRU))
1471         {
1472           fall_thru = succ2;
1473           cond_jump = succ1;
1474         }
1475       else if (succ1
1476                && (block_ends_with_call_p (cur_bb)
1477                    || can_throw_internal (BB_END (cur_bb))))
1478         {
1479           edge e;
1480           edge_iterator ei;
1481
1482           /* Find EDGE_CAN_FALLTHRU edge.  */
1483           FOR_EACH_EDGE (e, ei, cur_bb->succs)
1484             if (e->flags & EDGE_CAN_FALLTHRU)
1485               {
1486                 fall_thru = e;
1487                 break;
1488               }
1489         }
1490
1491       if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR))
1492         {
1493           /* Check to see if the fall-thru edge is a crossing edge.  */
1494
1495           if (fall_thru->flags & EDGE_CROSSING)
1496             {
1497               /* The fall_thru edge crosses; now check the cond jump edge, if
1498                  it exists.  */
1499
1500               cond_jump_crosses = true;
1501               invert_worked  = 0;
1502               old_jump = BB_END (cur_bb);
1503
1504               /* Find the jump instruction, if there is one.  */
1505
1506               if (cond_jump)
1507                 {
1508                   if (!(cond_jump->flags & EDGE_CROSSING))
1509                     cond_jump_crosses = false;
1510
1511                   /* We know the fall-thru edge crosses; if the cond
1512                      jump edge does NOT cross, and its destination is the
1513                      next block in the bb order, invert the jump
1514                      (i.e. fix it so the fall thru does not cross and
1515                      the cond jump does).  */
1516
1517                   if (!cond_jump_crosses
1518                       && cur_bb->aux == cond_jump->dest)
1519                     {
1520                       /* Find label in fall_thru block. We've already added
1521                          any missing labels, so there must be one.  */
1522
1523                       fall_thru_label = block_label (fall_thru->dest);
1524
1525                       if (old_jump && JUMP_P (old_jump) && fall_thru_label)
1526                         invert_worked = invert_jump (old_jump,
1527                                                      fall_thru_label,0);
1528                       if (invert_worked)
1529                         {
1530                           fall_thru->flags &= ~EDGE_FALLTHRU;
1531                           cond_jump->flags |= EDGE_FALLTHRU;
1532                           update_br_prob_note (cur_bb);
1533                           e = fall_thru;
1534                           fall_thru = cond_jump;
1535                           cond_jump = e;
1536                           cond_jump->flags |= EDGE_CROSSING;
1537                           fall_thru->flags &= ~EDGE_CROSSING;
1538                         }
1539                     }
1540                 }
1541
1542               if (cond_jump_crosses || !invert_worked)
1543                 {
1544                   /* This is the case where both edges out of the basic
1545                      block are crossing edges. Here we will fix up the
1546                      fall through edge. The jump edge will be taken care
1547                      of later.  The EDGE_CROSSING flag of fall_thru edge
1548                      is unset before the call to force_nonfallthru
1549                      function because if a new basic-block is created
1550                      this edge remains in the current section boundary
1551                      while the edge between new_bb and the fall_thru->dest
1552                      becomes EDGE_CROSSING.  */
1553
1554                   fall_thru->flags &= ~EDGE_CROSSING;
1555                   new_bb = force_nonfallthru (fall_thru);
1556
1557                   if (new_bb)
1558                     {
1559                       new_bb->aux = cur_bb->aux;
1560                       cur_bb->aux = new_bb;
1561
1562                       /* Make sure new fall-through bb is in same
1563                          partition as bb it's falling through from.  */
1564
1565                       BB_COPY_PARTITION (new_bb, cur_bb);
1566                       single_succ_edge (new_bb)->flags |= EDGE_CROSSING;
1567                     }
1568                   else
1569                     {
1570                       /* If a new basic-block was not created; restore
1571                          the EDGE_CROSSING flag.  */
1572                       fall_thru->flags |= EDGE_CROSSING;
1573                     }
1574
1575                   /* Add barrier after new jump */
1576                   emit_barrier_after_bb (new_bb ? new_bb : cur_bb);
1577                 }
1578             }
1579         }
1580     }
1581 }
1582
1583 /* This function checks the destination block of a "crossing jump" to
1584    see if it has any crossing predecessors that begin with a code label
1585    and end with an unconditional jump.  If so, it returns that predecessor
1586    block.  (This is to avoid creating lots of new basic blocks that all
1587    contain unconditional jumps to the same destination).  */
1588
1589 static basic_block
1590 find_jump_block (basic_block jump_dest)
1591 {
1592   basic_block source_bb = NULL;
1593   edge e;
1594   rtx insn;
1595   edge_iterator ei;
1596
1597   FOR_EACH_EDGE (e, ei, jump_dest->preds)
1598     if (e->flags & EDGE_CROSSING)
1599       {
1600         basic_block src = e->src;
1601
1602         /* Check each predecessor to see if it has a label, and contains
1603            only one executable instruction, which is an unconditional jump.
1604            If so, we can use it.  */
1605
1606         if (LABEL_P (BB_HEAD (src)))
1607           for (insn = BB_HEAD (src);
1608                !INSN_P (insn) && insn != NEXT_INSN (BB_END (src));
1609                insn = NEXT_INSN (insn))
1610             {
1611               if (INSN_P (insn)
1612                   && insn == BB_END (src)
1613                   && JUMP_P (insn)
1614                   && !any_condjump_p (insn))
1615                 {
1616                   source_bb = src;
1617                   break;
1618                 }
1619             }
1620
1621         if (source_bb)
1622           break;
1623       }
1624
1625   return source_bb;
1626 }
1627
1628 /* Find all BB's with conditional jumps that are crossing edges;
1629    insert a new bb and make the conditional jump branch to the new
1630    bb instead (make the new bb same color so conditional branch won't
1631    be a 'crossing' edge).  Insert an unconditional jump from the
1632    new bb to the original destination of the conditional jump.  */
1633
1634 static void
1635 fix_crossing_conditional_branches (void)
1636 {
1637   basic_block cur_bb;
1638   basic_block new_bb;
1639   basic_block dest;
1640   edge succ1;
1641   edge succ2;
1642   edge crossing_edge;
1643   edge new_edge;
1644   rtx old_jump;
1645   rtx set_src;
1646   rtx old_label = NULL_RTX;
1647   rtx new_label;
1648
1649   FOR_EACH_BB (cur_bb)
1650     {
1651       crossing_edge = NULL;
1652       if (EDGE_COUNT (cur_bb->succs) > 0)
1653         succ1 = EDGE_SUCC (cur_bb, 0);
1654       else
1655         succ1 = NULL;
1656
1657       if (EDGE_COUNT (cur_bb->succs) > 1)
1658         succ2 = EDGE_SUCC (cur_bb, 1);
1659       else
1660         succ2 = NULL;
1661
1662       /* We already took care of fall-through edges, so only one successor
1663          can be a crossing edge.  */
1664
1665       if (succ1 && (succ1->flags & EDGE_CROSSING))
1666         crossing_edge = succ1;
1667       else if (succ2 && (succ2->flags & EDGE_CROSSING))
1668         crossing_edge = succ2;
1669
1670       if (crossing_edge)
1671         {
1672           old_jump = BB_END (cur_bb);
1673
1674           /* Check to make sure the jump instruction is a
1675              conditional jump.  */
1676
1677           set_src = NULL_RTX;
1678
1679           if (any_condjump_p (old_jump))
1680             {
1681               if (GET_CODE (PATTERN (old_jump)) == SET)
1682                 set_src = SET_SRC (PATTERN (old_jump));
1683               else if (GET_CODE (PATTERN (old_jump)) == PARALLEL)
1684                 {
1685                   set_src = XVECEXP (PATTERN (old_jump), 0,0);
1686                   if (GET_CODE (set_src) == SET)
1687                     set_src = SET_SRC (set_src);
1688                   else
1689                     set_src = NULL_RTX;
1690                 }
1691             }
1692
1693           if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE))
1694             {
1695               if (GET_CODE (XEXP (set_src, 1)) == PC)
1696                 old_label = XEXP (set_src, 2);
1697               else if (GET_CODE (XEXP (set_src, 2)) == PC)
1698                 old_label = XEXP (set_src, 1);
1699
1700               /* Check to see if new bb for jumping to that dest has
1701                  already been created; if so, use it; if not, create
1702                  a new one.  */
1703
1704               new_bb = find_jump_block (crossing_edge->dest);
1705
1706               if (new_bb)
1707                 new_label = block_label (new_bb);
1708               else
1709                 {
1710                   basic_block last_bb;
1711                   rtx new_jump;
1712
1713                   /* Create new basic block to be dest for
1714                      conditional jump.  */
1715
1716                   /* Put appropriate instructions in new bb.  */
1717
1718                   new_label = gen_label_rtx ();
1719                   emit_label (new_label);
1720
1721                   gcc_assert (GET_CODE (old_label) == LABEL_REF);
1722                   old_label = JUMP_LABEL (old_jump);
1723                   new_jump = emit_jump_insn (gen_jump (old_label));
1724                   JUMP_LABEL (new_jump) = old_label;
1725
1726                   last_bb = EXIT_BLOCK_PTR->prev_bb;
1727                   new_bb = create_basic_block (new_label, new_jump, last_bb);
1728                   new_bb->aux = last_bb->aux;
1729                   last_bb->aux = new_bb;
1730
1731                   emit_barrier_after_bb (new_bb);
1732
1733                   /* Make sure new bb is in same partition as source
1734                      of conditional branch.  */
1735                   BB_COPY_PARTITION (new_bb, cur_bb);
1736                 }
1737
1738               /* Make old jump branch to new bb.  */
1739
1740               redirect_jump (old_jump, new_label, 0);
1741
1742               /* Remove crossing_edge as predecessor of 'dest'.  */
1743
1744               dest = crossing_edge->dest;
1745
1746               redirect_edge_succ (crossing_edge, new_bb);
1747
1748               /* Make a new edge from new_bb to old dest; new edge
1749                  will be a successor for new_bb and a predecessor
1750                  for 'dest'.  */
1751
1752               if (EDGE_COUNT (new_bb->succs) == 0)
1753                 new_edge = make_edge (new_bb, dest, 0);
1754               else
1755                 new_edge = EDGE_SUCC (new_bb, 0);
1756
1757               crossing_edge->flags &= ~EDGE_CROSSING;
1758               new_edge->flags |= EDGE_CROSSING;
1759             }
1760         }
1761     }
1762 }
1763
1764 /* Find any unconditional branches that cross between hot and cold
1765    sections.  Convert them into indirect jumps instead.  */
1766
1767 static void
1768 fix_crossing_unconditional_branches (void)
1769 {
1770   basic_block cur_bb;
1771   rtx last_insn;
1772   rtx label;
1773   rtx label_addr;
1774   rtx indirect_jump_sequence;
1775   rtx jump_insn = NULL_RTX;
1776   rtx new_reg;
1777   rtx cur_insn;
1778   edge succ;
1779
1780   FOR_EACH_BB (cur_bb)
1781     {
1782       last_insn = BB_END (cur_bb);
1783
1784       if (EDGE_COUNT (cur_bb->succs) < 1)
1785         continue;
1786
1787       succ = EDGE_SUCC (cur_bb, 0);
1788
1789       /* Check to see if bb ends in a crossing (unconditional) jump.  At
1790          this point, no crossing jumps should be conditional.  */
1791
1792       if (JUMP_P (last_insn)
1793           && (succ->flags & EDGE_CROSSING))
1794         {
1795           rtx label2, table;
1796
1797           gcc_assert (!any_condjump_p (last_insn));
1798
1799           /* Make sure the jump is not already an indirect or table jump.  */
1800
1801           if (!computed_jump_p (last_insn)
1802               && !tablejump_p (last_insn, &label2, &table))
1803             {
1804               /* We have found a "crossing" unconditional branch.  Now
1805                  we must convert it to an indirect jump.  First create
1806                  reference of label, as target for jump.  */
1807
1808               label = JUMP_LABEL (last_insn);
1809               label_addr = gen_rtx_LABEL_REF (Pmode, label);
1810               LABEL_NUSES (label) += 1;
1811
1812               /* Get a register to use for the indirect jump.  */
1813
1814               new_reg = gen_reg_rtx (Pmode);
1815
1816               /* Generate indirect the jump sequence.  */
1817
1818               start_sequence ();
1819               emit_move_insn (new_reg, label_addr);
1820               emit_indirect_jump (new_reg);
1821               indirect_jump_sequence = get_insns ();
1822               end_sequence ();
1823
1824               /* Make sure every instruction in the new jump sequence has
1825                  its basic block set to be cur_bb.  */
1826
1827               for (cur_insn = indirect_jump_sequence; cur_insn;
1828                    cur_insn = NEXT_INSN (cur_insn))
1829                 {
1830                   if (!BARRIER_P (cur_insn))
1831                     BLOCK_FOR_INSN (cur_insn) = cur_bb;
1832                   if (JUMP_P (cur_insn))
1833                     jump_insn = cur_insn;
1834                 }
1835
1836               /* Insert the new (indirect) jump sequence immediately before
1837                  the unconditional jump, then delete the unconditional jump.  */
1838
1839               emit_insn_before (indirect_jump_sequence, last_insn);
1840               delete_insn (last_insn);
1841
1842               /* Make BB_END for cur_bb be the jump instruction (NOT the
1843                  barrier instruction at the end of the sequence...).  */
1844
1845               BB_END (cur_bb) = jump_insn;
1846             }
1847         }
1848     }
1849 }
1850
1851 /* Add REG_CROSSING_JUMP note to all crossing jump insns.  */
1852
1853 static void
1854 add_reg_crossing_jump_notes (void)
1855 {
1856   basic_block bb;
1857   edge e;
1858   edge_iterator ei;
1859
1860   FOR_EACH_BB (bb)
1861     FOR_EACH_EDGE (e, ei, bb->succs)
1862       if ((e->flags & EDGE_CROSSING)
1863           && JUMP_P (BB_END (e->src)))
1864         add_reg_note (BB_END (e->src), REG_CROSSING_JUMP, NULL_RTX);
1865 }
1866
1867 /* Verify, in the basic block chain, that there is at most one switch
1868    between hot/cold partitions. This is modelled on
1869    rtl_verify_flow_info_1, but it cannot go inside that function
1870    because this condition will not be true until after
1871    reorder_basic_blocks is called.  */
1872
1873 static void
1874 verify_hot_cold_block_grouping (void)
1875 {
1876   basic_block bb;
1877   int err = 0;
1878   bool switched_sections = false;
1879   int current_partition = 0;
1880
1881   FOR_EACH_BB (bb)
1882     {
1883       if (!current_partition)
1884         current_partition = BB_PARTITION (bb);
1885       if (BB_PARTITION (bb) != current_partition)
1886         {
1887           if (switched_sections)
1888             {
1889               error ("multiple hot/cold transitions found (bb %i)",
1890                      bb->index);
1891               err = 1;
1892             }
1893           else
1894             {
1895               switched_sections = true;
1896               current_partition = BB_PARTITION (bb);
1897             }
1898         }
1899     }
1900
1901   gcc_assert(!err);
1902 }
1903
1904 /* Reorder basic blocks.  The main entry point to this file.  FLAGS is
1905    the set of flags to pass to cfg_layout_initialize().  */
1906
1907 void
1908 reorder_basic_blocks (void)
1909 {
1910   int n_traces;
1911   int i;
1912   struct trace *traces;
1913
1914   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
1915
1916   if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
1917     return;
1918
1919   set_edge_can_fallthru_flag ();
1920   mark_dfs_back_edges ();
1921
1922   /* We are estimating the length of uncond jump insn only once since the code
1923      for getting the insn length always returns the minimal length now.  */
1924   if (uncond_jump_length == 0)
1925     uncond_jump_length = get_uncond_jump_length ();
1926
1927   /* We need to know some information for each basic block.  */
1928   array_size = GET_ARRAY_SIZE (last_basic_block);
1929   bbd = XNEWVEC (bbro_basic_block_data, array_size);
1930   for (i = 0; i < array_size; i++)
1931     {
1932       bbd[i].start_of_trace = -1;
1933       bbd[i].in_trace = -1;
1934       bbd[i].end_of_trace = -1;
1935       bbd[i].heap = NULL;
1936       bbd[i].node = NULL;
1937     }
1938
1939   traces = XNEWVEC (struct trace, n_basic_blocks);
1940   n_traces = 0;
1941   find_traces (&n_traces, traces);
1942   connect_traces (n_traces, traces);
1943   FREE (traces);
1944   FREE (bbd);
1945
1946   relink_block_chain (/*stay_in_cfglayout_mode=*/true);
1947
1948   if (dump_file)
1949     dump_flow_info (dump_file, dump_flags);
1950
1951   if (flag_reorder_blocks_and_partition)
1952     verify_hot_cold_block_grouping ();
1953 }
1954
1955 /* Determine which partition the first basic block in the function
1956    belongs to, then find the first basic block in the current function
1957    that belongs to a different section, and insert a
1958    NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
1959    instruction stream.  When writing out the assembly code,
1960    encountering this note will make the compiler switch between the
1961    hot and cold text sections.  */
1962
1963 static void
1964 insert_section_boundary_note (void)
1965 {
1966   basic_block bb;
1967   rtx new_note;
1968   int first_partition = 0;
1969
1970   if (!flag_reorder_blocks_and_partition)
1971     return;
1972
1973   FOR_EACH_BB (bb)
1974     {
1975       if (!first_partition)
1976         first_partition = BB_PARTITION (bb);
1977       if (BB_PARTITION (bb) != first_partition)
1978         {
1979           new_note = emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS,
1980                                        BB_HEAD (bb));
1981           /* ??? This kind of note always lives between basic blocks,
1982              but add_insn_before will set BLOCK_FOR_INSN anyway.  */
1983           BLOCK_FOR_INSN (new_note) = NULL;
1984           break;
1985         }
1986     }
1987 }
1988
1989 /* Duplicate the blocks containing computed gotos.  This basically unfactors
1990    computed gotos that were factored early on in the compilation process to
1991    speed up edge based data flow.  We used to not unfactoring them again,
1992    which can seriously pessimize code with many computed jumps in the source
1993    code, such as interpreters.  See e.g. PR15242.  */
1994
1995 static bool
1996 gate_duplicate_computed_gotos (void)
1997 {
1998   if (targetm.cannot_modify_jumps_p ())
1999     return false;
2000   return (optimize > 0
2001           && flag_expensive_optimizations
2002           && ! optimize_function_for_size_p (cfun));
2003 }
2004
2005
2006 static unsigned int
2007 duplicate_computed_gotos (void)
2008 {
2009   basic_block bb, new_bb;
2010   bitmap candidates;
2011   int max_size;
2012
2013   if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
2014     return 0;
2015
2016   cfg_layout_initialize (0);
2017
2018   /* We are estimating the length of uncond jump insn only once
2019      since the code for getting the insn length always returns
2020      the minimal length now.  */
2021   if (uncond_jump_length == 0)
2022     uncond_jump_length = get_uncond_jump_length ();
2023
2024   max_size = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS);
2025   candidates = BITMAP_ALLOC (NULL);
2026
2027   /* Look for blocks that end in a computed jump, and see if such blocks
2028      are suitable for unfactoring.  If a block is a candidate for unfactoring,
2029      mark it in the candidates.  */
2030   FOR_EACH_BB (bb)
2031     {
2032       rtx insn;
2033       edge e;
2034       edge_iterator ei;
2035       int size, all_flags;
2036
2037       /* Build the reorder chain for the original order of blocks.  */
2038       if (bb->next_bb != EXIT_BLOCK_PTR)
2039         bb->aux = bb->next_bb;
2040
2041       /* Obviously the block has to end in a computed jump.  */
2042       if (!computed_jump_p (BB_END (bb)))
2043         continue;
2044
2045       /* Only consider blocks that can be duplicated.  */
2046       if (find_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX)
2047           || !can_duplicate_block_p (bb))
2048         continue;
2049
2050       /* Make sure that the block is small enough.  */
2051       size = 0;
2052       FOR_BB_INSNS (bb, insn)
2053         if (INSN_P (insn))
2054           {
2055             size += get_attr_min_length (insn);
2056             if (size > max_size)
2057                break;
2058           }
2059       if (size > max_size)
2060         continue;
2061
2062       /* Final check: there must not be any incoming abnormal edges.  */
2063       all_flags = 0;
2064       FOR_EACH_EDGE (e, ei, bb->preds)
2065         all_flags |= e->flags;
2066       if (all_flags & EDGE_COMPLEX)
2067         continue;
2068
2069       bitmap_set_bit (candidates, bb->index);
2070     }
2071
2072   /* Nothing to do if there is no computed jump here.  */
2073   if (bitmap_empty_p (candidates))
2074     goto done;
2075
2076   /* Duplicate computed gotos.  */
2077   FOR_EACH_BB (bb)
2078     {
2079       if (bb->il.rtl->visited)
2080         continue;
2081
2082       bb->il.rtl->visited = 1;
2083
2084       /* BB must have one outgoing edge.  That edge must not lead to
2085          the exit block or the next block.
2086          The destination must have more than one predecessor.  */
2087       if (!single_succ_p (bb)
2088           || single_succ (bb) == EXIT_BLOCK_PTR
2089           || single_succ (bb) == bb->next_bb
2090           || single_pred_p (single_succ (bb)))
2091         continue;
2092
2093       /* The successor block has to be a duplication candidate.  */
2094       if (!bitmap_bit_p (candidates, single_succ (bb)->index))
2095         continue;
2096
2097       new_bb = duplicate_block (single_succ (bb), single_succ_edge (bb), bb);
2098       new_bb->aux = bb->aux;
2099       bb->aux = new_bb;
2100       new_bb->il.rtl->visited = 1;
2101     }
2102
2103 done:
2104   cfg_layout_finalize ();
2105
2106   BITMAP_FREE (candidates);
2107   return 0;
2108 }
2109
2110 struct rtl_opt_pass pass_duplicate_computed_gotos =
2111 {
2112  {
2113   RTL_PASS,
2114   "compgotos",                          /* name */
2115   gate_duplicate_computed_gotos,        /* gate */
2116   duplicate_computed_gotos,             /* execute */
2117   NULL,                                 /* sub */
2118   NULL,                                 /* next */
2119   0,                                    /* static_pass_number */
2120   TV_REORDER_BLOCKS,                    /* tv_id */
2121   0,                                    /* properties_required */
2122   0,                                    /* properties_provided */
2123   0,                                    /* properties_destroyed */
2124   0,                                    /* todo_flags_start */
2125   TODO_verify_rtl_sharing,/* todo_flags_finish */
2126  }
2127 };
2128
2129
2130 /* This function is the main 'entrance' for the optimization that
2131    partitions hot and cold basic blocks into separate sections of the
2132    .o file (to improve performance and cache locality).  Ideally it
2133    would be called after all optimizations that rearrange the CFG have
2134    been called.  However part of this optimization may introduce new
2135    register usage, so it must be called before register allocation has
2136    occurred.  This means that this optimization is actually called
2137    well before the optimization that reorders basic blocks (see
2138    function above).
2139
2140    This optimization checks the feedback information to determine
2141    which basic blocks are hot/cold, updates flags on the basic blocks
2142    to indicate which section they belong in.  This information is
2143    later used for writing out sections in the .o file.  Because hot
2144    and cold sections can be arbitrarily large (within the bounds of
2145    memory), far beyond the size of a single function, it is necessary
2146    to fix up all edges that cross section boundaries, to make sure the
2147    instructions used can actually span the required distance.  The
2148    fixes are described below.
2149
2150    Fall-through edges must be changed into jumps; it is not safe or
2151    legal to fall through across a section boundary.  Whenever a
2152    fall-through edge crossing a section boundary is encountered, a new
2153    basic block is inserted (in the same section as the fall-through
2154    source), and the fall through edge is redirected to the new basic
2155    block.  The new basic block contains an unconditional jump to the
2156    original fall-through target.  (If the unconditional jump is
2157    insufficient to cross section boundaries, that is dealt with a
2158    little later, see below).
2159
2160    In order to deal with architectures that have short conditional
2161    branches (which cannot span all of memory) we take any conditional
2162    jump that attempts to cross a section boundary and add a level of
2163    indirection: it becomes a conditional jump to a new basic block, in
2164    the same section.  The new basic block contains an unconditional
2165    jump to the original target, in the other section.
2166
2167    For those architectures whose unconditional branch is also
2168    incapable of reaching all of memory, those unconditional jumps are
2169    converted into indirect jumps, through a register.
2170
2171    IMPORTANT NOTE: This optimization causes some messy interactions
2172    with the cfg cleanup optimizations; those optimizations want to
2173    merge blocks wherever possible, and to collapse indirect jump
2174    sequences (change "A jumps to B jumps to C" directly into "A jumps
2175    to C").  Those optimizations can undo the jump fixes that
2176    partitioning is required to make (see above), in order to ensure
2177    that jumps attempting to cross section boundaries are really able
2178    to cover whatever distance the jump requires (on many architectures
2179    conditional or unconditional jumps are not able to reach all of
2180    memory).  Therefore tests have to be inserted into each such
2181    optimization to make sure that it does not undo stuff necessary to
2182    cross partition boundaries.  This would be much less of a problem
2183    if we could perform this optimization later in the compilation, but
2184    unfortunately the fact that we may need to create indirect jumps
2185    (through registers) requires that this optimization be performed
2186    before register allocation.
2187
2188    Hot and cold basic blocks are partitioned and put in separate
2189    sections of the .o file, to reduce paging and improve cache
2190    performance (hopefully).  This can result in bits of code from the
2191    same function being widely separated in the .o file.  However this
2192    is not obvious to the current bb structure.  Therefore we must take
2193    care to ensure that: 1). There are no fall_thru edges that cross
2194    between sections; 2). For those architectures which have "short"
2195    conditional branches, all conditional branches that attempt to
2196    cross between sections are converted to unconditional branches;
2197    and, 3). For those architectures which have "short" unconditional
2198    branches, all unconditional branches that attempt to cross between
2199    sections are converted to indirect jumps.
2200
2201    The code for fixing up fall_thru edges that cross between hot and
2202    cold basic blocks does so by creating new basic blocks containing
2203    unconditional branches to the appropriate label in the "other"
2204    section.  The new basic block is then put in the same (hot or cold)
2205    section as the original conditional branch, and the fall_thru edge
2206    is modified to fall into the new basic block instead.  By adding
2207    this level of indirection we end up with only unconditional branches
2208    crossing between hot and cold sections.
2209
2210    Conditional branches are dealt with by adding a level of indirection.
2211    A new basic block is added in the same (hot/cold) section as the
2212    conditional branch, and the conditional branch is retargeted to the
2213    new basic block.  The new basic block contains an unconditional branch
2214    to the original target of the conditional branch (in the other section).
2215
2216    Unconditional branches are dealt with by converting them into
2217    indirect jumps.  */
2218
2219 static unsigned
2220 partition_hot_cold_basic_blocks (void)
2221 {
2222   VEC(edge, heap) *crossing_edges;
2223
2224   if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
2225     return 0;
2226
2227   df_set_flags (DF_DEFER_INSN_RESCAN);
2228
2229   crossing_edges = find_rarely_executed_basic_blocks_and_crossing_edges ();
2230   if (crossing_edges == NULL)
2231     return 0;
2232
2233   /* Make sure the source of any crossing edge ends in a jump and the
2234      destination of any crossing edge has a label.  */
2235   add_labels_and_missing_jumps (crossing_edges);
2236
2237   /* Convert all crossing fall_thru edges to non-crossing fall
2238      thrus to unconditional jumps (that jump to the original fall
2239      thru dest).  */
2240   fix_up_fall_thru_edges ();
2241
2242   /* If the architecture does not have conditional branches that can
2243      span all of memory, convert crossing conditional branches into
2244      crossing unconditional branches.  */
2245   if (!HAS_LONG_COND_BRANCH)
2246     fix_crossing_conditional_branches ();
2247
2248   /* If the architecture does not have unconditional branches that
2249      can span all of memory, convert crossing unconditional branches
2250      into indirect jumps.  Since adding an indirect jump also adds
2251      a new register usage, update the register usage information as
2252      well.  */
2253   if (!HAS_LONG_UNCOND_BRANCH)
2254     fix_crossing_unconditional_branches ();
2255
2256   add_reg_crossing_jump_notes ();
2257
2258   VEC_free (edge, heap, crossing_edges);
2259
2260   /* ??? FIXME: DF generates the bb info for a block immediately.
2261      And by immediately, I mean *during* creation of the block.
2262
2263         #0  df_bb_refs_collect
2264         #1  in df_bb_refs_record
2265         #2  in create_basic_block_structure
2266
2267      Which means that the bb_has_eh_pred test in df_bb_refs_collect
2268      will *always* fail, because no edges can have been added to the
2269      block yet.  Which of course means we don't add the right 
2270      artificial refs, which means we fail df_verify (much) later.
2271
2272      Cleanest solution would seem to make DF_DEFER_INSN_RESCAN imply
2273      that we also shouldn't grab data from the new blocks those new
2274      insns are in either.  In this way one can create the block, link
2275      it up properly, and have everything Just Work later, when deferred
2276      insns are processed.
2277
2278      In the meantime, we have no other option but to throw away all
2279      of the DF data and recompute it all.  */
2280   if (cfun->eh->lp_array)
2281     {
2282       df_finish_pass (true);
2283       df_scan_alloc (NULL);
2284       df_scan_blocks ();
2285       /* Not all post-landing pads use all of the EH_RETURN_DATA_REGNO
2286          data.  We blindly generated all of them when creating the new
2287          landing pad.  Delete those assignments we don't use.  */
2288       df_set_flags (DF_LR_RUN_DCE);
2289       df_analyze ();
2290     }
2291
2292   return TODO_verify_flow | TODO_verify_rtl_sharing;
2293 }
2294 \f
2295 static bool
2296 gate_handle_reorder_blocks (void)
2297 {
2298   if (targetm.cannot_modify_jumps_p ())
2299     return false;
2300   /* Don't reorder blocks when optimizing for size because extra jump insns may
2301      be created; also barrier may create extra padding.
2302
2303      More correctly we should have a block reordering mode that tried to
2304      minimize the combined size of all the jumps.  This would more or less
2305      automatically remove extra jumps, but would also try to use more short
2306      jumps instead of long jumps.  */
2307   if (!optimize_function_for_speed_p (cfun))
2308     return false;
2309   return (optimize > 0
2310           && (flag_reorder_blocks || flag_reorder_blocks_and_partition));
2311 }
2312
2313
2314 /* Reorder basic blocks.  */
2315 static unsigned int
2316 rest_of_handle_reorder_blocks (void)
2317 {
2318   basic_block bb;
2319
2320   /* Last attempt to optimize CFG, as scheduling, peepholing and insn
2321      splitting possibly introduced more crossjumping opportunities.  */
2322   cfg_layout_initialize (CLEANUP_EXPENSIVE);
2323
2324   reorder_basic_blocks ();
2325   cleanup_cfg (CLEANUP_EXPENSIVE);
2326
2327   FOR_EACH_BB (bb)
2328     if (bb->next_bb != EXIT_BLOCK_PTR)
2329       bb->aux = bb->next_bb;
2330   cfg_layout_finalize ();
2331
2332   /* Add NOTE_INSN_SWITCH_TEXT_SECTIONS notes.  */
2333   insert_section_boundary_note ();
2334   return 0;
2335 }
2336
2337 struct rtl_opt_pass pass_reorder_blocks =
2338 {
2339  {
2340   RTL_PASS,
2341   "bbro",                               /* name */
2342   gate_handle_reorder_blocks,           /* gate */
2343   rest_of_handle_reorder_blocks,        /* execute */
2344   NULL,                                 /* sub */
2345   NULL,                                 /* next */
2346   0,                                    /* static_pass_number */
2347   TV_REORDER_BLOCKS,                    /* tv_id */
2348   0,                                    /* properties_required */
2349   0,                                    /* properties_provided */
2350   0,                                    /* properties_destroyed */
2351   0,                                    /* todo_flags_start */
2352   TODO_verify_rtl_sharing,              /* todo_flags_finish */
2353  }
2354 };
2355
2356 static bool
2357 gate_handle_partition_blocks (void)
2358 {
2359   /* The optimization to partition hot/cold basic blocks into separate
2360      sections of the .o file does not work well with linkonce or with
2361      user defined section attributes.  Don't call it if either case
2362      arises.  */
2363   return (flag_reorder_blocks_and_partition
2364           && optimize
2365           /* See gate_handle_reorder_blocks.  We should not partition if
2366              we are going to omit the reordering.  */
2367           && optimize_function_for_speed_p (cfun)
2368           && !DECL_ONE_ONLY (current_function_decl)
2369           && !user_defined_section_attribute);
2370 }
2371
2372 struct rtl_opt_pass pass_partition_blocks =
2373 {
2374  {
2375   RTL_PASS,
2376   "bbpart",                             /* name */
2377   gate_handle_partition_blocks,         /* gate */
2378   partition_hot_cold_basic_blocks,      /* execute */
2379   NULL,                                 /* sub */
2380   NULL,                                 /* next */
2381   0,                                    /* static_pass_number */
2382   TV_REORDER_BLOCKS,                    /* tv_id */
2383   PROP_cfglayout,                       /* properties_required */
2384   0,                                    /* properties_provided */
2385   0,                                    /* properties_destroyed */
2386   0,                                    /* todo_flags_start */
2387   0                                     /* todo_flags_finish */
2388  }
2389 };