OSDN Git Service

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