- Generated by
1.8.1.1
|
GCC Middle and Back End API Reference
|
Data Structures | |
| struct | bblst |
| struct | candidate |
| struct | edgelst |
Typedefs | |
| typedef sbitmap | edgeset |
|
static |
Add dependences so that branches are scheduled to run last in their block.
For all branches, calls, uses, clobbers, cc0 setters, and instructions
that can throw exceptions, force them to remain in order at the end of
the block by adding dependencies and giving the last a high priority.
There may be notes present, and prev_head may also be a note.
Branches must obviously remain at the end. Calls should remain at the
end since moving them results in worse register allocation. Uses remain
at the end to ensure proper register allocation.
cc0 setters remain at the end because they can't be moved away from
their cc0 user.
COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).
Insns setting TARGET_CLASS_LIKELY_SPILLED_P registers (usually return
values) are not moved before reload because we can wind up with register
allocation failures. Don't overrun the bounds of the basic block.
Make sure these insns are scheduled last in their block.
Finally, if the block ends in a jump, and we are doing intra-block
scheduling, make sure that the branch depends on any COND_EXEC insns
inside the block to avoid moving the COND_EXECs past the branch insn.
We only have to do this after reload, because (1) before reload there
are no COND_EXEC insns, and (2) the region scheduler is an intra-block
scheduler after reload.
FIXME: We could in some cases move COND_EXEC insns past the branch if
this scheduler would be a little smarter. Consider this code:
T = [addr]
C ? addr += 4
!C ? X += 12
C ? T += 1
C ? jump foo
On a target with a one cycle stall on a memory access the optimal
sequence would be:
T = [addr]
C ? addr += 4
C ? T += 1
C ? jump foo
!C ? X += 12
We don't want to put the 'X += 12' before the branch because it just
wastes a cycle of execution time when the branch is taken.
Note that in the example "!C" will always be true. That is another
possible improvement for handling COND_EXECs in this scheduler: it
could remove always-true predicates. Note that we want to add this dependency even when
sched_insns_conditions_mutex_p returns true. The whole point
is that we _want_ this dependency, even if these insns really
are independent.
References deps_join(), edge_def::dest, basic_block_def::index, deps_desc::pending_jump_insns, deps_desc::pending_read_insns, deps_desc::pending_read_mems, deps_desc::pending_write_insns, deps_desc::pending_write_mems, and basic_block_def::succs.
|
static |
|
static |
Return next block in ebb chain. For parameter meaning please refer to sched-int.h: struct sched_info: advance_target_bb.
|
static |
True when a bb with index BB_INDEX contained in region RGN.
References probability_cutoff, and profile_info.
|
static |
|
static |
Updates counter and other information. Split from can_schedule_ready_p () because when we schedule insn speculatively then insn passed to can_schedule_ready_p () differs from the one passed to begin_schedule_ready ().
An interblock motion?
For speculative load, mark insns fed by it.
In block motion.
|
static |
|
static |
Called after taking INSN from the ready list. Returns nonzero if this insn can be scheduled, nonzero if we should silently discard it.
An interblock motion?
|
static |
Return 1 if insn can be speculatively moved from block src to trg, otherwise return 0. Called before first insertion of insn to ready-list or before the scheduling.
Find the registers set by instruction.
References bblst::nr_members, and candidate::split_bbs.
Referenced by is_prisky().
|
static |
Speculative scheduling functions.
Referenced by check_live_1().
|
static |
Return 0 if x is a set of a register alive in the beginning of one of the split-blocks of src, otherwise return 1.
Global registers are assumed live.
Check for hard registers.
We can have split blocks, that were recently generated.
Such blocks are always outside current region. Check for pseudo registers.
References check_live_1(), and SET.
|
static |
|
static |
Compute dependences inside bb. In a multiple blocks region: (1) a bb is analyzed after its predecessors, and (2) the lists in effect at the end of bb (after analyzing for bb) are inherited by bb's successors. Specifically for reg-reg data dependences, the block insns are scanned by sched_analyze () top-to-bottom. Three lists are maintained by sched_analyze (): reg_last[].sets for register DEFs, reg_last[].implicit_sets for implicit hard register DEFs, and reg_last[].uses for register USEs. When analysis is completed for bb, we update for its successors: ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb]) ; - IMPLICIT_DEFS[succ] = Union (IMPLICIT_DEFS [succ], IMPLICIT_DEFS [bb]) ; - USES[succ] = Union (USES [succ], DEFS [bb]) The mechanism for computing mem-mem data dependence is very similar, and the result is interblock dependences in the region.
Do the analysis for this block.
Selective scheduling handles control dependencies by itself.
Free up the INSN_LISTs.
|
static |
Functions for regions scheduling information.
Compute dominators, probability, and potential-split-edges of bb. Assume that these values were already computed for bb's predecessors.
We shouldn't have any real ebbs yet.
Initialize dom[bb] to '111..1'.
INSN is a JUMP_INSN. Store the set of registers that must be considered as used by this jump in USED.
Nothing to do here, since we postprocess jumps in
add_branch_dependences.
| void compute_priorities | ( | void | ) |
Compute insn priority for a current region.
|
static |
|
static |
Find the valid candidate-source-blocks for the target block TRG, compute their probability, and check if they are speculative or not. For speculative sources, compute their update-blocks and split-blocks.
bblst_table holds split blocks and update blocks for each block after
the current one in the region. split blocks and update blocks are
the TO blocks of region edges, so there can be at most rgn_nr_edges
of them. Define some of the fields for the target bb as well.
In CFGs with low probability edges TF can possibly be zero.
Compute split blocks and store them in bblst_table.
The TO block of every split edge is a split block. Compute update blocks and store them in bblst_table.
For every split edge, look at the FROM block, and check
all out edges. For each out edge that is not a split edge,
add the TO block to the update block list. This list can end
up with a lot of duplicates. We need to weed them out to avoid
overrunning the end of the bblst_table. Make sure we didn't overrun the end of bblst_table.
References bblst::first_member, basic_block_def::index, bblst::nr_members, candidate::split_bbs, and candidate::update_bbs.
|
static |
| int contributes_to_priority | ( | ) |
NEXT is an instruction that depends on INSN (a backward dependence); return nonzero if we should include this dependence in priority calculations.
NEXT and INSN reside in one ebb.
| void debug_candidate | ( | int | ) |
| DEBUG_FUNCTION void debug_candidate | ( | ) |
Print candidates info, for debugging purposes. Callable from debugger.
References global_regs, and update_live_1().
| void debug_candidates | ( | int | ) |
| DEBUG_FUNCTION void debug_candidates | ( | ) |
Print candidates info, for debugging purposes. Callable from debugger.
References bitmap_set_bit(), bitmap_set_range(), df_get_live_in(), bblst::first_member, bblst::nr_members, and candidate::update_bbs.
Print dependencies information for instructions between HEAD and TAIL. ??? This function would probably fit best in haifa-sched.c.
| DEBUG_FUNCTION void debug_region | ( | ) |
Print the region's basic blocks.
We don't have ebb_head initialized yet, so we can't use
BB_TO_BLOCK ().
| DEBUG_FUNCTION void debug_regions | ( | void | ) |
Functions for the construction of regions.
Print the regions, for debugging purposes. Callable from debugger.
We don't have ebb_head initialized yet, so we can't use
BB_TO_BLOCK ().
References current_blocks, dump_bb(), and rgn_bb_table.
Referenced by free_rgn_deps().
| DEBUG_FUNCTION void debug_rgn_dependencies | ( | ) |
Print dependences for debugging starting from FROM_BB. Callable from debugger.
Print dependences for debugging starting from FROM_BB. Callable from debugger.
| void deps_join | ( | ) |
Join PRED_DEPS to the SUCC_DEPS.
The reg_last lists are inherited by successor.
Mem read/write lists are inherited by successor.
last_function_call is inherited by successor.
last_function_call_may_noreturn is inherited by successor.
sched_before_next_call is inherited by successor.
| void dump_region_dot | ( | ) |
Dump region RGN to file F using dot syntax.
We don't have ebb_head initialized yet, so we can't use
BB_TO_BLOCK ().
| void dump_region_dot_file | ( | ) |
The same, but first open a file specified by FNAME.
| void extend_regions | ( | void | ) |
Extend internal data structures.
| void extend_rgns | ( | ) |
Extend regions. DEGREE - Array of incoming edge count, considering only the edges, that don't have their sources in formed regions yet. IDXP - pointer to the next available index in rgn_bb_table. HEADER - set of all region heads. LOOP_HDR - mapping from block to the containing loop (two blocks can reside within one region if they have the same loop header).
This block already was processed in find_rgns.
The idea is to topologically walk through CFG in top-down order.
During the traversal, if all the predecessors of a node are
marked to be in the same region (they all have the same max_hdr),
then current node is also marked to be a part of that region.
Otherwise the node starts its own region.
CFG should be traversed until no further changes are made. On each
iteration the set of the region heads is extended (the set of those
blocks that have max_hdr[bbi] == bbi). This set is upper bounded by the
set of all basic blocks, thus the algorithm is guaranteed to
terminate. If pred wasn't processed in find_rgns.
And pred and bb reside in the same loop.
(Or out of any loop). Then bb extends the containing region of pred.
Too bad, there are at least two predecessors
that reside in different regions. Thus, BB should
begin its own region. BB starts its own region.
If BB start its own region,
update set of headers with BB. Statistics were gathered on the SPEC2000 package of tests with
mainline weekly snapshot gcc-4.1-20051015 on ia64.
Statistics for SPECint:
1 iteration : 1751 cases (38.7%)
2 iterations: 2770 cases (61.3%)
Blocks wrapped in regions by find_rgns without extension: 18295 blocks
Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
(We don't count single block regions here).
Statistics for SPECfp:
1 iteration : 621 cases (35.9%)
2 iterations: 1110 cases (64.1%)
Blocks wrapped in regions by find_rgns without extension: 6476 blocks
Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
(We don't count single block regions here).
By default we do at most 2 iterations.
This can be overridden with max-sched-extend-regions-iters parameter:
0 - disable region extension,
N > 0 - do at most N iterations. Save the old statistics for later printout.
We have succeeded. Now assemble the regions.
BBN is a region head.
Here we check whether the region is too_large.
If the region is too_large, then wrap every block of
the region into single block region.
Here we wrap region head only. Other blocks are
processed in the below cycle. This cycle iterates over all basic blocks, that
are supposed to be in the region with head BBN,
and wraps them into that region (or in single
block region). Wrap SUCCN into single block region.
Get the new statistics and print the comparison with the
one before calling this function.
|
static |
Extract list of edges from a bitmap containing EDGE_TO_BIT bits.
edgelst table space is reused in each call to extract_edgelst.
Iterate over each word in the bitset.
|
static |
Referenced by update_live_1().
|
static |
@verbatim
On the path from the insn to load_insn_bb, find a conditional branch depending on insn, that guards the speculative load.
Iterate through DEF-USE forward dependences.
|
static |
Wrapper function. If FLAG_SEL_SCHED_PIPELINING is set, then use custom function to form regions. Otherwise just call find_rgns_haifa.
Referenced by free_rgn_deps().
|
static |
|
static |
Build a single block region for each basic block in the function. This allows for using the same code for interblock and basic block scheduling.
|
static |
Free the arrays of DFA states at the end of each basic block.
|
static |
Free dependencies of instructions inside BB.
|
static |
Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add them to the unused_*_list variables, so that they can be reused.
| void free_rgn_deps | ( | void | ) |
Free all region dependencies saved in INSN_BACK_DEPS and INSN_RESOLVED_BACK_DEPS. The Haifa scheduler does this on the fly when scheduling, so this function is supposed to be called from the selective scheduling only.
References calculate_dominance_info(), CDI_DOMINATORS, debug_regions(), find_rgns(), free_dominance_info(), sched_verbose, and sel_sched_p().
|
static |
Free the computed target info.
|
static |
|
static |
Referenced by schedule_insns().
|
static |
|
static |
Calculate the histogram that shows the number of regions having the given number of basic blocks, and store it in the RSP array. Return the size of this array.
a[i] is the number of regions that have (i + 1) basic blocks.
References bitmap_bit_p(), basic_block_def::index, and edge_def::src.
| int get_rgn_sched_max_insns_priority | ( | void | ) |
Returns maximum priority that an insn was assigned to.
|
static |
Find regions for interblock scheduling.
A region for scheduling can be:
* A loop-free procedure, or
* A reducible inner loop, or
* A basic block not contained in any other region.
?!? In theory we could build other regions based on extended basic
blocks or reverse extended basic blocks. Is it worth the trouble?
Loop blocks that form a region are put into the region's block list
in topological order.
This procedure stores its results into the following global (ick) variables
* rgn_nr
* rgn_table
* rgn_bb_table
* block_to_bb
* containing region
We use dominator relationships to avoid making regions out of non-reducible
loops.
This procedure needs to be converted to work on pred/succ lists instead
of edge tables. That would simplify it somewhat. Note if a block is a natural loop header.
Note if a block is a natural inner loop header.
Note if a block is in the block queue.
Note if a block is in the block queue.
Perform a DFS traversal of the cfg. Identify loop headers, inner loops
and a mapping from block to its loop header (if the block is contained
in a loop, else -1).
Store results in HEADER, INNER, and MAX_HDR respectively, these will
be used as inputs to the second traversal.
STACK, SP and DFS_NR are only used during the first traversal. Allocate and initialize variables for the first traversal.
DFS traversal to find inner loops in the cfg.
We have reached a leaf node or a node that was already
processed. Pop edges off the stack until we find
an edge that has not yet been processed. Pop entry off the stack.
See if have finished the DFS tree traversal.
Nope, continue the traversal with the popped node.
Process a node.
We don't traverse to the exit block.
If the successor is in the stack, then we've found a loop.
Mark the loop, if it is not a natural loop, then it will
be rejected during the second traversal. If the child was already visited, then there is no need to visit
it again. Just update the loop relationships and restart
with a new edge. Push an entry on the stack and continue DFS traversal.
Reset ->aux field used by EDGE_PASSED.
Another check for unreachable blocks. The earlier test in
is_cfg_nonregular only finds unreachable blocks that do not
form a loop.
The DFS traversal will mark every block that is reachable from
the entry node by placing a nonzero value in dfs_nr. Thus if
dfs_nr is zero for any block, then it must be unreachable. Gross. To avoid wasting memory, the second pass uses the dfs_nr array
to hold degree counts. Do not perform region scheduling if there are any unreachable
blocks. We use EXTENDED_RGN_HEADER as an addition to HEADER and put
there basic blocks, which are forced to be region heads.
This is done to try to assemble few smaller regions
from a too_large region. Second traversal:find reducible inner loops and topologically sort
block of each region. Find blocks which are inner loop headers. We still have non-reducible
loops to consider at this point. Now check that the loop is reducible. We do this separate
from finding inner loops so that we do not find a reducible
loop which contains an inner non-reducible loop.
A simple way to find reducible/natural loops is to verify
that each block in the loop is dominated by the loop
header.
If there exists a block that is not dominated by the loop
header, then the block is reachable from outside the loop
and thus the loop is not a natural loop. First identify blocks in the loop, except for the loop
entry block. Now verify that the block is dominated by the loop
header. If we exited the loop early, then I is the header of
a non-reducible loop and we should quit processing it
now. I is a header of an inner loop, or block 0 in a subroutine
with no loops at all. We save degree in case when we meet a too_large region
and cancel it. We need a correct degree later when
calling extend_rgns. Decrease degree of all I's successors for topological
ordering. Estimate # insns, and count # blocks in the region.
Find all loop latches (blocks with back edges to the loop
header) or all the leaf blocks in the cfg has no loops.
Place those blocks into the queue. Leaf nodes have only a single successor which must
be EXIT_BLOCK. This is a loop latch.
Now add all the blocks in the loop to the queue.
We know the loop is a natural loop; however the algorithm
above will not always mark certain blocks as being in the
loop. Consider:
node children
a b,c
b c
c a,d
d b
The algorithm in the DFS traversal may not mark B & D as part
of the loop (i.e. they will not have max_hdr set to A).
We know they can not be loop latches (else they would have
had max_hdr set since they'd have a backedge to a dominator
block). So we don't need them on the initial queue.
We know they are part of the loop because they are dominated
by the loop header and can be reached by a backwards walk of
the edges starting with nodes on the initial queue.
It is safe and desirable to include those nodes in the
loop/scheduling region. To do so we would need to decrease
the degree of a node if it is the target of a backedge
within the loop itself as the node is placed in the queue.
We do not do this because I'm not sure that the actual
scheduling code will properly handle this case. ?!? See discussion above about nodes not marked as in
this loop during the initial DFS traversal. Place the loop header into list of region blocks.
Remove blocks from queue[] when their in degree
becomes zero. Repeat until no blocks are left on the
list. This produces a topological list of blocks in
the region. Restore DEGREE.
And force successors of BB to be region heads.
This may provide several smaller regions instead
of one too_large region. Any block that did not end up in a region is placed into a region
by itself.
|
static |
Implementations of the sched_info functions for region scheduling.
Add all insns that are initially ready to the ready list READY. Called once before scheduling a set of insns.
Print debugging information.
Prepare current target block info.
Initialize ready list with all 'ready' insns in target block.
Count number of insns in the target block being scheduled. Add to ready list all 'ready' insns in valid source blocks.
For speculative insns, check-live, exception-free, and
issue-delay.
References target_bb.
|
static |
Functions for construction of the control flow graph.
Return 1 if control flow graph should not be constructed, 0 otherwise. We decide not to build the control flow graph if there is possibly more than one entry to the function, if computed branches exist, if we have nonlocal gotos, or if we have an unreachable loop.
If we have a label that could be the target of a nonlocal goto, then
the cfg is not well structured. If we have any forced labels, then the cfg is not well structured.
If we have exception handlers, then we consider the cfg not well
structured. ?!? We should be able to handle this now that we
compute an accurate cfg for EH. If we have insns which refer to labels as non-jumped-to operands,
then we consider the cfg not well structured. If this function has a computed jump, then we consider the cfg
not well structured. For that label not to be seen as a referred-to label, this
must be a single-set which is feeding a jump *only*. This
could be a conditional jump with the label split off for
machine-specific reasons or a casesi/tablejump. Unreachable loops with more than one basic block are detected
during the DFS traversal in find_rgns.
Unreachable loops with a single block are detected here. This
test is redundant with the one in find_rgns, but it's much
cheaper to go ahead and catch the trivial case here. All the tests passed. Consider the cfg well structured.
|
static |
Referenced by set_spec_fed(), and update_live_1().
|
static |
Returns 1 if the same insn1 that participates in the computation of load_insn's address is feeding a conditional branch that is guarding on load_insn. This is true if we find two DEF-USE chains: insn1 -> ... -> conditional-branch insn1 -> ... -> load_insn, and if a flow path exists: insn1 -> ... -> conditional-branch -> ... -> load_insn, and if insn1 is on the path region-entry -> ... -> bb_trg -> ... load_insn. Locate insn1 by climbing on INSN_BACK_DEPS from load_insn. Locate the branch by following INSN_FORW_DEPS from insn1.
Must be a DEF-USE dependence upon non-branch.
Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn.
Now search for the conditional-branch.
Recursive step: search another insn1, "above" current insn1.
The chain does not exist.
|
static |
|
static |
Insn is a candidate to be moved speculatively from bb_src to bb_trg. Return 1 if insn is exception-free (and the motion is valid) and 0 otherwise.
Handle non-load insns.
Handle loads.
Don't 'break' here: PFREE-candidate is also PRISKY-candidate.
|
static |
|
static |
Returns 1 if a clue for "similar load" 'insn2' is found, and hence load_insn can move speculatively from bb_src to bb_trg. All the following must hold: (1) both loads have 1 base register (PFREE_CANDIDATEs). (2) load_insn and load1 have a def-use dependence upon the same insn 'insn1'. (3) either load2 is in bb_trg, or: - there's only one split-block, and - load1 is on the escape path, and From all these we can conclude that the two loads access memory addresses that differ at most by a constant, and hence if moving load_insn would cause an exception, it would have been caused by load2 anyhow.
Must have exactly one escape block.
Found a DEF-USE dependence (insn1, load_insn).
Found a DEF-USE dependence (insn1, insn2).
insn2 not guaranteed to be a 1 base reg load.
insn2 is the similar load, in the target block.
insn2 is a similar load, in a split-block.
Couldn't find a similar load.
|
static |
|
static |
Return 1 if load_insn is prisky (i.e. if load_insn is fed by a load moved speculatively, or if load_insn is protected by a compare on load_insn's address).
Dependence may 'hide' out of the region.
References check_live(), nr_inter, nr_spec, set_spec_fed(), target_bb, and update_live().
| rtl_opt_pass* make_pass_sched | ( | ) |
| rtl_opt_pass* make_pass_sched2 | ( | ) |
Referenced by schedule_insns().
|
static |
Called after INSN has all its hard dependencies resolved and the speculation of type TS is enough to overcome them all. Return nonzero if it should be moved to the ready list or the queue, or zero if we should silently discard it.
For speculative insns, before inserting to ready/queue,
check live, exception-free, and issue-delay. We are here because is_exception_free () == false.
But we possibly can handle that with control speculation. Add control speculation to NEXT's dependency type.
Check if NEXT can be speculated with new dependency type.
Here we got new control-speculative instruction.
NEXT isn't ready yet.
NEXT isn't ready yet.
References rgn_sched_info, and haifa_sched_info::sched_max_insns_priority.
|
static |
|
static |
Print regions statistics. S1 and S2 denote the data before and after calling extend_rgns, respectively.
We iterate until s2_sz because extend_rgns does not decrease
the maximal region size.
|
static |
|
static |
After computing the dependencies for block BB, propagate the dependencies found in TMP_DEPS to the successors of the block.
bb's structures are inherited by its successors.
Only bbs "below" bb, in the same region, are interesting.
These lists should point to the right place, for correct
freeing later. Can't allow these to be freed twice.
|
static |
(Re-)initialize the arrays of DFA states at the end of each basic block. SAVED_LAST_BASIC_BLOCK is the previous length of the arrays. It must be zero for the first call to this function, to allocate the arrays for the first time. This function is called once during initialization of the scheduler, and called again to resize the arrays if new basic blocks have been created, for example for speculation recovery code.
Nothing to do if nothing changed since the last time this was called.
The selective scheduler doesn't use the state arrays.
If BB_STATE_ARRAY has moved, fixup all the state pointers array.
Otherwise only fixup the newly allocated ones. For the state
array itself, only initialize the new entries.
|
static |
Run instruction scheduler.
|
static |
Run second scheduling pass after reload.
Do control and data sched analysis again,
and write some more of the results to dump file.
Referenced by schedule_insns().
|
static |
|
static |
BB was added to ebb after AFTER.
We need to fix rgn_table, block_to_bb, containing_rgn
and ebb_head. We extend ebb_head to one more position to
easily find the last position of the last ebb in
the current region. Thus, ebb_head[BLOCK_TO_BB (after) + 1]
is _always_ valid for access. Now POS is the index of the last block in the region.
Find index of basic block AFTER.
i - ebb right after "AFTER".
ebb_head[i] - VALID.
Source position: ebb_head[i]
Destination position: ebb_head[i] + 1
Last position:
RGN_BLOCKS (nr_regions) - 1
Number of elements to copy: (last_position) - (source_position) + 1
|
static |
Functions for speculative scheduling.
|
static |
INSN has been added to/removed from current region.
|
static |
Estimate number of the insns in the BB.
|
static |
|
static |
Fix internal data after interblock movement of jump instruction. For parameter meaning please refer to sched-int.h: struct sched_info: fix_recovery_cfg.
|
static |
Return true if scheduling INSN will trigger finish of scheduling current block.
INSN is the last not-scheduled instruction in the current block.
References alloc_INSN_LIST().
| void rgn_make_new_region_out_of_new_block | ( | ) |
I - first free position in rgn_bb_table.
|
static |
|
static |
Return a string that contains the insn uid and optionally anything else necessary to identify this insn in an output. It's valid to use a static buffer for this. The ALIGNED parameter should cause the string to be formatted so that multiple output lines will line up nicely.
|
static |
Compare priority of two insns. Return a positive number if the second insn is to be preferred for scheduling, and a negative one if the first is to be preferred. Zero if they are equally good.
Some comparison make sense in interblock scheduling only.
Prefer an inblock motion on an interblock motion.
Prefer a useful motion on a speculative one.
Prefer a more probable (speculative) insn.
| void rgn_setup_common_sched_info | ( | void | ) |
Setup scheduler infos.
References RTL_PASS.
| void rgn_setup_region | ( | ) |
Setup global variables like CURRENT_BLOCKS and CURRENT_NR_BLOCK to point to the region RGN.
Set variables for the current region.
EBB_HEAD is a region-scope structure. But we realloc it for
each region to save time/memory/something else.
See comments in add_block1, for what reasons we allocate +1 element.
References ebb_head, basic_block_def::index, and rgn_bb_table.
| void rgn_setup_sched_infos | ( | void | ) |
Setup all *_sched_info structures (for the Haifa frontend and for the dependence analysis) in the interblock scheduler.
Referenced by code_motion_process_successors().
| bool sched_is_disabled_for_current_region_p | ( | void | ) |
Returns true if all the basic blocks of the current region have NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region.
| void sched_rgn_compute_dependencies | ( | ) |
Compute instruction dependencies in region RGN.
Initializations for region data dependence analysis.
Initialize bitmap used in add_branch_dependences.
Compute backward dependencies.
We don't want to recalculate this twice.
(This is a recovery block. It is always a single block region.)
OR (We use selective scheduling.)
| void sched_rgn_finish | ( | void | ) |
Free data structures for region scheduling.
Reposition the prologue and epilogue notes in case we moved the
prologue/epilogue insns.
| void sched_rgn_init | ( | ) |
Initialize data structures for region scheduling.
Compute regions for scheduling.
Compute the dominators and post dominators.
Find regions.
For now. This will move as more and more of haifa is converted
to using the cfg code.
| void sched_rgn_local_finish | ( | void | ) |
Free data computed for the finished region.
| void sched_rgn_local_free | ( | void | ) |
Free data computed for the finished region.
References maybe_skip_selective_scheduling(), and run_selective_scheduling().
| void sched_rgn_local_init | ( | ) |
Init region data structures. Returns true if this region should not be scheduled.
Compute interblock info: probabilities, split-edges, dominators, etc.
Use ->aux to implement EDGE_TO_BIT mapping.
Split edges.
Compute probabilities, dominators, split_edges.
Cleanup ->aux used for EDGE_TO_BIT mapping.
We don't need them anymore. But we want to avoid duplication of
aux fields in the newly created edges.
| void schedule_insns | ( | void | ) |
The one entry point in this file.
Taking care of this degenerate case makes the rest of
this code simpler. Schedule every region in the subroutine.
Clean up.
References execute(), gate_handle_sched2(), make_pass_sched2(), rest_of_handle_sched2(), and RTL_PASS.
|
static |
Return nonzero if there are more insns that should be scheduled.
|
static |
|
static |
Schedule a region. A region is either an inner loop, a loop-free subroutine, or a single basic block. Each bb in the region is scheduled after its flow predecessors.
Don't schedule region that is marked by
NOTE_DISABLE_SCHED_OF_BLOCK. Set priorities.
Now we can schedule all blocks.
Clean up.
Sanity check: verify that all region insns were scheduled.
Done with this region.
Free dependencies.
|
static |
Turns on the fed_by_spec_load flag for insns fed by load_insn.
References is_conditionally_protected(), and sd_lists_empty_p().
Referenced by is_prisky().
|
static |
|
static |
Determine if PAT sets a TARGET_CLASS_LIKELY_SPILLED_P register.
|
static |
|
static |
Target info functions.
|
static |
Functions for target info.
Compute in BL the list of split-edges of bb_src relatively to bb_trg. Note that bb_trg dominates bb_src.
References free().
|
static |
|
static |
Update number of blocks and the estimate for number of insns in the region. Return true if the region is "too large" for interblock scheduling (compile time considerations).
References bitmap_clear(), bitmap_ones(), count, sbitmap_alloc(), and stack.
|
static |
Update the live registers info after insn was moved speculatively from block src to trg.
Find the registers set by instruction.
References bblst::first_member, haifa_classify_insn(), PFREE_CANDIDATE, and candidate::split_bbs.
Referenced by is_prisky().
|
static |
Referenced by debug_candidate().
|
static |
If x is a set of a register R, mark that R is alive in the beginning of every update-block of src.
Global registers are always live, so the code below does not apply
to them.
References find_conditional_protection(), and is_conditionally_protected().
|
static |
For every bb, a set of its ancestor edges.
|
static |
Data structures for the computation of data dependences in a regions. We keep one `deps' structure for every basic block. Before analyzing the data dependences for a bb, its variables are initialized as a function of the variables of its predecessors. When the analysis for a bb completes, we save the contents to the corresponding bb_deps[bb] variable.
|
static |
|
static |
Arrays that hold the DFA state at the end of a basic block, to re-use as the initial state at the start of successor blocks. The BB_STATE array holds the actual DFA state, and BB_STATE_ARRAY[I] is a pointer into BB_STATE for basic block I. FIXME: This should be a vec.
|
static |
|
static |
|
static |
A speculative motion requires checking live information on the path from 'source' to 'target'. The split blocks are those to be checked. After a speculative motion, live information should be modified in the 'update' blocks. Lists of split and update blocks for each candidate of the current target are in array bblst_table.
| int* block_to_bb = NULL |
Topological order of blocks in the region (if b2 is reachable from b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is always referred to by either block or b, while its topological order name (in the region) is referred to by bb.
|
static |
| int* containing_rgn = NULL |
The number of the region containing a block.
| int current_blocks |
Referenced by debug_regions().
| int current_nr_blocks |
Blocks of the current region being scheduled.
Referenced by code_motion_process_successors(), and mark_regno_birth_or_death().
|
static |
Dominators array: dom[i] contains the sbitmap of dominators of bb i in the region.
Referenced by determine_dominators_for_sons(), do_partial_partial_insertion(), get_immediate_dominator(), isl_id_for_ssa_name(), and occ_new().
| int* ebb_head = NULL |
ebb_head [i] - is index in rgn_bb_table of the head basic block of i'th ebb. Currently we can get a ebb only through splitting of currently scheduling block, therefore, we don't need ebb_head array for every region, hence, its sufficient to hold it for current one only.
Referenced by rgn_setup_region().
|
static |
|
static |
|
static |
A bitmap to note insns that participate in any dependency. Used in add_branch_dependences.
|
static |
The minimum probability of reaching a source block so that it will be considered for speculative scheduling.
|
static |
Functions for speculative scheduling.
|
static |
nr_inter/spec counts interblock/speculative motion for the function.
Referenced by is_prisky().
| int nr_regions = 0 |
Number of regions in the procedure.
|
static |
Referenced by is_prisky().
|
static |
The split edges of a source bb is different for each target bb. In order to compute this efficiently, the 'potential-split edges' are computed for each bb prior to scheduling a region. This is actually the split edges of each bb relative to the region entry. pot_split[bb] is the set of potential split edges of bb.
|
static |
Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is the probability of bb i relative to the region entry.
Referenced by create_empty_if_region_on_edge(), estimate_ipcp_clone_size_and_time(), find_traces_1_round(), fixup_new_cold_bb(), scale_dominated_blocks_in_loop(), and vect_create_cond_for_alias_checks().
| int* rgn_bb_table = NULL |
Array of lists of regions' blocks.
Referenced by debug_regions(), and rgn_setup_region().
|
static |
This variable holds common_sched_info hooks and data relevant to the interblock scheduler.
|
static |
This holds constant data used for initializing the above structure for the Haifa scheduler.
|
static |
Used in schedule_insns to initialize current_sched_info for scheduling regions (or single basic blocks).
|
static |
Same as above, but for the selective scheduler.
|
static |
Array of size rgn_nr_edges.
|
static |
|
static |
Number of edges in the region.
|
static |
This holds data for the dependence analysis relevant to the interblock scheduler.
|
static |
This variable holds the data and hooks needed to the Haifa scheduler backend for the interblock scheduler frontend.
Referenced by new_ready().
| region* rgn_table = NULL |
Table of region descriptions.
|
static |
The number of insns from the entire region scheduled so far.
|
static |
The number of insns from the current block scheduled so far.
| int target_bb |
The bb being currently scheduled.
Referenced by init_ready_list(), and is_prisky().
|
static |
The number of insns from the current block to be scheduled in total.
1.8.1.1