Go to the source code of this file.
Data Structures | |
| struct | edge_def |
| union | edge_def::edge_def_insns |
| struct | profile_record |
| struct | rtl_bb_info |
| struct | gimple_bb_info |
| struct | basic_block_def |
| union | basic_block_def::basic_block_il_dependent |
| struct | control_flow_graph |
| struct | ce_if_block |
| struct | edge_list |
| class | control_dependences |
| struct | edge_iterator |
Typedefs | |
| typedef int | __assert_gimple_bb_smaller_rtl_bb [(int) sizeof(struct rtl_bb_info)-(int) sizeof(struct gimple_bb_info)] |
| typedef struct ce_if_block | ce_if_block_t |
| typedef struct gcov_working_set_info | gcov_working_set_t |
Enumerations | |
| enum | cfg_edge_flags { LAST_CFG_EDGE_FLAG } |
| enum | cfg_bb_flags { LAST_CFG_BB_FLAG } |
| enum | dom_state { DOM_NONE, DOM_NO_FAST_QUERY, DOM_OK } |
| enum | profile_status_d { PROFILE_ABSENT, PROFILE_GUESSED, PROFILE_READ, PROFILE_LAST } |
| enum | replace_direction { dir_none, dir_forward, dir_backward, dir_both } |
| enum | cdi_direction { CDI_DOMINATORS = 1, CDI_POST_DOMINATORS = 2 } |
Variables | |
| struct gcov_ctr_summary * | profile_info |
| edge | mfb_kj_edge |
Typedef Documentation
| typedef int __assert_gimple_bb_smaller_rtl_bb[(int) sizeof(struct rtl_bb_info)-(int) sizeof(struct gimple_bb_info)] |
This ensures that struct gimple_bb_info is smaller than struct rtl_bb_info, so that inlining the former into basic_block_def is the better choice.
| typedef struct ce_if_block ce_if_block_t |
Structure to group all of the information to process IF-THEN and IF-THEN-ELSE blocks for the conditional execution support. This needs to be in a public file in case the IFCVT macros call functions passing the ce_if_block data structure.
| typedef struct gcov_working_set_info gcov_working_set_t |
In profile.c.
Enumeration Type Documentation
| enum cdi_direction |
| enum cfg_bb_flags |
| enum cfg_edge_flags |
| enum dom_state |
| enum profile_status_d |
| enum replace_direction |
Function Documentation
| void add_noreturn_fake_exit_edges | ( | void | ) |
This function will add a fake edge between any block which has no successors, and the exit block. Some data flow equations require these edges to exist.
Referenced by output_location(), and pre_insert_copies().
| void add_to_dominance_info | ( | enum | cdi_direction, |
| basic_block | |||
| ) |
| void alloc_aux_for_blocks | ( | int | ) |
| void alloc_aux_for_edge | ( | edge | , |
| int | |||
| ) |
Referenced by free_aux_for_blocks().
| void alloc_aux_for_edges | ( | int | ) |
| basic_block alloc_block | ( | void | ) |
Allocate memory for basic_block.
References basic_block_def::next_bb, and basic_block_def::prev_bb.
|
inlinestatic |
Apply probability PROB on frequency or count FREQ.
Referenced by cgraph_clone_edge(), and expand_transaction().
|
inlinestatic |
Apply scale factor SCALE on frequency or count FREQ. Use this interface when potentially scaling up, so that SCALE is not constrained to be < REG_BR_PROB_BASE.
Referenced by input_cfg(), and input_profile_summary().
| unsigned bb_dom_dfs_in | ( | enum | cdi_direction, |
| basic_block | |||
| ) |
Referenced by cmp_dfsnum().
| unsigned bb_dom_dfs_out | ( | enum | cdi_direction, |
| basic_block | |||
| ) |
Referenced by cmp_dfsnum().
|
inlinestatic |
Return true when one of the predecessor edges of BB is marked with EDGE_ABNORMAL.
Referenced by replace_pseudos_in().
|
inlinestatic |
Return true when one of the predecessor edges of BB is marked with EDGE_EH.
Referenced by mark_regno_birth_or_death().
| rtx bb_note | ( | basic_block | ) |
Referenced by delete_insn(), and has_preds_in_current_region_p().
| void bitmap_intersection_of_preds | ( | sbitmap | , |
| sbitmap * | , | ||
| basic_block | |||
| ) |
Referenced by compute_available().
| void bitmap_intersection_of_succs | ( | sbitmap | , |
| sbitmap * | , | ||
| basic_block | |||
| ) |
In cfganal.c
| void bitmap_union_of_preds | ( | sbitmap | , |
| sbitmap * | , | ||
| basic_block | |||
| ) |
Referenced by compute_kill(), and compute_out().
| void bitmap_union_of_succs | ( | sbitmap | , |
| sbitmap * | , | ||
| basic_block | |||
| ) |
| rtx block_label | ( | basic_block | ) |
In cfgrtl.c
Referenced by add_labels_and_missing_jumps(), emit_barrier_after_bb(), fixup_new_cold_bb(), and sched_extend_ready_list().
| bool br_prob_note_reliable_p | ( | const_rtx | ) |
| void break_superblocks | ( | void | ) |
Splits superblocks.
| void brief_dump_cfg | ( | FILE * | , |
| int | |||
| ) |
| edge cached_make_edge | ( | sbitmap | , |
| basic_block | , | ||
| basic_block | , | ||
| int | |||
| ) |
| void calculate_dominance_info | ( | enum | cdi_direction | ) |
| bool can_fallthru | ( | basic_block | , |
| basic_block | |||
| ) |
|
inlinestatic |
Check tha probability is sane.
| bool cleanup_cfg | ( | int | ) |
In cfgcleanup.c.
Referenced by migrate_btr_defs(), and remove_death().
| void clear_aux_for_blocks | ( | void | ) |
Clear AUX pointers of all blocks.
References edge_aux_obstack.
Referenced by alloc_aux_for_blocks(), and duplicate_computed_gotos().
| void clear_aux_for_edges | ( | void | ) |
Clear AUX pointers of all edges.
References first, and memset().
Referenced by alloc_aux_for_edges().
| void clear_bb_flags | ( | void | ) |
Clear all basic block flags that do not have to be preserved.
Referenced by reorder_basic_blocks().
| void clear_edges | ( | void | ) |
Free the memory associated with the edge structures.
References free_edge(), basic_block_def::preds, basic_block_def::succs, and vec_safe_truncate().
|
inlinestatic |
Given PROB1 and PROB2, return PROB1*PROB2/REG_BR_PROB_BASE. Used to combine BB probabilities.
Referenced by estimate_ipcp_clone_size_and_time().
| void commit_edge_insertions | ( | void | ) |
Update the CFG for all queued instructions.
Optimization passes that invoke this routine can cause hot blocks
previously reached by both hot and cold blocks to become dominated only
by cold blocks. This will cause the verification below to fail,
and lead to now cold code in the hot section. In some cases this
may only be visible after newly unreachable blocks are deleted,
which will be done by fixup_partitions.
Referenced by cfg_layout_can_merge_blocks_p().
| void commit_one_edge_insertion | ( | edge | e | ) |
| void compact_blocks | ( | void | ) |
Sequentially order blocks and compact the arrays.
References basic_block_def::index.
Referenced by cleanup_tree_cfg_1().
Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors. Return the number of passes we performed to iterate to a solution.
Allocate a worklist array/queue. Entries are only added to the
list if they were not already on the list. So the size is
bounded by the number of basic blocks. We want a maximal solution.
Put every block on the worklist; this is necessary because of the
optimistic initialization of AVOUT above. Mark blocks which are successors of the entry block so that we
can easily identify them below. Iterate until the worklist is empty.
Take the first entry off the worklist.
If one of the predecessor blocks is the ENTRY block, then the
intersection of avouts is the null set. We can identify such blocks
by the special value in the AUX field in the block structure. Do not clear the aux field for blocks which are successors of the
ENTRY block. That way we never add then to the worklist again. Clear the aux field of this block so that it can be added to
the worklist again if necessary. If the out state of this block changed, then we need
to add the successors of this block to the worklist
if they are not already on the worklist.
References basic_block_def::aux, bitmap_clear(), bitmap_intersection_of_preds(), bitmap_ior_and_compl(), edge_def::dest, basic_block_def::index, basic_block_def::succs, and worklist.
Referenced by compute_insert_delete(), and free_cprop_mem().
| void compute_bb_for_insn | ( | void | ) |
Records the basic block struct in BLOCK_FOR_INSN for every insn.
References df_analyze(), df_note_add_problem(), free_bb_for_insn(), and insert_section_boundary_note().
| void compute_dominance_frontiers | ( | struct bitmap_head_def * | ) |
| bitmap compute_idf | ( | bitmap | , |
| struct bitmap_head_def * | |||
| ) |
| void connect_infinite_loops_to_exit | ( | void | ) |
This function adds a fake edge between any infinite loops to the exit block. Some optimizations require a path from each node to the exit node. See also Morgan, Figure 3.10, pp. 82-83. The current implementation is ugly, not attempting to minimize the number of inserted fake edges. To reduce the number of fake edges to insert, add fake edges from _innermost_ loops containing only nodes not reachable from the exit block.
Perform depth-first search in the reverse graph to find nodes
reachable from the exit block. Repeatedly add fake edges, updating the unreachable nodes.
| bool contains_no_active_insn_p | ( | const_basic_block | ) |
| bool control_flow_insn_p | ( | const_rtx | ) |
Referenced by move_for_stack_reg(), rtl_verify_edges(), and swap_to_top().
| basic_block create_basic_block_structure | ( | rtx | , |
| rtx | , | ||
| rtx | , | ||
| basic_block | |||
| ) |
|
read |
Functions to access an edge list with a vector representation. Enough data is kept such that given an index number, the pred and succ that edge represents can be determined, or given a pred and a succ, its index number can be returned. This allows algorithms which consume a lot of memory to represent the normally full matrix of edge (pred,succ) with a single indexed vector, edge (EDGE_INDEX (pred, succ)), with no wasted space in the client code due to sparse flow graphs.
This functions initializes the edge list. Basically the entire flowgraph is processed, and all edges are assigned a number, and the data structure is filled in.
Determine the number of edges in the flow graph by counting successor
edges on each basic block. Follow successors of blocks, and register these edges.
References free().
Referenced by compute_insert_delete().
| void debug | ( | edge_def & | ref | ) |
| void debug | ( | edge_def * | ptr | ) |
| void debug_bb | ( | basic_block | ) |
| basic_block debug_bb_n | ( | int | ) |
| void default_rtl_profile | ( | void | ) |
Set RTL expansion to default mode (i.e. when profile info is not known).
References pointer_map_contains().
Referenced by blocks_nreverse().
| void delete_from_dominance_info | ( | enum | cdi_direction, |
| basic_block | |||
| ) |
| bool delete_unreachable_blocks | ( | void | ) |
Delete all unreachable basic blocks.
When we're in GIMPLE mode and there may be debug insns, we should
delete blocks in reverse dominator order, so as to get a chance
to substitute all released DEFs into debug stmts. If we don't
have dominators information, walking blocks backward gets us a
better chance of retaining most debug information than
otherwise. Speed up the removal of blocks that don't dominate
others. Walking backwards, this should be the common
case.
Referenced by cleanup_empty_eh_unsplit(), cleanup_tree_cfg_1(), and split_live_ranges_for_shrink_wrap().
| int dfs_enumerate_from | ( | basic_block | bb, |
| int | reverse, | ||
| bool(*)(const_basic_block, const void *) | predicate, | ||
| basic_block * | rslt, | ||
| int | rslt_max, | ||
| const void * | data | ||
| ) |
Performs dfs search from BB over vertices satisfying PREDICATE; if REVERSE, go against direction of edges. Returns number of blocks found and their list in RSLT. RSLT can contain at most RSLT_MAX items.
A bitmap to keep track of visited blocks. Allocating it each time
this function is called is not possible, since dfs_enumerate_from
is often used on small (almost) disjoint parts of cfg (bodies of
loops), and allocating a large sbitmap would lead to quadratic
behavior. Resize the VISITED sbitmap if necessary.
Ensure that we increase the size of the sbitmap exponentially.
References bitmap_set_bit(), CDI_DOMINATORS, get_immediate_dominator(), basic_block_def::index, basic_block_def::preds, and edge_def::src.
Referenced by thread_single_edge().
| basic_block dfs_find_deadend | ( | basic_block | ) |
Referenced by remove_fake_exit_edges().
| bool dom_info_available_p | ( | enum | cdi_direction | ) |
| enum dom_state dom_info_state | ( | enum | cdi_direction | ) |
| bool dominated_by_p | ( | enum | cdi_direction, |
| const_basic_block | , | ||
| const_basic_block | |||
| ) |
Referenced by bb_dom_dfs_in(), btr_def_live_range(), can_sm_ref_p(), dump_value_range(), eliminate_local_variables(), find_basis_for_base_expr(), find_dom(), find_identical_invariants(), find_subloop_latch_edge_by_profile(), get_instantiated_value_entry(), get_loop_latch_edges(), glb_enum_p(), move_stmt_r(), ref_indep_loop_p(), replace_conditional_candidate(), same_phi_alternatives_1(), simple_mem_ref_in_stmt(), simplify_using_outer_evolutions(), split_edge(), stmt_kills_ref_p(), strlen_optimize_stmt(), tm_log_emit_restores(), verify_dominators(), and zero_one_operation().
| void dump_bb_info | ( | FILE * | outf, |
| basic_block | bb, | ||
| int | indent, | ||
| int | flags, | ||
| bool | do_header, | ||
| bool | do_footer | ||
| ) |
Dumps cfg related information about basic block BB to OUTF. If HEADER is true, dump things that appear before the instructions contained in BB. If FOOTER is true, dump things that appear after. Flags are the TDF_* masks as documented in dumpfile.h. NB: With TDF_DETAILS, it is assumed that cfun is available, so that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE.
| void dump_edge_info | ( | FILE * | , |
| edge | , | ||
| int | , | ||
| int | |||
| ) |
| void dump_flow_info | ( | FILE * | , |
| int | |||
| ) |
Referenced by dump_flow_info().
| bool edge_probability_reliable_p | ( | const_edge | ) |
|
inlinestatic |
Return 1 if we should continue to iterate. Return 0 otherwise. *Edge P is set to the next edge if we are to continue to iterate and NULL otherwise.
Referenced by insert_store().
|
inlinestatic |
Return the edge pointed to by the iterator `i'.
Referenced by insert_store(), and link_roots().
|
inlinestatic |
Is the iterator `i' at the end of the sequence?
Referenced by insert_store(), and link_roots().
|
inlinestatic |
Return an iterator pointing to the last element of an edge vector.
|
inlinestatic |
Advance the iterator to the next element.
Referenced by find_edge(), find_implicit_sets(), get_all_loop_exits(), gimple_expand_cfg(), insert_store(), link_roots(), post_order_compute(), print_loops(), remove_ctrl_stmt_and_useless_edges(), rewrite_trees(), rtl_verify_bb_layout(), and try_forward_edges().
|
inlinestatic |
Is the iterator `i' at one position before the end of the sequence?
Referenced by post_order_compute().
|
inlinestatic |
Move the iterator to the previous element.
|
inlinestatic |
Return an edge pointed to by the iterator. Do it safely so that NULL is returned when the iterator is pointing at the end of the sequence.
Referenced by find_edge(), find_implicit_sets(), gimple_expand_cfg(), and move_stmt_r().
|
inlinestatic |
Return an iterator pointing to the start of an edge vector.
| void emit_barrier_after_bb | ( | basic_block | bb | ) |
| void expunge_block | ( | basic_block | ) |
| edge find_edge | ( | basic_block | , |
| basic_block | |||
| ) |
| int find_edge_index | ( | struct edge_list * | , |
| basic_block | , | ||
| basic_block | |||
| ) |
|
inlinestatic |
Return the fallthru edge in EDGES if it exists, NULL otherwise.
Referenced by cfg_layout_initialize(), and find_active_insn_after().
| void find_many_sub_basic_blocks | ( | sbitmap | ) |
In cfgbuild.c.
| void find_unreachable_blocks | ( | void | ) |
In cfganal.c
Find unreachable blocks. An unreachable block will have 0 in the reachable bit in block->flags. A nonzero value indicates the block is reachable.
Clear all the reachability flags.
Add our starting points to the worklist. Almost always there will
be only one. It isn't inconceivable that we might one day directly
support Fortran alternate entry points. Mark the block reachable.
Iterate: find everything reachable from what we've already seen.
References basic_block_def::flags.
Referenced by replace_locals_op().
| gcov_working_set_t* find_working_set | ( | unsigned | pct_times_10 | ) |
| basic_block first_dom_son | ( | enum | cdi_direction, |
| basic_block | |||
| ) |
Referenced by do_partial_partial_insertion(), get_immediate_dominator(), and glb_enum_p().
| bool fixup_abnormal_edges | ( | void | ) |
This is used by a few passes that emit some instructions after abnormal calls, moving the basic block's end, while they in fact do want to emit them on the fallthru edge. Look for abnormal call edges, find backward the call in the block and insert the instructions on the edge instead. Similarly, handle instructions throwing exceptions internally. Return true when instructions have been found and inserted on edges.
Look for cases we are interested in - calls or instructions causing
exceptions. Get past the new insns generated. Allow notes, as the insns
may be already deleted. Sometimes there's still the return value USE.
If it's placed after a trapping call (i.e. that
call is the last insn anyway), we have no fallthru
edge. Simply delete this use and don't try to insert
on the non-existent edge. We're not deleting it, we're moving it.
It may be that we don't find any trapping insn. In this
case we discovered quite late that the insn that had been
marked as can_throw_internal in fact couldn't trap at all.
So we should in fact delete the EH edges out of the block.
| void fixup_partitions | ( | void | ) |
Perform cleanup on the hot/cold bb partitioning after optimization passes that modify the cfg.
Delete any blocks that became unreachable and weren't
already cleaned up, for example during edge forwarding
and convert_jumps_to_returns. This will expose more
opportunities for fixing the partition boundaries here.
Also, the calculation of the dominance graph during verification
will assert if there are unreachable nodes. If there are partitions, do a sanity check on them: A basic block in
 a cold partition cannot dominate a basic block in a hot partition.
Fixup any that now violate this requirement, as a result of edge
forwarding and unreachable block deletion. Â Do the partition fixup after all necessary blocks have been converted to
cold, so that we only update the region crossings the minimum number of
places, which can require forcing edges to be non fallthru.
References error(), get_insns(), basic_block_def::index, and print_rtl_with_bb().
| int flow_find_cross_jump | ( | basic_block | bb1, |
| basic_block | bb2, | ||
| rtx * | f1, | ||
| rtx * | f2, | ||
| enum replace_direction * | dir_p | ||
| ) |
Look through the insns at the end of BB1 and BB2 and find the longest sequence that are either equivalent, or allow forward or backward replacement. Store the first insns for that sequence in *F1 and *F2 and return the sequence length. DIR_P indicates the allowed replacement direction on function entry, and the actual replacement direction on function exit. If NULL, only equivalent sequences are allowed. To simplify callers of this function, if the blocks match exactly, store the head of the blocks in *F1 and *F2.
Skip simple jumps at the end of the blocks. Complex jumps still
need to be compared for equivalence, which we'll do below. Count everything except for unconditional jump as insn.
In the following example, we can replace all jumps to C by jumps to A.
This removes 4 duplicate insns.
[bb A] insn1 [bb C] insn1
insn2 insn2
[bb B] insn3 insn3
insn4 insn4
jump_insn jump_insn
We could also replace all jumps to A by jumps to C, but that leaves B
alive, and removes only 2 duplicate insns. In a subsequent crossjump
step, all jumps to B would be replaced with jumps to the middle of C,
achieving the same result with more effort.
So we allow only the first possibility, which means that we don't allow
fallthru in the block that's being replaced. Don't begin a cross-jump with a NOTE insn.
Don't allow the insn after a compare to be shared by
cross-jumping unless the compare is also shared. Include preceding notes and labels in the cross-jump. One,
this may bring us to the head of the blocks as requested above.
Two, it keeps line number notes as matched as may be.
| int flow_find_head_matching_sequence | ( | basic_block | bb1, |
| basic_block | bb2, | ||
| rtx * | f1, | ||
| rtx * | f2, | ||
| int | stop_after | ||
| ) |
Like flow_find_cross_jump, except start looking for a matching sequence from the head of the two blocks. Do not include jumps at the end. If STOP_AFTER is nonzero, stop after finding that many matching instructions.
Ignore notes, except NOTE_INSN_EPILOGUE_BEG.
A sanity check to make sure we're not merging insns with different
effects on EH. If only one of them ends a basic block, it shouldn't
have an EH edge; if both end a basic block, there should be the same
number of EH edges. Don't begin a cross-jump with a NOTE insn.
Don't allow a compare to be shared by cross-jumping unless the insn
after the compare is also shared.
| basic_block force_nonfallthru_and_redirect | ( | edge | , |
| basic_block | , | ||
| rtx | |||
| ) |
| bool forwarder_block_p | ( | const_basic_block | ) |
Referenced by add_forwarder_blocks().
| void free_aux_for_blocks | ( | void | ) |
Free data allocated in block_aux_obstack and clear AUX pointers of all blocks.
References alloc_aux_for_edge(), and basic_block_def::succs.
| void free_aux_for_edges | ( | void | ) |
Free data allocated in edge_aux_obstack and clear AUX pointers of all edges.
| unsigned int free_bb_for_insn | ( | void | ) |
Release the basic_block_for_insn array.
References RTL_PASS, and TV_NONE.
Referenced by compute_bb_for_insn().
| void free_dominance_info | ( | enum | cdi_direction | ) |
| void free_edge_list | ( | struct edge_list * | ) |
Referenced by pre_insert_copies().
| void free_original_copy_tables | ( | void | ) |
Free the data structures to maintain mapping between blocks and its copies.
References hash_table< Descriptor, Allocator >::find(), basic_block_def::index, htab_bb_copy_original_entry::index1, and htab_bb_copy_original_entry::index2.
Referenced by ssa_name_has_uses_outside_loop_p(), vect_create_cond_for_alias_checks(), and vect_update_ivs_after_vectorizer().
| vec<basic_block> get_all_dominated_blocks | ( | enum | cdi_direction, |
| basic_block | |||
| ) |
| basic_block get_bb_copy | ( | basic_block | ) |
| basic_block get_bb_original | ( | basic_block | ) |
Referenced by insert_var_expansion_initialization().
| vec<basic_block> get_dominated_by | ( | enum | cdi_direction, |
| basic_block | |||
| ) |
Referenced by split_edge_and_insert().
| vec<basic_block> get_dominated_by_region | ( | enum cdi_direction | dir, |
| basic_block * | region, | ||
| unsigned | n_region | ||
| ) |
Returns the list of basic blocks that are immediately dominated (in direction DIR) by some block between N_REGION ones stored in REGION, except for blocks in the REGION itself.
References basic_block_def::dom, dom_convert_dir_to_idx(), DOM_NO_FAST_QUERY, DOM_OK, et_set_father(), et_split(), and et_node::son.
Referenced by move_stmt_r().
| vec<basic_block> get_dominated_to_depth | ( | enum | cdi_direction, |
| basic_block | , | ||
| int | |||
| ) |
| basic_block get_immediate_dominator | ( | enum | cdi_direction, |
| basic_block | |||
| ) |
Referenced by dfs_enumerate_from(), do_partial_partial_insertion(), find_pdom(), move_stmt_r(), select_best_block(), and split_edge().
| rtx get_last_bb_insn | ( | basic_block | ) |
| void gimple_predict_edge | ( | edge | , |
| enum | br_predictor, | ||
| int | |||
| ) |
| bool gimple_predicted_by_p | ( | const_basic_block | , |
| enum | br_predictor | ||
| ) |
| void gt_ggc_mx | ( | edge_def * | e | ) |
Garbage collection and PCH support for edge_def.
| void gt_pch_nx | ( | edge_def * | e | ) |
Referenced by vec< T, A, vl_embed >::embedded_size(), and gimplify_build3().
| void gt_pch_nx | ( | edge_def * | e, |
| gt_pointer_operator | , | ||
| void * | |||
| ) |
| void guess_outgoing_edge_probabilities | ( | basic_block | ) |
| void init_flow | ( | struct function * | ) |
In cfg.c
| void init_rtl_bb_info | ( | basic_block | ) |
| void initialize_original_copy_tables | ( | void | ) |
Initialize the data structures to maintain mapping between blocks and its copies.
Referenced by ssa_name_has_uses_outside_loop_p(), vect_create_cond_for_alias_checks(), and vect_update_ivs_after_vectorizer().
Referenced by cfg_layout_can_merge_blocks_p(), convert_regs_entry(), insert_rtx_to_part_on_edge(), and reg_killed_on_edge().
| bool inside_basic_block_p | ( | const_rtx | ) |
|
inlinestatic |
Return inverse probability for PROB.
| int inverted_post_order_compute | ( | int * | ) |
Referenced by dom_walker::walk().
| void iterate_fix_dominators | ( | enum cdi_direction | dir, |
| vec< basic_block > | bbs, | ||
| bool | conservative | ||
| ) |
Recompute dominance information for basic blocks in the set BBS. The function assumes that the immediate dominators of all the other blocks in CFG are correct, and that there are no unreachable blocks. If CONSERVATIVE is true, we additionally assume that all the ancestors of a block of BBS in the current dominance tree dominate it.
We only support updating dominators. There are some problems with
updating postdominators (need to add fake edges from infinite loops
and noreturn functions), and since we do not currently use
iterate_fix_dominators for postdominators, any attempt to handle these
problems would be unused, untested, and almost surely buggy. We keep
the DIR argument for consistency with the rest of the dominator analysis
interface. The algorithm we use takes inspiration from the following papers, although
the details are quite different from any of them:
[1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
Dominator Tree of a Reducible Flowgraph
[2] V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
dominator trees
[3] K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
Algorithm
First, we use the following heuristics to decrease the size of the BBS
set:
a) if BB has a single predecessor, then its immediate dominator is this
predecessor
additionally, if CONSERVATIVE is true:
b) if all the predecessors of BB except for one (X) are dominated by BB,
then X is the immediate dominator of BB
c) if the nearest common ancestor of the predecessors of BB is X and
X -> BB is an edge in CFG, then X is the immediate dominator of BB
Then, we need to establish the dominance relation among the basic blocks
in BBS. We split the dominance tree by removing the immediate dominator
edges from BBS, creating a forest F. We form a graph G whose vertices
are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
X' -> Y in CFG such that X' belongs to the tree of the dominance forest
whose root is X. We then determine dominance tree of G. Note that
for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
In this step, we can use arbitrary algorithm to determine dominators.
We decided to prefer the algorithm [3] to the algorithm of
Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
10 during gcc bootstrap), and [3] should perform better in this case.
Finally, we need to determine the immediate dominators for the basic
blocks of BBS. If the immediate dominator of X in G is Y, then
the immediate dominator of X in CFG belongs to the tree of F rooted in
Y. We process the dominator tree T of G recursively, starting from leaves.
Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
subtrees of the dominance tree of CFG rooted in X_i are already correct.
Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}. We make
the following observations:
(i) the immediate dominator of all blocks in a strongly connected
component of G' is the same
(ii) if X has no predecessors in G', then the immediate dominator of X
is the nearest common ancestor of the predecessors of X in the
subtree of F rooted in Y
Therefore, it suffices to find the topological ordering of G', and
process the nodes X_i in this order using the rules (i) and (ii).
Then, we contract all the nodes X_i with Y in G, so that the further
steps work correctly. Split the tree now. If the idoms of blocks in BBS are not
conservatively correct, setting the dominators using the
heuristics in prune_bbs_to_update_dominators could
create cycles in the dominance "tree", and cause ICE. Construct the graph G.
If the dominance tree is conservatively correct, split it now.
Do not include parallel edges to G.
Find the dominator tree of G.
Finally, traverse the tree and find the immediate dominators.
| void link_block | ( | basic_block | , |
| basic_block | |||
| ) |
Referenced by create_check_block_twin().
| edge make_edge | ( | basic_block | , |
| basic_block | , | ||
| int | |||
| ) |
Referenced by copy_phi_args(), create_empty_if_region_on_edge(), expand_transaction(), input_cfg(), remove_conditions_and_labels(), remove_fake_exit_edges(), sched_extend_ready_list(), split_function(), stmt_starts_bb_p(), tm_memopt_clear_visited(), unchecked_make_edge(), and update_dominators_in_loop().
| edge make_single_succ_edge | ( | basic_block | , |
| basic_block | , | ||
| int | |||
| ) |
Referenced by remove_fake_predecessors(), and sched_extend_ready_list().
| bool mark_dfs_back_edges | ( | void | ) |
Mark the back edges in DFS traversal.
Return nonzero if a loop (natural or otherwise) is present.
Inspired by Depth_First_Search_PP described in:
Advanced Compiler Design and Implementation
Steven Muchnick
Morgan Kaufmann, 1997
and heavily borrowed from pre_and_rev_post_order_compute. Allocate the preorder and postorder number arrays.
Allocate stack for back-tracking up CFG.
Allocate bitmap to track nodes that have been visited.
None of the nodes in the CFG have been visited yet.
Push the first edge on to the stack.
Look at the edge on the top of the stack.
Check if the edge destination has been visited yet.
Mark that we have visited the destination.
Since the DEST node has been visited for the first
time, check its successors.
Referenced by draw_cfg_nodes().
| bool maybe_hot_bb_p | ( | struct function * | , |
| const_basic_block | |||
| ) |
In predict.c
| bool maybe_hot_edge_p | ( | edge | ) |
Referenced by optimize_function_for_speed_p(), and optimize_loop_nest_for_size_p().
| bool mfb_keep_just | ( | edge | ) |
| basic_block nearest_common_dominator | ( | enum | cdi_direction, |
| basic_block | , | ||
| basic_block | |||
| ) |
Referenced by bb_dom_dfs_in(), occ_new(), and verify_dominators().
| basic_block nearest_common_dominator_for_set | ( | enum | cdi_direction, |
| bitmap | |||
| ) |
Referenced by same_phi_alternatives_1().
| basic_block next_dom_son | ( | enum | cdi_direction, |
| basic_block | |||
| ) |
Referenced by do_partial_partial_insertion(), get_immediate_dominator(), and glb_enum_p().
| bool optimize_bb_for_size_p | ( | const_basic_block | ) |
Referenced by create_outofssa_var_map().
| bool optimize_bb_for_speed_p | ( | const_basic_block | ) |
| bool optimize_edge_for_size_p | ( | edge | ) |
Referenced by optimize_bb_for_size_p().
| bool optimize_edge_for_speed_p | ( | edge | ) |
Referenced by find_traces_1_round().
| bool optimize_loop_for_size_p | ( | struct loop * | ) |
Referenced by tree_ssa_unswitch_loops().
| bool optimize_loop_for_speed_p | ( | struct loop * | ) |
Referenced by optimize_insn_for_size_p(), optimize_insn_for_speed_p(), and rewrite_use_compare().
| bool optimize_loop_nest_for_size_p | ( | struct loop * | ) |
| bool optimize_loop_nest_for_speed_p | ( | struct loop * | ) |
| int post_order_compute | ( | int * | post_order, |
| bool | include_entry_exit, | ||
| bool | delete_unreachable | ||
| ) |
Compute reverse top sort order. This is computing a post order numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is true, unreachable blocks are deleted.
Allocate stack for back-tracking up CFG.
Allocate bitmap to track nodes that have been visited.
None of the nodes in the CFG have been visited yet.
Push the first edge on to the stack.
Look at the edge on the top of the stack.
Check if the edge destination has been visited yet.
Mark that we have visited the destination.
Since the DEST node has been visited for the first
time, check its successors. Delete the unreachable blocks if some were found and we are
supposed to do it.
References ei_next(), ei_one_before_end_p(), and basic_block_def::index.
| int pre_and_rev_post_order_compute | ( | int * | pre_order, |
| int * | rev_post_order, | ||
| bool | include_entry_exit | ||
| ) |
Like pre_and_rev_post_order_compute_fn but operating on the current function and asserting that all nodes were visited.
The number of nodes visited should be the number of blocks.
The number of nodes visited should be the number of blocks minus
the entry and exit blocks which are not visited here.
References bitmap_bit_p(), flow_dfs_compute_reverse_add_bb(), basic_block_def::index, basic_block_def::preds, depth_first_search_dsS::sp, edge_def::src, depth_first_search_dsS::stack, and depth_first_search_dsS::visited_blocks.
| int pre_and_rev_post_order_compute_fn | ( | struct function * | fn, |
| int * | pre_order, | ||
| int * | rev_post_order, | ||
| bool | include_entry_exit | ||
| ) |
Compute the depth first search order of FN and store in the array PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the reverse completion number for each node. Returns the number of nodes visited. A depth first search tries to get as far away from the starting point as quickly as possible. In case the function has unreachable blocks the number of nodes visited does not include them. pre_order is a really a preorder numbering of the graph. rev_post_order is really a reverse postorder numbering of the graph.
Allocate stack for back-tracking up CFG.
Allocate bitmap to track nodes that have been visited.
None of the nodes in the CFG have been visited yet.
Push the first edge on to the stack.
Look at the edge on the top of the stack.
Check if the edge destination has been visited yet.
Mark that we have visited the destination.
Since the DEST node has been visited for the first
time, check its successors. There are no successors for the DEST node so assign
its reverse completion number. There are no more successors for the SRC node
so assign its reverse completion number.
|
read |
In lcm.c
Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and delete vectors for edge based LCM. Returns an edgelist which is used to map the insert vector to what edge an expression should be inserted on.
Compute global availability.
Compute global anticipatability.
Compute earliestness.
Allocate an extra element for the exit block in the laterin vector.
|
read |
Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the insert and delete vectors for edge based reverse LCM. Returns an edgelist which is used to map the insert vector to what edge an expression should be inserted on.
Compute global anticipatability.
Compute farthestness.
Allocate an extra element for the entry block.
| void predict_edge_def | ( | edge | e, |
| enum br_predictor | predictor, | ||
| enum prediction | taken | ||
| ) |
Predict edge E by given predictor if possible.
Referenced by apply_return_prediction(), and tree_bb_level_predictions().
| bool predictable_edge_p | ( | edge | ) |
| void print_edge_list | ( | FILE * | , |
| struct edge_list * | |||
| ) |
Referenced by compute_insert_delete().
| bool probably_never_executed_bb_p | ( | struct function * | , |
| const_basic_block | |||
| ) |
Referenced by sanitize_hot_paths().
Referenced by sanitize_hot_paths().
| bool purge_all_dead_edges | ( | void | ) |
Search all basic blocks for potentially dead edges and purge them. Return true if some edge has been eliminated.
Referenced by split_live_ranges_for_shrink_wrap().
| bool purge_dead_edges | ( | basic_block | ) |
| basic_block recompute_dominator | ( | enum | cdi_direction, |
| basic_block | |||
| ) |
Referenced by first_mem_ref_loc_1::operator()(), and prune_bbs_to_update_dominators().
| void redirect_edge_pred | ( | edge | , |
| basic_block | |||
| ) |
Referenced by expand_transaction().
| void redirect_edge_succ | ( | edge | , |
| basic_block | |||
| ) |
Referenced by first_mem_ref_loc_1::operator()().
| edge redirect_edge_succ_nodup | ( | edge | , |
| basic_block | |||
| ) |
Referenced by create_empty_if_region_on_edge(), and graphite_create_new_loop_guard().
| void redirect_immediate_dominators | ( | enum cdi_direction | dir, |
| basic_block | bb, | ||
| basic_block | to | ||
| ) |
Redirect all edges pointing to BB to TO.
| void relink_block_chain | ( | bool | ) |
| void remove_edge_raw | ( | edge | ) |
Referenced by remove_branch().
| void remove_fake_edges | ( | void | ) |
This routine will remove all fake edges from the flow graph. If we remove all fake successors, it will automatically remove all fake predecessors.
References flow_dfs_compute_reverse_add_bb(), and flow_dfs_compute_reverse_init().
| void remove_fake_exit_edges | ( | void | ) |
This routine will remove all fake edges to the EXIT_BLOCK.
References dfs_find_deadend(), flow_dfs_compute_reverse_add_bb(), flow_dfs_compute_reverse_execute(), and make_edge().
Referenced by pre_insert_copies().
| void remove_predictions_associated_with_edge | ( | edge | ) |
| void rtl_make_eh_edge | ( | sbitmap | , |
| basic_block | , | ||
| rtx | |||
| ) |
| void rtl_predict_edge | ( | edge | , |
| enum | br_predictor, | ||
| int | |||
| ) |
| bool rtl_predicted_by_p | ( | const_basic_block | , |
| enum | br_predictor | ||
| ) |
| void rtl_profile_for_bb | ( | basic_block | ) |
In cfgexpand.c.
Referenced by move_insn_for_shrink_wrap().
| void rtl_profile_for_edge | ( | edge | ) |
| void scale_bbs_frequencies_gcov_type | ( | basic_block * | bbs, |
| int | nbbs, | ||
| gcov_type | num, | ||
| gcov_type | den | ||
| ) |
Multiply all frequencies of basic blocks in array BBS of length NBBS by NUM/DEN, in gcov_type arithmetic. More accurate than previous function but considerably slower.
| void scale_bbs_frequencies_int | ( | basic_block * | , |
| int | , | ||
| int | , | ||
| int | |||
| ) |
| void set_bb_copy | ( | basic_block | , |
| basic_block | |||
| ) |
| void set_bb_original | ( | basic_block | , |
| basic_block | |||
| ) |
| void set_dom_info_availability | ( | enum | cdi_direction, |
| enum | dom_state | ||
| ) |
| void set_immediate_dominator | ( | enum cdi_direction | dir, |
| basic_block | bb, | ||
| basic_block | dominated_by | ||
| ) |
Set the immediate dominator of the block possibly removing existing edge. NULL can be used to remove any edge.
Referenced by create_empty_if_region_on_edge(), determine_dominators_for_sons(), graphite_create_new_loop_guard(), first_mem_ref_loc_1::operator()(), prune_bbs_to_update_dominators(), recompute_dominator(), redirect_edge_succ_nodup(), remove_conditions_and_labels(), sched_extend_ready_list(), split_edge(), tidy_fallthru_edges(), update_dominators_in_loop(), and verify_dominators().
|
inlinestatic |
Returns the single predecessor block of basic block BB. Aborts if BB does not have exactly one predecessor.
Referenced by create_loads_and_stores_for_name(), find_comparison_dom_walker::find_comparison_dom_walker(), get_ancestor_addr_info(), maybe_instrument_assignment(), redirect_edge_succ_nodup(), split_edge(), tidy_fallthru_edges(), and verify_dominators().
| basic_block* single_pred_before_succ_order | ( | void | ) |
Returns the list of basic blocks in the function in an order that guarantees that if a block X has just a single predecessor Y, then Y is after X in the ordering.
Walk the predecessors of x as long as they have precisely one
predecessor and add them to the list, so that they get stored
after x.
|
inlinestatic |
Returns the single predecessor edge of basic block BB. Aborts if BB does not have exactly one predecessor.
Referenced by create_if_region_on_edge(), rewrite_trees(), and single_pred_cond_non_loop_exit().
|
inlinestatic |
Returns true if BB has precisely one predecessor.
Referenced by cond_move_convert_if_block(), find_dom(), find_traces_1_round(), get_ancestor_addr_info(), rewrite_trees(), simple_mem_ref_in_stmt(), threadedge_finalize_values(), update_dominators_in_loop(), vect_can_advance_ivs_p(), and verify_dominators().
|
inlinestatic |
Returns the single successor block of basic block BB. Aborts if BB does not have exactly one successor.
Referenced by cond_move_convert_if_block(), create_empty_if_region_on_edge(), create_loop_fn(), dependent_clean(), expand_omp_atomic_load(), expand_omp_sections(), find_traces_1_round(), instrument_memory_accesses(), ipa_tm_scan_irr_block(), redirect_edge_succ_nodup(), remap_ssa_name(), remove_exit_barriers(), split_bbs_on_noreturn_calls(), split_edge(), and tidy_fallthru_edges().
|
inlinestatic |
Returns the single successor edge of basic block BB. Aborts if BB does not have exactly one successor.
Referenced by cond_exec_find_if_block(), cond_move_convert_if_block(), create_empty_if_region_on_edge(), create_if_region_on_edge(), create_loads_and_stores_for_name(), create_loop_fn(), create_temp_arrays(), expand_omp_for(), find_traces_1_round(), graphite_create_new_loop_guard(), move_insn_for_shrink_wrap(), phi_alternatives_equal(), print_graphite_scop_statistics(), split_edge(), translate_clast_for_loop(), unsplit_all_eh(), update_dominators_in_loop(), value_replacement(), and verify_loop_closed_ssa().
|
inlinestatic |
Returns true if BB has precisely one successor.
Referenced by cond_move_convert_if_block(), create_preheader(), dup_block_and_redirect(), find_dom(), find_traces_1_round(), move_insn_for_shrink_wrap(), print_graphite_scop_statistics(), remap_ssa_name(), threadedge_finalize_values(), and unsplit_all_eh().
| basic_block split_edge_and_insert | ( | edge | , |
| rtx | |||
| ) |
| edge try_redirect_by_replacing_jump | ( | edge | , |
| basic_block | , | ||
| bool | |||
| ) |
| edge unchecked_make_edge | ( | basic_block | , |
| basic_block | , | ||
| int | |||
| ) |
Referenced by fixup_new_cold_bb(), and unchecked_make_edge().
| void unlink_block | ( | basic_block | ) |
Referenced by create_check_block_twin().
| void update_bb_for_insn | ( | basic_block | ) |
Referenced by create_check_block_twin().
| void update_bb_profile_for_threading | ( | basic_block | bb, |
| int | edge_frequency, | ||
| gcov_type | count, | ||
| edge | taken_edge | ||
| ) |
An edge originally destinating BB of FREQUENCY and COUNT has been proved to leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be redirected to destination of TAKEN_EDGE. This function may leave the profile inconsistent in the case TAKEN_EDGE frequency or count is believed to be lower than FREQUENCY or COUNT respectively.
Compute the probability of TAKEN_EDGE being reached via threaded edge.
Watch for overflows. Now rescale the probabilities.
Protect from overflow due to additional scaling.
References edge_def::probability, and basic_block_def::succs.
| void update_br_prob_note | ( | basic_block | ) |
Referenced by add_labels_and_missing_jumps(), and make_pass_into_cfg_layout_mode().
| void verify_dominators | ( | enum | cdi_direction | ) |
Referenced by cleanup_tree_cfg_1().
| void verify_edge_list | ( | FILE * | , |
| struct edge_list * | |||
| ) |
Referenced by compute_insert_delete().
Variable Documentation
| edge mfb_kj_edge |
In cfgloopmanip.c.
A callback for make_forwarder block, to redirect all edges except for MFB_KJ_EDGE to the entry part. E is the edge for that we should decide whether to redirect it.
| struct gcov_ctr_summary* profile_info |
Counter summary from the last set of coverage counts read by profile.c.
Counter summary from the last set of coverage counts read.
Referenced by bb_in_region_p().
