GCC Middle and Back End API Reference
lcm.cc File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "cfganal.h"
#include "lcm.h"
Include dependency graph for lcm.cc:

Functions

static void compute_laterin (struct edge_list *, sbitmap *, sbitmap *, sbitmap *, sbitmap *)
 
static void compute_insert_delete (struct edge_list *edge_list, sbitmap *, sbitmap *, sbitmap *, sbitmap *, sbitmap *)
 
static void compute_farthest (struct edge_list *, int, sbitmap *, sbitmap *, sbitmap *, sbitmap *, sbitmap *)
 
static void compute_nearerout (struct edge_list *, sbitmap *, sbitmap *, sbitmap *, sbitmap *)
 
static void compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *, sbitmap *, sbitmap *, sbitmap *, sbitmap *)
 
void compute_antinout_edge (sbitmap *antloc, sbitmap *transp, sbitmap *antin, sbitmap *antout)
 
void compute_earliest (struct edge_list *edge_list, int n_exprs, sbitmap *antin, sbitmap *antout, sbitmap *avout, sbitmap *kill, sbitmap *earliest)
 
struct edge_listpre_edge_lcm_avs (int n_exprs, sbitmap *transp, sbitmap *avloc, sbitmap *antloc, sbitmap *kill, sbitmap *avin, sbitmap *avout, sbitmap **insert, sbitmap **del)
 
struct edge_listpre_edge_lcm (int n_exprs, sbitmap *transp, sbitmap *avloc, sbitmap *antloc, sbitmap *kill, sbitmap **insert, sbitmap **del)
 
void compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout, sbitmap *avin)
 
struct edge_listpre_edge_rev_lcm (int n_exprs, sbitmap *transp, sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill, sbitmap **insert, sbitmap **del)
 

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_earliest()

void compute_earliest ( struct edge_list * edge_list,
int n_exprs,
sbitmap * antin,
sbitmap * antout,
sbitmap * avout,
sbitmap * kill,
sbitmap * earliest )

◆ compute_farthest()

static void compute_farthest ( struct edge_list * edge_list,
int n_exprs,
sbitmap * st_avout,
sbitmap * st_avin,
sbitmap * st_antin,
sbitmap * kill,
sbitmap * farthest )
static

◆ compute_insert_delete()

static void compute_insert_delete ( struct edge_list * edge_list,
sbitmap * antloc,
sbitmap * later,
sbitmap * laterin,
sbitmap * insert,
sbitmap * del )
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 void compute_laterin ( struct edge_list * edge_list,
sbitmap * earliest,
sbitmap * antloc,
sbitmap * later,
sbitmap * laterin )
static
Generic partial redundancy elimination with lazy code motion support.
   Copyright (C) 1998-2024 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 void compute_nearerout ( struct edge_list * edge_list,
sbitmap * farthest,
sbitmap * st_avloc,
sbitmap * nearer,
sbitmap * nearerout )
static

◆ compute_rev_insert_delete()

static void compute_rev_insert_delete ( struct edge_list * edge_list,
sbitmap * st_avloc,
sbitmap * nearer,
sbitmap * nearerout,
sbitmap * insert,
sbitmap * del )
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, edge_list, 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, edge_list, 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, edge_list, 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().