GCC Middle and Back End API Reference
|
|
static |
@verbatim Generic partial redundancy elimination with lazy code motion support.
Copyright (C) 1998-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/.
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.
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 basic_block_def::aux, bitmap_clear(), bitmap_intersection_of_succs(), bitmap_or_and(), bitmap_vector_ones(), clear_aux_for_blocks(), clear_aux_for_edges(), free(), basic_block_def::index, basic_block_def::preds, edge_def::src, and worklist.
Referenced by pre_edge_lcm(), and pre_edge_rev_lcm().
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, bitmap_clear(), bitmap_intersection_of_preds(), bitmap_ior_and_compl(), bitmap_vector_ones(), clear_aux_for_blocks(), clear_aux_for_edges(), edge_def::dest, free(), basic_block_def::index, basic_block_def::succs, and worklist.
Referenced by compute_cprop_data(), pre_edge_lcm(), and pre_edge_rev_lcm().
|
static |
Compute the earliest vector for edge based lcm.
References bitmap_and_compl(), bitmap_and_or(), bitmap_clear(), bitmap_copy(), bitmap_not(), basic_block_def::index, sbitmap_alloc(), sbitmap_free(), and temp_bitmap.
Referenced by pre_edge_lcm().
|
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(), basic_block_def::index, edge_list::num_edges, sbitmap_alloc(), sbitmap_free(), and temp_bitmap.
Referenced by pre_edge_rev_lcm().
|
static |
Compute the insertion and deletion points for edge based LCM.
References bitmap_and_compl(), and basic_block_def::index.
Referenced by pre_edge_lcm().
|
static |
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 edge_def::aux, basic_block_def::aux, bitmap_and(), bitmap_copy(), bitmap_ior_and_compl(), bitmap_ones(), bitmap_vector_ones(), clear_aux_for_edges(), edge_def::dest, free(), basic_block_def::index, basic_block_def::preds, edge_def::src, basic_block_def::succs, and worklist.
Referenced by pre_edge_lcm().
|
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 edge_def::aux, basic_block_def::aux, bitmap_and(), bitmap_copy(), bitmap_ior_and_compl(), bitmap_ones(), bitmap_vector_ones(), clear_aux_for_edges(), edge_def::dest, free(), basic_block_def::index, edge_list::num_edges, basic_block_def::preds, edge_def::src, basic_block_def::succs, and worklist.
Referenced by pre_edge_rev_lcm().
|
static |
Compute the insertion and deletion points for edge based LCM.
References bitmap_and_compl(), and basic_block_def::index.
Referenced by pre_edge_rev_lcm().
|
read |
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.
References bitmap_vector_clear(), compute_antinout_edge(), compute_available(), compute_earliest(), compute_insert_delete(), compute_laterin(), create_edge_list(), dump_bitmap_vector(), dump_file, edge_list, edge_list::num_edges, print_edge_list(), sbitmap_vector_alloc(), sbitmap_vector_free(), and verify_edge_list().
Referenced by compute_pre_data(), and optimize_mode_switching().
|
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.
References bitmap_vector_clear(), compute_antinout_edge(), compute_available(), compute_farthest(), compute_nearerout(), compute_rev_insert_delete(), create_edge_list(), dump_bitmap_vector(), dump_file, edge_list, edge_list::num_edges, print_edge_list(), sbitmap_vector_alloc(), sbitmap_vector_free(), and verify_edge_list().
Referenced by one_store_motion_pass().