GCC Middle and Back End API Reference
lcm.c File Reference

Functions

static void compute_antinout_edge (sbitmap *, sbitmap *, sbitmap *, sbitmap *)
static void compute_earliest (struct edge_list *, int, sbitmap *, sbitmap *, sbitmap *, sbitmap *, sbitmap *)
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 *)
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

static void compute_antinout_edge ( sbitmap antloc,
sbitmap transp,
sbitmap antin,
sbitmap antout 
)
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().

void compute_available ( sbitmap avloc,
sbitmap kill,
sbitmap avout,
sbitmap avin 
)
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 void compute_earliest ( struct edge_list edge_list,
int  n_exprs,
sbitmap antin,
sbitmap antout,
sbitmap avout,
sbitmap kill,
sbitmap earliest 
)
static
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
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 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 bitmap_and_compl(), and basic_block_def::index.

Referenced by pre_edge_lcm().

static void compute_laterin ( struct edge_list edge_list,
sbitmap earliest,
sbitmap antloc,
sbitmap later,
sbitmap laterin 
)
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 void compute_nearerout ( struct edge_list edge_list,
sbitmap farthest,
sbitmap st_avloc,
sbitmap nearer,
sbitmap 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 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 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 bitmap_and_compl(), and basic_block_def::index.

Referenced by pre_edge_rev_lcm().

struct edge_list* pre_edge_lcm ( int  n_exprs,
sbitmap transp,
sbitmap avloc,
sbitmap antloc,
sbitmap kill,
sbitmap **  insert,
sbitmap **  del 
)
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().

struct edge_list* pre_edge_rev_lcm ( int  n_exprs,
sbitmap transp,
sbitmap st_avloc,
sbitmap st_antloc,
sbitmap kill,
sbitmap **  insert,
sbitmap **  del 
)
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().