#include "config.h"#include "system.h"#include "coretypes.h"#include "tm.h"#include "rtl.h"#include "function.h"#include "basic-block.h"#include "cfgloop.h"#include "diagnostic-core.h"#include "flags.h"#include "tree.h"#include "gimple.h"#include "gimple-ssa.h"#include "pointer-set.h"#include "ggc.h"#include "dumpfile.h"
Macros | |
| #define | HEAVY_EDGE_RATIO 8 |
| #define | HEAVY_EDGE_MIN_SAMPLES 10 |
Variables | |
| static struct pointer_set_t * | mfb_reis_set |
Macro Definition Documentation
| #define HEAVY_EDGE_MIN_SAMPLES 10 |
Minimum number of samples for that we apply find_subloop_latch_edge_by_profile heuristics.
| #define HEAVY_EDGE_RATIO 8 |
Ratio of frequencies of edges so that one of more latch edges is considered to belong to inner loop with same header.
Function Documentation
| void add_bb_to_loop | ( | ) |
Adds basic block BB to LOOP.
Referenced by expand_transaction(), predicted_by_p(), redirect_edge_succ_nodup(), split_function(), and tidy_fallthru_edges().
|
read |
Allocates and returns new loop structure.
References alloc_loop(), ENTRY_BLOCK_PTR_FOR_FUNCTION, EXIT_BLOCK_PTR_FOR_FUNCTION, loop::header, loops::larray, loop::latch, n_basic_blocks_for_function, loop::num_nodes, loops::tree_root, and vec_alloc().
Referenced by alloc_loop(), create_empty_if_region_on_edge(), and remap_decl_1().
| int bb_loop_depth | ( | ) |
Returns the loop depth of the loop BB belongs to.
Referenced by memref_referenced_p(), and select_best_block().
| bool bb_loop_header_p | ( | ) |
Returns whether HEADER is a loop header.
If we have an abnormal predecessor, do not consider the loop (not worth the problems).
Look for back edges where a predecessor is dominated by this block. A natural loop has a single entry node (header) that dominates all the nodes in the loop. It also has single back edge to the header from a latch node.
|
static |
Cancels the LOOP; it must be innermost one.
Move blocks up one level (they should be removed as soon as possible).
References error(), get_loop_body_with_size(), loop::header, n_basic_blocks, loop::num, and loop::num_nodes.
| void delete_loop | ( | ) |
Removes LOOP from structures and frees its data.
Remove the loop from structure.
Remove loop from loops array.
Free loop data.
| void disambiguate_loops_with_multiple_latches | ( | void | ) |
Split loops with multiple latch edges.
|
static |
LOOP may have several latch edges. Transform it into (possibly several) loops with single latch edge.
We eliminate the multiple latches by splitting the header to the forwarder block F and the rest R, and redirecting the edges. There are two cases:
1) If there is a latch edge E that corresponds to a subloop (we guess that based on profile – if it is taken much more often than the remaining edges; and on trees, using the information about induction variables of the loops), we redirect E to R, all the remaining edges to F, then rescan the loops and try again for the outer loop. 2) If there is no such edge, we redirect all latch edges to F, and the entry edges to R, thus making F the single latch of the loop.
During latch merging, we may need to redirect the entry edges to a new block. This would cause problems if the entry edge was the one from the entry block. To avoid having to handle this case specially, split such entry edge.
References ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, flow_loop_nested_p(), and basic_block_def::loop_father.
|
static |
Dumps information about the exit in *SLOT to FILE. Callback for htab_traverse.
References EDGE_COUNT, EXIT_BLOCK_PTR, gcc_assert, get_loop_body(), loop::latch, and loop::num_nodes.
| void dump_recorded_exits | ( | FILE * | ) |
Dumps the recorded exits of loops to FILE.
| void dump_recorded_exits | ( | ) |
References loop_exit::e, gcc_assert, and basic_block_def::loop_father.
|
static |
Records the vector of superloops of the loop LOOP, whose immediate superloop is FATHER.
|
static |
Fills dominance descendants inside LOOP of the basic block BB into array TOVISIT from index *TV.
References BITMAP_ALLOC, bitmap_set_bit, edge_def::dest, EXIT_BLOCK_PTR, flow_bb_inside_loop_p(), FOR_EACH_EDGE, gcc_assert, loop::header, basic_block_def::index, loop::latch, loop::num_nodes, basic_block_def::succs, and visited.
Referenced by get_loop_body().
|
read |
Finds nearest common ancestor in loop tree for given loops.
Referenced by compute_always_reached(), fix_loop_placement(), gbb_loop(), redirect_edge_succ_nodup(), and tidy_fallthru_edges().
|
static |
If we can determine that one of the several latch edges of LOOP behaves as a latch edge of a separate subloop, returns this edge. Otherwise returns NULL.
We consider ivs to guess the latch edge only in SSA. Perhaps we should use cfghook for this, but it is hard to imagine it would be useful elsewhere.
|
static |
Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based on the structure of induction variables. Returns this edge, or NULL if we do not find any.
We are quite conservative, and look just for an obvious simple innermost loop (which is the case where we would lose the most performance by not disambiguating the loop). More precisely, we look for the following situation: The source of the chosen latch edge dominates sources of all the other latch edges. Additionally, the header does not contain a phi node such that the argument from the chosen edge is equal to the argument from another edge.
Find the candidate for the latch edge.
Verify that it dominates all the latch edges.
Check for a phi node that would deny that this is a latch edge of a subloop.
Ignore the values that are not changed inside the subloop.
|
static |
If the profile info is available, finds an edge in LATCHES that much more frequent than the remaining edges. Returns such an edge, or NULL if we do not find one.
We do not use guessed profile here, only the measured one. The guessed profile is usually too flat and unreliable for this (and it is mostly based on the loop structure of the program, so it does not make much sense to derive the loop structure from it).
References CDI_DOMINATORS, dominated_by_p(), dump_file, flow_bb_inside_loop_p(), FOR_EACH_VEC_ELT, gimple_bb(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), loop::header, NULL, PHI_ARG_DEF_FROM_EDGE, edge_def::src, SSA_NAME_DEF_STMT, and TREE_CODE.
| bool flow_bb_inside_loop_p | ( | ) |
Return nonzero if basic block BB belongs to LOOP.
Referenced by analyze_evolution_in_loop(), compute_always_reached(), create_expression_by_pieces(), determine_base_object(), determine_unroll_factor(), fill_sons_in_loop(), find_loop_niter(), find_subloop_latch_edge_by_profile(), gather_scalar_reductions(), glb_enum_p(), record_loop_exits(), split_edge_and_insert(), vect_analyze_slp(), vect_create_cond_for_alias_checks(), and vect_mark_relevant().
| void flow_loop_dump | ( | const struct loop * | loop, |
| FILE * | file, | ||
| void(*)(const struct loop *, FILE *, int) | loop_dump_aux, | ||
| int | verbose | ||
| ) |
Dump the loop information specified by LOOP to the stream FILE using auxiliary dump callback function LOOP_DUMP_AUX if non null.
Referenced by rewrite_uses().
| void flow_loop_free | ( | ) |
Free data allocated for LOOP.
Break the list of the loop exit records. They will be freed when the corresponding edge is rescanned or removed, and this avoids accessing the (already released) head of the list stored in the loop structure.
References loop_exit::next, and loop_exit::prev.
| bool flow_loop_nested_p | ( | ) |
Return nonzero if the nodes of LOOP are a subset of OUTER.
Referenced by chrec_contains_undetermined(), chrec_replace_initial_condition(), disambiguate_multiple_latches(), fix_bb_placement(), fix_loop_placement(), follow_ssa_edge_inner_loop_phi(), hide_evolution_in_other_loops_than_loop(), loop_phi_node_p(), and outermost_invariant_loop().
| int flow_loop_nodes_find | ( | ) |
Find the nodes contained within the LOOP with header HEADER. Return the number of nodes within the loop.
References loop_exit::e, FOR_EACH_EDGE, basic_block_def::loop_father, basic_block_def::preds, and edge_def::src.
| void flow_loop_tree_node_add | ( | ) |
Add LOOP to the loop hierarchy tree where FATHER is father of the added loop. If LOOP has some children, take care of that their pred field will be initialized correctly.
| void flow_loop_tree_node_remove | ( | ) |
Remove LOOP from the loop hierarchy tree.
Remove loop from the list of sons.
|
static |
Natural loop discovery code for 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/.
|
static |
Dump loop related CFG information.
References edge_def::dest, FOR_EACH_EDGE, basic_block_def::index, and basic_block_def::succs.
| void flow_loops_dump | ( | FILE * | file, |
| void(*)(const struct loop *, FILE *, int) | loop_dump_aux, | ||
| int | verbose | ||
| ) |
Dump the loop information about loops to the stream FILE, using auxiliary dump callback function LOOP_DUMP_AUX if non null.
Referenced by analyze_function().
|
read |
Find all the natural loops in the function and save in LOOPS structure and recalculate loop_father information in basic block structures. If LOOPS is non-NULL then the loop structures for already recorded loops will be re-used and their number will not change. We assume that no stale loops exist in LOOPS. When LOOPS is NULL it is allocated and re-built from scratch. Return the built LOOPS structure.
Ensure that the dominators are computed.
Ensure that loop exits were released.
Taking care of this degenerate case makes the rest of this code simpler.
The root loop node contains all basic-blocks.
Compute depth first search order of the CFG so that outer natural loops will be found before inner natural loops.
Gather all loop headers in reverse completion order and allocate loop structures for loops that are not already present.
The current active loop tree has valid loop-fathers for
header blocks. If we found an existing loop remove it from the
loop tree. It is going to be inserted again
below. Otherwise allocate a new loop structure for the loop.
??? We could re-use unused loop slots here.
Reset latch, we recompute it below.
Make blocks part of the loop root node at start.
Now iterate over the loops found, insert them into the loop tree and assign basic-block ownership.
Look for the latch for this header block, if it has just a
single one. More than one latch edge.
| void flow_loops_free | ( | ) |
Free all the memory allocated for LOOPS.
Free the loop descriptors.
|
static |
Creates a subloop of LOOP with latch edge LATCH.
Find the blocks and subloops that belong to the new loop, and add it to the appropriate place in the loop tree.
References dump_file.
| bool get_estimated_loop_iterations | ( | ) |
Sets NIT to the estimated number of executions of the latch of the LOOP. If we have no reliable estimate, the function returns false, otherwise returns true.
Even if the bound is not recorded, possibly we can derrive one from profile.
| HOST_WIDE_INT get_estimated_loop_iterations_int | ( | ) |
Similar to get_estimated_loop_iterations, but returns the estimate only if it fits to HOST_WIDE_INT. If this is not the case, or the estimate on the number of iterations of LOOP could not be derived, returns -1.
|
staticread |
Returns the list of records for E as an exit of a loop.
| basic_block* get_loop_body | ( | ) |
Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs order against direction of edges from latch. Specially, if header != latch, latch is the 1-st block.
There may be blocks unreachable from EXIT_BLOCK, hence we need to special-case the fake loop that contains the whole function.
References EXIT_BLOCK_PTR, fill_sons_in_loop(), gcc_assert, loop::header, loop::latch, and loop::num_nodes.
Referenced by copy_loop_info(), dump_recorded_exit(), num_loop_insns(), record_loop_exits(), rewrite_use_compare(), and split_edge_and_insert().
| basic_block* get_loop_body_in_bfs_order | ( | ) |
Get body of a LOOP in breadth first sort order.
This basic block is now visited
References ggc_free(), loop_exit::next, loop_exit::next_e, and loop_exit::prev.
| basic_block* get_loop_body_in_custom_order | ( | const struct loop * | loop, |
| int(*)(const void *, const void *) | bb_comparator | ||
| ) |
Gets body of a LOOP sorted via provided BB_COMPARATOR.
References loop_exit::e.
| basic_block* get_loop_body_in_dom_order | ( | ) |
Gets body of a LOOP (that must be different from the outermost loop) sorted by dominance relation. Additionally, if a basic block s dominates the latch, then only blocks dominated by s are be after it.
Referenced by clear_iv_info(), create_loop_fn(), and ref_indep_loop_p().
| unsigned get_loop_body_with_size | ( | const struct loop * | loop, |
| basic_block * | body, | ||
| unsigned | max_size | ||
| ) |
Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs order against direction of edges from latch. Specially, if header != latch, latch is the 1-st block. LOOP cannot be the fake loop tree root, and its size must be at most MAX_SIZE. The blocks in the LOOP body are stored to BODY, and the size of the LOOP is returned.
Referenced by cancel_loop().
Returns the list of the exit edges of a LOOP.
If we maintain the lists of exits, use them. Otherwise we must scan the body of the loop.
Referenced by add_exit_phis(), delete_allocno_from_bucket(), estimated_unrolled_size(), nontemporal_store_p(), and ref_indep_loop_p_2().
Returns the list of the latch edges of LOOP.
References CDI_DOMINATORS, dominated_by_p(), loop::header, and edge_def::src.
| location_t get_loop_location | ( | ) |
Return location corresponding to the loop control condition if possible.
For a for or while loop, we would like to return the location of the for or while statement, if possible. To do this, look for the branch guarding the loop back-edge.
If this is a simple loop with an in_edge, then the loop control branch is typically at the end of its source.
If loop has a single exit, then the loop control branch must be at the end of its source.
Next check the latch, to see if it is non-empty.
Finally, if none of the above identifies the loop control branch, return the first location in the loop header.
If all else fails, simply return the current function location.
References get_max_loop_iterations_int(), and HOST_WIDE_INT.
Referenced by loop_exit_at_end_p().
| bool get_max_loop_iterations | ( | ) |
Sets NIT to an upper bound for the maximum number of executions of the latch of the LOOP. If we have no reliable estimate, the function returns false, otherwise returns true.
| HOST_WIDE_INT get_max_loop_iterations_int | ( | ) |
Similar to get_max_loop_iterations, but returns the estimate only if it fits to HOST_WIDE_INT. If this is not the case, or the estimate on the number of iterations of LOOP could not be derived, returns -1.
Referenced by get_loop_location().
|
static |
Enumeration predicate for get_loop_body_with_size.
References CDI_DOMINATORS, dominated_by_p(), first_dom_son(), flow_bb_inside_loop_p(), next_dom_son(), and NULL.
Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops (including the root of the loop tree).
Dummy loop containing whole function.
| bool loop_exit_edge_p | ( | ) |
Returns true if E is an exit of LOOP.
Referenced by redirection_block_p(), and remove_conditions_and_labels().
|
static |
Equality function for struct loop_exit. Compares with edge.
|
static |
Frees the list of loop exit descriptions EX.
References loop::exits.
|
static |
Hash function for struct loop_exit.
References loop::exits, loop_exit::next, and loop_exit::prev.
| bool loop_exits_from_bb_p | ( | ) |
Returns true when BB has an outgoing edge exiting LOOP.
| bool loop_exits_to_bb_p | ( | ) |
Returns true when BB has an incoming edge exiting LOOP.
| edge loop_latch_edge | ( | ) |
Returns latch edge of LOOP.
References FOR_BB_INSNS_REVERSE, INSN_HAS_LOCATION, INSN_LOCATION, INSN_P, and edge_def::src.
Referenced by create_iv(), create_parallel_loop(), get_initial_def_for_reduction(), get_iv(), predcom_tmp_var(), and redirection_block_p().
| edge loop_preheader_edge | ( | ) |
Returns preheader edge of LOOP.
Referenced by alloc_iv(), create_iv(), create_parallel_loop(), decide_peel_simple(), find_invariants_to_move(), find_loop_location(), get_initial_def_for_reduction(), predcom_tmp_var(), scale_dominated_blocks_in_loop(), ssa_name_has_uses_outside_loop_p(), vect_can_advance_ivs_p(), vect_do_peeling_for_loop_bound(), vect_get_new_vect_var(), vect_slp_analyze_bb(), and vect_update_ivs_after_vectorizer().
| HOST_WIDE_INT max_stmt_executions_int | ( | ) |
Returns an upper bound on the number of executions of statements in the LOOP. For statements before the loop exit, this exceeds the number of execution of the latch by one.
If the computation overflows, return -1.
Referenced by initialize_matrix_A(), and lambda_vector_equal().
|
static |
Make all the latch edges of LOOP to go to a single forwarder block – a new latch of LOOP.
|
static |
| unsigned num_loop_branches | ( | ) |
Counts the number of conditional branches inside LOOP.
| void record_loop_exits | ( | void | ) |
For each loop, record list of exit edges, and start maintaining these lists.
References edge_def::dest, loop_exit::e, EXIT_BLOCK_PTR, loop::exits, flow_bb_inside_loop_p(), FOR_EACH_EDGE, gcc_assert, get_loop_body(), loop::latch, LOOPS_HAVE_RECORDED_EXITS, loops_state_satisfies_p(), loop_exit::next, loop::num_nodes, and vNULL.
| void record_niter_bound | ( | struct loop * | loop, |
| double_int | i_bound, | ||
| bool | realistic, | ||
| bool | upper | ||
| ) |
Records that every statement in LOOP is executed I_BOUND times. REALISTIC is true if I_BOUND is expected to be close to the real number of iterations. UPPER is true if we are sure the loop iterates at most I_BOUND times.
Update the bounds only when there is no previous estimation, or when the current estimation is smaller.
If an upper bound is smaller than the realistic estimate of the number of iterations, use the upper bound instead.
Referenced by vect_update_ivs_after_vectorizer().
| void release_recorded_exits | ( | void | ) |
Releases lists of loop exits.
References rescan_loop_exit().
| void remove_bb_from_loops | ( | ) |
Remove basic block BB from loops.
Referenced by predicted_by_p().
| void rescan_loop_exit | ( | ) |
Updates the lists of loop exits in that E appears. If REMOVED is true, E is being removed, and we just remove it from the lists of exits. If NEW_EDGE is true and E is not a loop exit, we do not try to remove it from loop exit lists.
Referenced by copy_phi_args(), redirect_edge_succ_nodup(), release_recorded_exits(), remove_branch(), and tidy_fallthru_edges().
| edge single_exit | ( | ) |
Returns the single exit edge of LOOP, or NULL if LOOP has either no exit or more than one exit. If loops do not have the exits recorded, NULL is returned always.
References loop::any_upper_bound, and loop::nb_iterations_upper_bound.
Referenced by create_empty_if_region_on_edge(), vect_can_advance_ivs_p(), vect_create_cond_for_alias_checks(), vect_create_epilog_for_reduction(), and vect_update_ivs_after_vectorizer().
|
read |
Returns the loop such that LOOP is nested DEPTH (indexed from zero) loops within LOOP.
Referenced by set_ifsese_condition().
| DEBUG_FUNCTION void verify_loop_structure | ( | void | ) |
Checks that information about loops is correct – sizes of loops are all right – results of get_loop_body really belong to the loop – loop header have just single entry edge and single latch edge – loop latches have only single successor that is header of their loop – irreducible loops are correctly marked – the cached loop depth and loop father of each bb is correct
We need up-to-date dominators, compute or verify them.
Check the headers.
Check the recorded loop father and sizes of loops.
Ignore this block if it is in an inner loop.
Check headers and latches.
Check irreducible loops.
Record old info.
Recount it.
Compare.
Check the recorded loop exits.
Check that the list forms a cycle, and all elements except
for the head are nonnull. When a loop exit is also an entry edge which
can happen when avoiding CFG manipulations
then the last loop exited is the outer loop
of the loop entered.
Variable Documentation
|
static |
Callback for make_forwarder_block. Returns true if the edge E is marked in the set MFB_REIS_SET.
