#include "config.h"#include "system.h"#include "coretypes.h"#include "backend.h"#include "cfganal.h"#include "lcm.h"
Function Documentation
◆ compute_antinout_edge()
| void compute_antinout_edge | ( | sbitmap * | antloc, |
| sbitmap * | transp, | ||
| sbitmap * | antin, | ||
| sbitmap * | antout ) |
Edge based lcm routines.
Compute expression anticipatability at entrance and exit of each block. This is done based on the flow graph, and not on the pred-succ lists. Other than that, its pretty much identical to compute_antinout.
References antloc, basic_block_def::aux, BASIC_BLOCK_FOR_FN, bitmap_clear(), bitmap_intersection_of_succs(), bitmap_or_and(), bitmap_vector_ones(), cfun, clear_aux_for_blocks(), clear_aux_for_edges(), ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, FOR_EACH_EDGE, free(), i, basic_block_def::index, inverted_rev_post_order_compute(), last_basic_block_for_fn, n_basic_blocks_for_fn, NULL, NUM_FIXED_BLOCKS, basic_block_def::preds, transp, and worklist.
Referenced by pre_edge_lcm_avs(), and pre_edge_rev_lcm().
◆ compute_available()
Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors. Return the number of passes we performed to iterate to a solution.
References basic_block_def::aux, BASIC_BLOCK_FOR_FN, bitmap_clear(), bitmap_intersection_of_preds(), bitmap_ior_and_compl(), bitmap_vector_ones(), cfun, clear_aux_for_blocks(), clear_aux_for_edges(), ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, FOR_EACH_EDGE, free(), i, basic_block_def::index, kill, last_basic_block_for_fn, n_basic_blocks_for_fn, NULL, NUM_FIXED_BLOCKS, pre_and_rev_post_order_compute_fn(), basic_block_def::succs, and worklist.
Referenced by compute_cprop_data(), pre_edge_lcm_avs(), and pre_edge_rev_lcm().
◆ compute_earliest()
| void compute_earliest | ( | struct edge_list * | edge_list, |
| int | n_exprs, | ||
| sbitmap * | antin, | ||
| sbitmap * | antout, | ||
| sbitmap * | avout, | ||
| sbitmap * | kill, | ||
| sbitmap * | earliest ) |
Compute the earliest vector for edge based lcm.
References bitmap_and_compl(), bitmap_and_or(), bitmap_clear(), bitmap_copy(), bitmap_not(), cfun, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, basic_block_def::index, INDEX_EDGE_PRED_BB, INDEX_EDGE_SUCC_BB, kill, NUM_EDGES, and temp_bitmap.
Referenced by pre_edge_lcm_avs().
◆ compute_farthest()
|
static |
Edge based LCM routines on a reverse flowgraph.
Compute the farthest vector for edge based lcm.
References bitmap_and_compl(), bitmap_and_or(), bitmap_clear(), bitmap_copy(), bitmap_not(), cfun, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, basic_block_def::index, INDEX_EDGE_PRED_BB, INDEX_EDGE_SUCC_BB, kill, NUM_EDGES, edge_list::num_edges, and temp_bitmap.
Referenced by pre_edge_rev_lcm().
◆ compute_insert_delete()
|
static |
Compute the insertion and deletion points for edge based LCM.
References antloc, b, bitmap_and_compl(), cfun, EXIT_BLOCK_PTR_FOR_FN, FOR_EACH_BB_FN, basic_block_def::index, INDEX_EDGE_SUCC_BB, insert(), last_basic_block_for_fn, and NUM_EDGES.
Referenced by pre_edge_lcm_avs().
◆ compute_laterin()
|
static |
Generic partial redundancy elimination with lazy code motion support. Copyright (C) 1998-2025 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/>.
These routines are meant to be used by various optimization
passes which can be modeled as lazy code motion problems.
Including, but not limited to:
* Traditional partial redundancy elimination.
* Placement of caller/caller register save/restores.
* Load/store motion.
* Copy motion.
* Conversion of flat register files to a stacked register
model.
* Dead load/store elimination.
These routines accept as input:
* Basic block information (number of blocks, lists of
predecessors and successors). Note the granularity
does not need to be basic block, they could be statements
or functions.
* Bitmaps of local properties (computed, transparent and
anticipatable expressions).
The output of these routines is bitmap of redundant computations
and a bitmap of optimal placement points. Edge based LCM routines.
later(p,s) is dependent on the calculation of laterin(p). laterin(p) is dependent on the calculation of later(p2,p). laterin(ENTRY) is defined as all 0's later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY) laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)). If we progress in this manner, starting with all basic blocks in the work list, anytime we change later(bb), we need to add succs(bb) to the worklist if they are not already on the worklist. Boundary conditions: We prime the worklist all the normal basic blocks. The ENTRY block can never be added to the worklist since it is never the successor of any block. We explicitly prevent the EXIT block from being added to the worklist. We optimistically initialize LATER. That is the only time this routine will compute LATER for an edge out of the entry block since the entry block is never on the worklist. Thus, LATERIN is neither used nor computed for the ENTRY block. Since the EXIT block is never added to the worklist, we will neither use nor compute LATERIN for the exit block. Edges which reach the EXIT block are handled in the normal fashion inside the loop. However, the insertion/deletion computation needs LATERIN(EXIT), so we have to compute it.
References antloc, basic_block_def::aux, BASIC_BLOCK_FOR_FN, bitmap_and(), bitmap_copy(), bitmap_ior_and_compl(), bitmap_ones(), bitmap_vector_ones(), cfun, clear_aux_for_edges(), ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, FOR_EACH_EDGE, free(), i, basic_block_def::index, INDEX_EDGE, last_basic_block_for_fn, n_basic_blocks_for_fn, NULL, NUM_EDGES, NUM_FIXED_BLOCKS, pre_and_rev_post_order_compute_fn(), basic_block_def::preds, basic_block_def::succs, and worklist.
Referenced by pre_edge_lcm_avs().
◆ compute_nearerout()
|
static |
Compute nearer and nearerout vectors for edge based lcm. This is the mirror of compute_laterin, additional comments on the implementation can be found before compute_laterin.
References basic_block_def::aux, bitmap_and(), bitmap_copy(), bitmap_ior_and_compl(), bitmap_ones(), bitmap_vector_ones(), cfun, clear_aux_for_edges(), ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, FOR_EACH_BB_FN, FOR_EACH_EDGE, free(), i, basic_block_def::index, INDEX_EDGE, last_basic_block_for_fn, n_basic_blocks_for_fn, NULL, NUM_EDGES, edge_list::num_edges, basic_block_def::preds, st_avloc, basic_block_def::succs, and worklist.
Referenced by pre_edge_rev_lcm().
◆ compute_rev_insert_delete()
|
static |
Compute the insertion and deletion points for edge based LCM.
References b, bitmap_and_compl(), cfun, ENTRY_BLOCK_PTR_FOR_FN, FOR_EACH_BB_FN, basic_block_def::index, INDEX_EDGE_PRED_BB, insert(), last_basic_block_for_fn, NUM_EDGES, and st_avloc.
Referenced by pre_edge_rev_lcm().
◆ pre_edge_lcm()
| struct edge_list * pre_edge_lcm | ( | int | n_exprs, |
| sbitmap * | transp, | ||
| sbitmap * | avloc, | ||
| sbitmap * | antloc, | ||
| sbitmap * | kill, | ||
| sbitmap ** | insert, | ||
| sbitmap ** | del ) |
Wrapper to allocate avin/avout and call pre_edge_lcm_avs.
References antloc, cfun, insert(), kill, last_basic_block_for_fn, pre_edge_lcm_avs(), sbitmap_vector_alloc(), sbitmap_vector_free(), and transp.
Referenced by compute_pre_data().
◆ pre_edge_lcm_avs()
| struct edge_list * pre_edge_lcm_avs | ( | int | n_exprs, |
| sbitmap * | transp, | ||
| sbitmap * | avloc, | ||
| sbitmap * | antloc, | ||
| sbitmap * | kill, | ||
| sbitmap * | avin, | ||
| sbitmap * | avout, | ||
| sbitmap ** | insert, | ||
| sbitmap ** | del ) |
Given local properties TRANSP, ANTLOC, AVLOC, KILL return the insert and delete vectors for edge based LCM and return the AVIN, AVOUT bitmap. map the insert vector to what edge an expression should be inserted on.
References antloc, bitmap_vector_clear(), cfun, compute_antinout_edge(), compute_available(), compute_earliest(), compute_insert_delete(), compute_laterin(), create_edge_list(), dump_bitmap_vector(), dump_file, insert(), kill, last_basic_block_for_fn, NUM_EDGES, edge_list::num_edges, print_edge_list(), sbitmap_vector_alloc(), sbitmap_vector_free(), transp, and verify_edge_list().
Referenced by pre_edge_lcm().
◆ pre_edge_rev_lcm()
| struct edge_list * pre_edge_rev_lcm | ( | int | n_exprs, |
| sbitmap * | transp, | ||
| sbitmap * | st_avloc, | ||
| sbitmap * | st_antloc, | ||
| sbitmap * | kill, | ||
| sbitmap ** | insert, | ||
| sbitmap ** | del ) |
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.
References bitmap_vector_clear(), cfun, compute_antinout_edge(), compute_available(), compute_farthest(), compute_nearerout(), compute_rev_insert_delete(), create_edge_list(), dump_bitmap_vector(), dump_file, insert(), kill, last_basic_block_for_fn, NUM_EDGES, edge_list::num_edges, print_edge_list(), sbitmap_vector_alloc(), sbitmap_vector_free(), st_antloc, st_avloc, transp, and verify_edge_list().
Referenced by one_store_motion_pass().
