#include "config.h"#include "system.h"#include "coretypes.h"#include "tm.h"#include "tree.h"#include "rtl.h"#include "regs.h"#include "flags.h"#include "output.h"#include "fibheap.h"#include "target.h"#include "function.h"#include "tm_p.h"#include "obstack.h"#include "expr.h"#include "params.h"#include "diagnostic-core.h"#include "toplev.h"#include "tree-pass.h"#include "df.h"#include "bb-reorder.h"#include "except.h"
Data Structures | |
| struct | bbro_basic_block_data_def |
| struct | trace |
Macros | |
| #define | N_ROUNDS 5 |
| #define | HAVE_return 0 |
| #define | gen_return() NULL_RTX |
| #define | uncond_jump_length (this_target_bb_reorder->x_uncond_jump_length) |
| #define | DUPLICATION_THRESHOLD 100 |
| #define | GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5) |
| #define | FREE(P) (gcc_assert (P), free (P), P = 0) |
Typedefs | |
| typedef struct bbro_basic_block_data_def | bbro_basic_block_data |
Variables | |
| struct target_bb_reorder | default_target_bb_reorder |
| static const int | branch_threshold [N_ROUNDS] = {400, 200, 100, 0, 0} |
| static const int | exec_threshold [N_ROUNDS] = {500, 200, 50, 0, 0} |
| static int | array_size |
| static bbro_basic_block_data * | bbd |
| static int | max_entry_frequency |
| static gcov_type | max_entry_count |
Macro Definition Documentation
| #define DUPLICATION_THRESHOLD 100 |
If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry block the edge destination is not duplicated while connecting traces.
| #define FREE | ( | P | ) | (gcc_assert (P), free (P), P = 0) |
Free the memory and set the pointer to NULL.
| #define gen_return | ( | ) | NULL_RTX |
| #define GET_ARRAY_SIZE | ( | X | ) | ((((X) / 4) + 1) * 5) |
To avoid frequent reallocation the size of arrays is greater than needed, the number of elements is (not less than) 1.25 * size_wanted.
| #define HAVE_return 0 |
Stubs in case we don't have a return insn. We have to check at run time too, not only compile time.
| #define N_ROUNDS 5 |
Basic block reordering routines for the GNU compiler. Copyright (C) 2000-2013 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/. This (greedy) algorithm constructs traces in several rounds. The construction starts from "seeds". The seed for the first round is the entry point of the function. When there are more than one seed, the one with the lowest key in the heap is selected first (see bb_to_key). Then the algorithm repeatedly adds the most probable successor to the end of a trace. Finally it connects the traces.
There are two parameters: Branch Threshold and Exec Threshold. If the probability of an edge to a successor of the current basic block is lower than Branch Threshold or its frequency is lower than Exec Threshold, then the successor will be the seed in one of the next rounds. Each round has these parameters lower than the previous one. The last round has to have these parameters set to zero so that the remaining blocks are picked up.
The algorithm selects the most probable successor from all unvisited successors and successors that have been added to this trace. The other successors (that has not been "sent" to the next round) will be other seeds for this round and the secondary traces will start from them. If the successor has not been visited in this trace, it is added to the trace (however, there is some heuristic for simple branches). If the successor has been visited in this trace, a loop has been found. If the loop has many iterations, the loop is rotated so that the source block of the most probable edge going out of the loop is the last block of the trace. If the loop has few iterations and there is no edge from the last block of the loop going out of the loop, the loop header is duplicated.
When connecting traces, the algorithm first checks whether there is an edge from the last block of a trace to the first block of another trace. When there are still some unconnected traces it checks whether there exists a basic block BB such that BB is a successor of the last block of a trace and BB is a predecessor of the first block of another trace. In this case, BB is duplicated, added at the end of the first trace and the traces are connected through it. The rest of traces are simply connected so there will be a jump to the beginning of the rest of traces.
The above description is for the full algorithm, which is used when the function is optimized for speed. When the function is optimized for size, in order to reduce long jumps and connect more fallthru edges, the algorithm is modified as follows: (1) Break long traces to short ones. A trace is broken at a block that has multiple predecessors/ successors during trace discovery. When connecting traces, only connect Trace n with Trace n + 1. This change reduces most long jumps compared with the above algorithm. (2) Ignore the edge probability and frequency for fallthru edges. (3) Keep the original order of blocks when there is no chance to fall through. We rely on the results of cfg_cleanup.
To implement the change for code size optimization, block's index is selected as the key and all traces are found in one round.
References:
"Software Trace Cache" A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999 http://citeseer.nj.nec.com/15361.html The number of rounds. In most cases there will only be 4 rounds, but when partitioning hot and cold basic blocks into separate sections of the object file there will be an extra round.
| #define uncond_jump_length (this_target_bb_reorder->x_uncond_jump_length) |
Referenced by reorder_basic_blocks().
Typedef Documentation
| typedef struct bbro_basic_block_data_def bbro_basic_block_data |
Structure to hold needed information for each basic block.
Function Documentation
|
static |
If any destination of a crossing edge does not have a label, add label; Convert any easy fall-through crossing edges to unconditional jumps.
Make sure dest has a label.
Nothing to do for non-fallthru edges.
If the block does not end with a control flow insn, then we
can trivially add a jump to the end to fixup the crossing.
Otherwise the jump will have to go in a new bb, which will
be handled by fix_up_fall_thru_edges function. Make sure there's only one successor.
Mark edge as non-fallthru.
References block_label(), edge_def::dest, edge_def::flags, invert_jump(), JUMP_P, and update_br_prob_note().
Referenced by duplicate_computed_gotos().
|
static |
Add REG_CROSSING_JUMP note to all crossing jump insns.
Some notes were added during fix_up_fall_thru_edges, via force_nonfallthru_and_redirect.
Referenced by duplicate_computed_gotos().
|
static |
Referenced by find_traces_1_round().
|
static |
Compute and return the key (for the heap) of the basic block BB.
Use index as key to align with its original order.
Do not start in probably never executed blocks.
Prefer blocks whose predecessor is an end of some trace or whose predecessor edge is EDGE_DFS_BACK.
The block with priority should have significantly lower key.
|
static |
Return the trace number in which BB was visited.
Referenced by find_traces_1_round().
|
static |
Return true when the edge E from basic block BB is better than the temporary best edge (details are in function). The probability of edge E is PROB. The frequency of the successor is FREQ. The current best probability is BEST_PROB, the best frequency is BEST_FREQ. The edge is considered to be equivalent when PROB does not differ much from BEST_PROB; similarly for frequency.
The BEST_* values do not have to be best, but can be a bit smaller than maximum values.
The smaller one is better to keep the original order.
The edge has higher probability than the temporary best edge.
The edge has lower probability than the temporary best edge.
The edge and the temporary best edge have almost equivalent probabilities. The higher frequency of a successor now means that there is another edge going into that successor. This successor has lower frequency so it is better.
This successor has higher frequency so it is worse.
The edges have equivalent probabilities and the successors have equivalent frequencies. Select the previous successor.
If we are doing hot/cold partitioning, make sure that we always favor non-crossing edges over crossing edges.
References edge_def::dest, basic_block_def::index, and edge_def::src.
Referenced by find_traces_1_round().
|
static |
Return true when the edge E is better than the temporary best edge CUR_BEST_EDGE. If SRC_INDEX_P is true, the function compares the src bb of E and CUR_BEST_EDGE; otherwise it will compare the dest bb. BEST_LEN is the trace length of src (or dest) bb in CUR_BEST_EDGE. TRACES record the information about traces. When optimizing for size, the edge with smaller index is better. When optimizing for speed, the edge with bigger probability or longer trace is better.
The smaller one is better to keep the original order.
The edge has higher probability than the temporary best edge.
The edge has lower probability than the temporary best edge.
The edge and the temporary best edge have equivalent probabilities.
The edge with longer trace is better. The edge has higher probability than the temporary best edge.
The edge has lower probability than the temporary best edge.
The edge and the temporary best edge have equivalent probabilities.
The edge with longer trace is better.
|
static |
|
static |
Connect traces in array TRACES, N_TRACES is the count of traces.
Find the predecessor traces.
Find the successor traces.
Find the continuation of the chain.
Stop finding the successor traces.
It is OK to connect block n with block n + 1 or a block
before n. For others, only connect to the loop header. If dest has multiple predecessors, skip it. We expect
that one predecessor with smaller index connects with it
later. Only connect Trace n with Trace n + 1. It is conservative
to keep the order as close as possible to the original order.
It also helps to reduce long jumps. Try to connect the traces by duplication of 1 block.
If the destination is a start of a trace which is only
one block long, then no need to search the successor
blocks of the trace. Accept it. Copy tiny blocks always; copy larger blocks only when the
edge is traversed frequently enough.
References edge_def::dest, dump_file, basic_block_def::index, and edge_def::src.
|
static |
Referenced by find_traces_1_round().
|
static |
Create a duplicate of the basic block OLD_BB and redirect edge E to it, add it to trace after BB, mark OLD_BB visited and update pass' data structures (TRACE is a number of trace which OLD_BB is duplicated to).
References EDGE_FREQUENCY, bbro_basic_block_data_def::end_of_trace, ENTRY_BLOCK_PTR, edge_def::flags, basic_block_def::index, and edge_def::src.
|
static |
Referenced by find_traces_1_round().
|
static |
Return true when BB can and should be copied. CODE_MAY_GROW is true when code size is allowed to grow by duplication.
Avoid duplicating blocks which have many successors (PR/13430).
|
static |
We are estimating the length of uncond jump insn only once since the code for getting the insn length always returns the minimal length now.
Look for blocks that end in a computed jump, and see if such blocks are suitable for unfactoring. If a block is a candidate for unfactoring, mark it in the candidates.
Build the reorder chain for the original order of blocks.
Obviously the block has to end in a computed jump.
Only consider blocks that can be duplicated.
Make sure that the block is small enough.
Final check: there must not be any incoming abnormal edges.
Nothing to do if there is no computed jump here.
Duplicate computed gotos.
BB must have one outgoing edge. That edge must not lead to
the exit block or the next block.
The destination must have more than one predecessor. The successor block has to be a duplication candidate.
Don't duplicate a partition crossing edge, which requires difficult
fixup.
References add_labels_and_missing_jumps(), add_reg_crossing_jump_notes(), cfun, clear_aux_for_blocks(), crtl, df_analyze(), DF_DEFER_INSN_RESCAN, df_finish_pass(), DF_LR_RUN_DCE, df_scan_alloc(), df_scan_blocks(), df_set_flags(), find_rarely_executed_basic_blocks_and_crossing_edges(), fix_crossing_conditional_branches(), fix_crossing_unconditional_branches(), fix_up_fall_thru_edges(), HAS_LONG_COND_BRANCH, HAS_LONG_UNCOND_BRANCH, n_basic_blocks, NULL, and NUM_FIXED_BLOCKS.
|
static |
This function checks the destination block of a "crossing jump" to see if it has any crossing predecessors that begin with a code label and end with an unconditional jump. If so, it returns that predecessor block. (This is to avoid creating lots of new basic blocks that all contain unconditional jumps to the same destination).
Check each predecessor to see if it has a label, and contains only one executable instruction, which is an unconditional jump. If so, we can use it.
Find the basic blocks that are rarely executed and need to be moved to a separate section of the .o file (to cut down on paging and improve cache locality). Return a vector of all edges that cross.
Mark which partition (hot/cold) each basic block belongs in.
Handle profile insanities created by upstream optimizations
by also checking the incoming edge weights. If there is a non-cold
incoming edge, conservatively prevent this block from being split
into the cold section. Ensure that hot bbs are included along a hot path from the entry to exit. Several different possibilities may include cold bbs along all paths to/from a hot bb. One is that there are edge weight insanities due to optimization phases that do not properly update basic block profile counts. The second is that the entry of the function may not be hot, because it is entered fewer times than the number of profile training runs, but there is a loop inside the function that causes blocks within the function to be above the threshold for hotness. This is fixed by walking up from hot bbs to the entry block, and then down from hot bbs to the exit, performing partitioning fixups as necessary.
The format of .gcc_except_table does not allow landing pads to be in a different partition as the throw. Fix this by either moving or duplicating the landing pads.
Mark every edge that crosses between sections.
We should never have EDGE_CROSSING set yet.
Now that we've split eh edges as appropriate, allow landing pads
to be merged with the post-landing pads.
Referenced by duplicate_computed_gotos().
|
static |
Local function prototypes.
|
static |
Find the traces for Software Trace Cache. Chain each trace through RBI()->next. Store the number of traces to N_TRACES and description of traces to TRACES.
Add one extra round of trace collection when partitioning hot/cold basic blocks into separate sections. The last round is for all the cold blocks (and ONLY the cold blocks).
Insert entry points of function into heap.
Find the traces.
References branch_threshold, dump_file, exec_threshold, find_traces_1_round(), INT_MAX, max_entry_count, max_entry_frequency, and REG_BR_PROB_BASE.
|
static |
One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do not include basic blocks whose probability is lower than BRANCH_TH or whose frequency is lower than EXEC_TH into traces (or whose count is lower than COUNT_TH). Store the new traces into TRACES and modify the number of traces *N_TRACES. Set the round (which the trace belongs to) to ROUND. The function expects starting basic blocks to be in *HEAP and will delete *HEAP and store starting points for the next round into new *HEAP.
Heap for discarded basic blocks which are possible starting points for the next round.
If the BB's frequency is too low, send BB to the next round. When
partitioning hot/cold blocks into separate sections, make sure all
the cold blocks (and ONLY the cold blocks) go into the (extra) final
round. When optimizing for size, do not push to next round. The probability and frequency of the best edge.
Select the successor that will be placed after BB.
The only sensible preference for a call instruction is the
fallthru edge. Don't bother selecting anything else. Edge that cannot be fallthru or improbable or infrequent
successor (i.e. it is unsuitable successor). When optimizing
for size, ignore the probability and frequency. If partitioning hot/cold basic blocks, don't consider edges
that cross section boundaries. If the best destination has multiple predecessors, and can be
duplicated cheaper than a jump, don't allow it to be added
to a trace. We'll duplicate it when connecting traces. If the best destination has multiple successors or predecessors,
don't allow it to be added when optimizing for size. This makes
sure predecessors with smaller index are handled before the best
destinarion. It breaks long trace and reduces long jumps.
Take if-then-else as an example.
A
/ \
B C
\ /
D
If we do not remove the best edge B->D/C->D, the final order might
be A B D ... C. C is at the end of the program. If D's successors
and D are complicated, might need long jumps for A->C and C->D.
Similar issue for order: A C D ... B.
After removing the best edge, the final result will be ABCD/ ACBD.
It does not add jump compared with the previous order. But it
reduces the possibility of long jumps. Add all non-selected successors to the heaps.
E->DEST is already in some heap.
When partitioning hot/cold basic blocks, make sure
the cold blocks (and only the cold blocks) all get
pushed to the last round of trace collection. When
optimizing for size, do not push to next round. We do nothing with one basic block loops.
The loop has at least 4 iterations. If the loop
header is not the first block of the function
we can rotate the loop. The loop has less than 4 iterations.
Terminate the trace.
Check for a situation
A
/|
B |
\|
C
where
EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
>= EDGE_FREQUENCY (AC).
(i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
Best ordering is then A B C.
When optimizing for size, A B C is always the best order.
This situation is created for example by:
if (A) B;
C; The trace is terminated so we have to recount the keys in heap
(some block can have a lower key because now one of its predecessors
is an end of the trace). "Return" the new heap.
References basic_block_def::aux, BB_PARTITION, bb_to_key(), bb_visited_trace(), better_edge_p(), block_ends_with_call_p(), copy_bb(), copy_bb_p(), edge_def::count, edge_def::dest, dump_file, EDGE_COUNT, EDGE_FREQUENCY, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, edge_def::flags, FOR_EACH_EDGE, basic_block_def::frequency, gcc_assert, bbro_basic_block_data_def::heap, bbro_basic_block_data_def::in_trace, basic_block_def::index, INT_MIN, trace::length, mark_bb_visited(), bbro_basic_block_data_def::node, NULL, optimize_edge_for_speed_p(), basic_block_def::preds, edge_def::probability, push_to_next_round_p(), rotate_loop(), single_pred_p(), single_succ(), single_succ_edge(), single_succ_p(), and basic_block_def::succs.
Referenced by find_traces().
|
static |
Find all BB's with conditional jumps that are crossing edges; insert a new bb and make the conditional jump branch to the new bb instead (make the new bb same color so conditional branch won't be a 'crossing' edge). Insert an unconditional jump from the new bb to the original destination of the conditional jump.
We already took care of fall-through edges, so only one successor
can be a crossing edge.
Check to make sure the jump instruction is a
conditional jump. Check to see if new bb for jumping to that dest has
already been created; if so, use it; if not, create
a new one. Create new basic block to be dest for
conditional jump. Put appropriate instructions in new bb.
Make sure new bb is in same partition as source
of conditional branch. Make old jump branch to new bb.
Remove crossing_edge as predecessor of 'dest'.
Make a new edge from new_bb to old dest; new edge
will be a successor for new_bb and a predecessor
for 'dest'.
Referenced by duplicate_computed_gotos().
|
static |
Find any unconditional branches that cross between hot and cold sections. Convert them into indirect jumps instead.
Check to see if bb ends in a crossing (unconditional) jump. At
this point, no crossing jumps should be conditional.
Make sure the jump is not already an indirect or table jump.
We have found a "crossing" unconditional branch. Now
we must convert it to an indirect jump. First create
reference of label, as target for jump. Get a register to use for the indirect jump.
Generate indirect the jump sequence.
Make sure every instruction in the new jump sequence has
its basic block set to be cur_bb. Insert the new (indirect) jump sequence immediately before
the unconditional jump, then delete the unconditional jump. Make BB_END for cur_bb be the jump instruction (NOT the
barrier instruction at the end of the sequence...).
References BB_HEAD, BB_PARTITION, crtl, emit_note_before(), FOR_EACH_BB, and gcc_assert.
Referenced by duplicate_computed_gotos().
|
static |
The landing pad OLD_LP, in block OLD_BB, has edges from both partitions. Duplicate the landing pad and split the edges so that no EH edge crosses partitions.
Generate the new landing-pad structure.
Put appropriate instructions in new bb.
Create new basic block to be dest for lp.
Make sure new bb is in the other partition.
Fix up the edges.
Adjust the edge to the new destination.
|
static |
Find any bb's where the fall-through edge is a crossing edge (note that these bb's must also contain a conditional jump or end with a call instruction; we've already dealt with fall-through edges for blocks that didn't have a conditional jump or didn't end with call instruction in the call to add_labels_and_missing_jumps). Convert the fall-through edge to non-crossing edge by inserting a new bb to fall-through into. The new bb will contain an unconditional jump (crossing edge) to the original fall through destination.
Find the fall-through edge.
Find EDGE_CAN_FALLTHRU edge.
Check to see if the fall-thru edge is a crossing edge.
The fall_thru edge crosses; now check the cond jump edge, if
it exists. Find the jump instruction, if there is one.
We know the fall-thru edge crosses; if the cond
jump edge does NOT cross, and its destination is the
next block in the bb order, invert the jump
(i.e. fix it so the fall through does not cross and
the cond jump does). Find label in fall_thru block. We've already added
any missing labels, so there must be one. This is the case where both edges out of the basic
block are crossing edges. Here we will fix up the
fall through edge. The jump edge will be taken care
of later. The EDGE_CROSSING flag of fall_thru edge
is unset before the call to force_nonfallthru
function because if a new basic-block is created
this edge remains in the current section boundary
while the edge between new_bb and the fall_thru->dest
becomes EDGE_CROSSING. This is done by force_nonfallthru_and_redirect.
If a new basic-block was not created; restore
the EDGE_CROSSING flag. Add barrier after new jump
References edge_def::flags.
Referenced by duplicate_computed_gotos().
|
static |
Duplicate the blocks containing computed gotos. This basically unfactors computed gotos that were factored early on in the compilation process to speed up edge based data flow. We used to not unfactoring them again, which can seriously pessimize code with many computed jumps in the source code, such as interpreters. See e.g. PR15242.
|
static |
The optimization to partition hot/cold basic blocks into separate sections of the .o file does not work well with linkonce or with user defined section attributes. Don't call it if either case arises.
See gate_handle_reorder_blocks. We should not partition if
we are going to omit the reordering.
References OPTGROUP_NONE, PROP_cfglayout, and RTL_PASS.
|
static |
| int get_uncond_jump_length | ( | void | ) |
Return the length of unconditional jump instruction.
References BB_PARTITION, edge_def::dest, edge_def::flags, FOR_EACH_EDGE, basic_block_def::preds, edge_def::src, and basic_block_def::succs.
Referenced by reorder_basic_blocks().
| void insert_section_boundary_note | ( | void | ) |
Determine which partition the first basic block in the function belongs to, then find the first basic block in the current function that belongs to a different section, and insert a NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the instruction stream. When writing out the assembly code, encountering this note will make the compiler switch between the hot and cold text sections.
Referenced by compute_bb_for_insn().
| rtl_opt_pass* make_pass_duplicate_computed_gotos | ( | ) |
| rtl_opt_pass* make_pass_partition_blocks | ( | ) |
| rtl_opt_pass* make_pass_reorder_blocks | ( | ) |
|
static |
Referenced by find_traces_1_round().
|
static |
This function marks BB that it was visited in trace number TRACE.
|
static |
This function is the main 'entrance' for the optimization that partitions hot and cold basic blocks into separate sections of the .o file (to improve performance and cache locality). Ideally it would be called after all optimizations that rearrange the CFG have been called. However part of this optimization may introduce new register usage, so it must be called before register allocation has occurred. This means that this optimization is actually called well before the optimization that reorders basic blocks (see function above).
This optimization checks the feedback information to determine which basic blocks are hot/cold, updates flags on the basic blocks to indicate which section they belong in. This information is later used for writing out sections in the .o file. Because hot and cold sections can be arbitrarily large (within the bounds of memory), far beyond the size of a single function, it is necessary to fix up all edges that cross section boundaries, to make sure the instructions used can actually span the required distance. The fixes are described below.
Fall-through edges must be changed into jumps; it is not safe or legal to fall through across a section boundary. Whenever a fall-through edge crossing a section boundary is encountered, a new basic block is inserted (in the same section as the fall-through source), and the fall through edge is redirected to the new basic block. The new basic block contains an unconditional jump to the original fall-through target. (If the unconditional jump is insufficient to cross section boundaries, that is dealt with a little later, see below).
In order to deal with architectures that have short conditional branches (which cannot span all of memory) we take any conditional jump that attempts to cross a section boundary and add a level of indirection: it becomes a conditional jump to a new basic block, in the same section. The new basic block contains an unconditional jump to the original target, in the other section.
For those architectures whose unconditional branch is also incapable of reaching all of memory, those unconditional jumps are converted into indirect jumps, through a register.
IMPORTANT NOTE: This optimization causes some messy interactions with the cfg cleanup optimizations; those optimizations want to merge blocks wherever possible, and to collapse indirect jump sequences (change "A jumps to B jumps to C" directly into "A jumps to C"). Those optimizations can undo the jump fixes that partitioning is required to make (see above), in order to ensure that jumps attempting to cross section boundaries are really able to cover whatever distance the jump requires (on many architectures conditional or unconditional jumps are not able to reach all of memory). Therefore tests have to be inserted into each such optimization to make sure that it does not undo stuff necessary to cross partition boundaries. This would be much less of a problem if we could perform this optimization later in the compilation, but unfortunately the fact that we may need to create indirect jumps (through registers) requires that this optimization be performed before register allocation.
Hot and cold basic blocks are partitioned and put in separate sections of the .o file, to reduce paging and improve cache performance (hopefully). This can result in bits of code from the same function being widely separated in the .o file. However this is not obvious to the current bb structure. Therefore we must take care to ensure that: 1). There are no fall_thru edges that cross between sections; 2). For those architectures which have "short" conditional branches, all conditional branches that attempt to cross between sections are converted to unconditional branches; and, 3). For those architectures which have "short" unconditional branches, all unconditional branches that attempt to cross between sections are converted to indirect jumps.
The code for fixing up fall_thru edges that cross between hot and cold basic blocks does so by creating new basic blocks containing unconditional branches to the appropriate label in the "other" section. The new basic block is then put in the same (hot or cold) section as the original conditional branch, and the fall_thru edge is modified to fall into the new basic block instead. By adding this level of indirection we end up with only unconditional branches crossing between hot and cold sections.
Conditional branches are dealt with by adding a level of indirection. A new basic block is added in the same (hot/cold) section as the conditional branch, and the conditional branch is retargeted to the new basic block. The new basic block contains an unconditional branch to the original target of the conditional branch (in the other section).
Unconditional branches are dealt with by converting them into indirect jumps.
Make sure the source of any crossing edge ends in a jump and the destination of any crossing edge has a label.
Convert all crossing fall_thru edges to non-crossing fall thrus to unconditional jumps (that jump to the original fall through dest).
If the architecture does not have conditional branches that can span all of memory, convert crossing conditional branches into crossing unconditional branches.
If the architecture does not have unconditional branches that can span all of memory, convert crossing unconditional branches into indirect jumps. Since adding an indirect jump also adds a new register usage, update the register usage information as well.
Clear bb->aux fields that the above routines were using.
??? FIXME: DF generates the bb info for a block immediately.
And by immediately, I mean *during* creation of the block.
#0 df_bb_refs_collect
#1 in df_bb_refs_record
#2 in create_basic_block_structure
Which means that the bb_has_eh_pred test in df_bb_refs_collect
will *always* fail, because no edges can have been added to the
block yet. Which of course means we don't add the right
artificial refs, which means we fail df_verify (much) later.
Cleanest solution would seem to make DF_DEFER_INSN_RESCAN imply
that we also shouldn't grab data from the new blocks those new
insns are in either. In this way one can create the block, link
it up properly, and have everything Just Work later, when deferred
insns are processed.
In the meantime, we have no other option but to throw away all
of the DF data and recompute it all. Not all post-landing pads use all of the EH_RETURN_DATA_REGNO
data. We blindly generated all of them when creating the new
landing pad. Delete those assignments we don't use.
|
static |
Check to see if bb should be pushed into the next round of trace collections or not. Reasons for pushing the block forward are 1). If the block is cold, we are doing partitioning, and there will be another round (cold partition blocks are not supposed to be collected into traces until the very last round); or 2). There will be another round, and the basic block is not "hot enough" for the current round of trace collection.
Referenced by find_traces_1_round().
|
static |
Reorder basic blocks. The main entry point to this file. FLAGS is the set of flags to pass to cfg_layout_initialize().
We are estimating the length of uncond jump insn only once since the code for getting the insn length always returns the minimal length now.
We need to know some information for each basic block.
Signal that rtl_verify_flow_info_1 can now verify that there is at most one switch between hot/cold sections.
References basic_block_def::aux, BB_END, BITMAP_ALLOC, can_duplicate_block_p(), candidates, cfg_layout_initialize(), clear_bb_flags(), computed_jump_p(), EXIT_BLOCK_PTR, find_reg_note(), edge_def::flags, FOR_BB_INSNS, FOR_EACH_BB, FOR_EACH_EDGE, get_attr_min_length(), get_uncond_jump_length(), INSN_P, n_basic_blocks, basic_block_def::next_bb, NULL, NUM_FIXED_BLOCKS, PARAM_VALUE, basic_block_def::preds, and uncond_jump_length.
|
static |
Last attempt to optimize CFG, as scheduling, peepholing and insn splitting possibly introduced more crossjumping opportunities.
|
static |
Referenced by find_traces_1_round().
|
static |
Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE (with sequential number TRACE_N).
Information about the best end (end after rotation) of the loop.
The best edge is preferred when its destination is not visited yet or is a start block of some trace.
Find the most frequent edge that goes out from current trace.
The best edge is preferred.
The current edge E is also preferred.
The current edge E is preferred.
Rotate the loop so that the BEST_EDGE goes out from the last block of
the trace. Try to get rid of uncond jump to cond jump.
Duplicate HEADER if it is a small block containing cond jump
in the end. We have not found suitable loop tail so do no rotation.
|
static |
Ensure that all hot bbs are included in a hot path through the procedure. This is done by calling this function twice, once with WALK_UP true (to look for paths from the entry to hot bbs) and once with WALK_UP false (to look for paths from hot bbs to the exit). Returns the updated value of COLD_BB_COUNT and adds newly-hot bbs to BBS_IN_HOT_PARTITION.
Callers check this.
Keep examining hot bbs while we still have some left to check and there are remaining cold bbs.
Walk the preds/succs and check if there is at least one already
marked hot. Keep track of the most frequent pred/succ so that we
can mark it hot if we don't find one. The following loop will look for the hottest edge via
the edge count, if it is non-zero, then fallback to the edge
frequency and finally the edge probability. If bb is reached by (or reaches, in the case of !WALK_UP) another hot
block (or unpartitioned, e.g. the entry block) then it is ok. If not,
then the most frequent pred (or succ) needs to be adjusted. In the
case where multiple preds/succs have the same frequency (e.g. a
50-50 branch), then both will be adjusted. Select the hottest edge using the edge count, if it is non-zero,
then fallback to the edge frequency and finally the edge
probability. We have a hot bb with an immediate dominator that is cold.
The dominator needs to be re-marked hot. Now we need to examine newly-hot reach_bb to see if it is also
dominated by a cold bb.
References BB_SET_PARTITION, cfun, FOR_EACH_EDGE, basic_block_def::preds, probably_never_executed_bb_p(), and probably_never_executed_edge_p().
|
static |
Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru.
The FALLTHRU edge is also CAN_FALLTHRU edge.
If the BB ends with an invertible condjump all (2) edges are CAN_FALLTHRU edges.
Variable Documentation
|
static |
The current size of the following dynamic array.
|
static |
The array which holds needed information for basic blocks.
|
static |
Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE.
Referenced by find_traces().
| struct target_bb_reorder default_target_bb_reorder |
|
static |
Exec thresholds in thousandths (per mille) of the frequency of bb 0.
Referenced by find_traces().
|
static |
Referenced by find_traces().
|
static |
Maximum frequency and count of one of the entry blocks.
Referenced by find_traces().
