OSDN Git Service

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