diff options
Diffstat (limited to 'gcc/lcm.cc')
-rw-r--r-- | gcc/lcm.cc | 838 |
1 files changed, 838 insertions, 0 deletions
diff --git a/gcc/lcm.cc b/gcc/lcm.cc new file mode 100644 index 0000000..e66b712 --- /dev/null +++ b/gcc/lcm.cc @@ -0,0 +1,838 @@ +/* Generic partial redundancy elimination with lazy code motion support. + Copyright (C) 1998-2022 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. */ + + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "cfganal.h" +#include "lcm.h" + +/* Edge based LCM routines. */ +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 *); + +/* Edge based LCM routines on a reverse flowgraph. */ +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 *); + +/* 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. */ + +static void +compute_antinout_edge (sbitmap *antloc, sbitmap *transp, sbitmap *antin, + sbitmap *antout) +{ + basic_block bb; + edge e; + basic_block *worklist, *qin, *qout, *qend; + unsigned int qlen; + edge_iterator ei; + + /* Allocate a worklist array/queue. Entries are only added to the + list if they were not already on the list. So the size is + bounded by the number of basic blocks. */ + qin = qout = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun)); + + /* We want a maximal solution, so make an optimistic initialization of + ANTIN. */ + bitmap_vector_ones (antin, last_basic_block_for_fn (cfun)); + + /* Put every block on the worklist; this is necessary because of the + optimistic initialization of ANTIN above. */ + int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); + int postorder_num = post_order_compute (postorder, false, false); + for (int i = 0; i < postorder_num; ++i) + { + bb = BASIC_BLOCK_FOR_FN (cfun, postorder[i]); + *qin++ = bb; + bb->aux = bb; + } + free (postorder); + + qin = worklist; + qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS]; + qlen = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; + + /* Mark blocks which are predecessors of the exit block so that we + can easily identify them below. */ + FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds) + e->src->aux = EXIT_BLOCK_PTR_FOR_FN (cfun); + + /* Iterate until the worklist is empty. */ + while (qlen) + { + /* Take the first entry off the worklist. */ + bb = *qout++; + qlen--; + + if (qout >= qend) + qout = worklist; + + if (bb->aux == EXIT_BLOCK_PTR_FOR_FN (cfun)) + /* Do not clear the aux field for blocks which are predecessors of + the EXIT block. That way we never add then to the worklist + again. */ + bitmap_clear (antout[bb->index]); + else + { + /* Clear the aux field of this block so that it can be added to + the worklist again if necessary. */ + bb->aux = NULL; + bitmap_intersection_of_succs (antout[bb->index], antin, bb); + } + + if (bitmap_or_and (antin[bb->index], antloc[bb->index], + transp[bb->index], antout[bb->index])) + /* If the in state of this block changed, then we need + to add the predecessors of this block to the worklist + if they are not already on the worklist. */ + FOR_EACH_EDGE (e, ei, bb->preds) + if (!e->src->aux && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) + { + *qin++ = e->src; + e->src->aux = e; + qlen++; + if (qin >= qend) + qin = worklist; + } + } + + clear_aux_for_edges (); + clear_aux_for_blocks (); + free (worklist); +} + +/* Compute the earliest vector for edge based lcm. */ + +static void +compute_earliest (struct edge_list *edge_list, int n_exprs, sbitmap *antin, + sbitmap *antout, sbitmap *avout, sbitmap *kill, + sbitmap *earliest) +{ + int x, num_edges; + basic_block pred, succ; + + num_edges = NUM_EDGES (edge_list); + + auto_sbitmap difference (n_exprs), temp_bitmap (n_exprs); + for (x = 0; x < num_edges; x++) + { + pred = INDEX_EDGE_PRED_BB (edge_list, x); + succ = INDEX_EDGE_SUCC_BB (edge_list, x); + if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun)) + bitmap_copy (earliest[x], antin[succ->index]); + else + { + if (succ == EXIT_BLOCK_PTR_FOR_FN (cfun)) + bitmap_clear (earliest[x]); + else + { + bitmap_and_compl (difference, antin[succ->index], + avout[pred->index]); + bitmap_not (temp_bitmap, antout[pred->index]); + bitmap_and_or (earliest[x], difference, + kill[pred->index], temp_bitmap); + } + } + } +} + +/* 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. */ + +static void +compute_laterin (struct edge_list *edge_list, sbitmap *earliest, + sbitmap *antloc, sbitmap *later, sbitmap *laterin) +{ + int num_edges, i; + edge e; + basic_block *worklist, *qin, *qout, *qend, bb; + unsigned int qlen; + edge_iterator ei; + + num_edges = NUM_EDGES (edge_list); + + /* Allocate a worklist array/queue. Entries are only added to the + list if they were not already on the list. So the size is + bounded by the number of basic blocks. */ + qin = qout = worklist + = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun)); + + /* Initialize a mapping from each edge to its index. */ + for (i = 0; i < num_edges; i++) + INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i; + + /* We want a maximal solution, so initially consider LATER true for + all edges. This allows propagation through a loop since the incoming + loop edge will have LATER set, so if all the other incoming edges + to the loop are set, then LATERIN will be set for the head of the + loop. + + If the optimistic setting of LATER on that edge was incorrect (for + example the expression is ANTLOC in a block within the loop) then + this algorithm will detect it when we process the block at the head + of the optimistic edge. That will requeue the affected blocks. */ + bitmap_vector_ones (later, num_edges); + + /* Note that even though we want an optimistic setting of LATER, we + do not want to be overly optimistic. Consider an outgoing edge from + the entry block. That edge should always have a LATER value the + same as EARLIEST for that edge. */ + FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs) + bitmap_copy (later[(size_t) e->aux], earliest[(size_t) e->aux]); + + /* Add all the blocks to the worklist. This prevents an early exit from + the loop given our optimistic initialization of LATER above. */ + auto_vec<int, 20> postorder; + inverted_post_order_compute (&postorder); + for (unsigned int i = 0; i < postorder.length (); ++i) + { + bb = BASIC_BLOCK_FOR_FN (cfun, postorder[i]); + if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) + || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)) + continue; + *qin++ = bb; + bb->aux = bb; + } + + /* Note that we do not use the last allocated element for our queue, + as EXIT_BLOCK is never inserted into it. */ + qin = worklist; + qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS]; + qlen = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; + + /* Iterate until the worklist is empty. */ + while (qlen) + { + /* Take the first entry off the worklist. */ + bb = *qout++; + bb->aux = NULL; + qlen--; + if (qout >= qend) + qout = worklist; + + /* Compute the intersection of LATERIN for each incoming edge to B. */ + bitmap_ones (laterin[bb->index]); + FOR_EACH_EDGE (e, ei, bb->preds) + bitmap_and (laterin[bb->index], laterin[bb->index], + later[(size_t)e->aux]); + + /* Calculate LATER for all outgoing edges. */ + FOR_EACH_EDGE (e, ei, bb->succs) + if (bitmap_ior_and_compl (later[(size_t) e->aux], + earliest[(size_t) e->aux], + laterin[bb->index], + antloc[bb->index]) + /* If LATER for an outgoing edge was changed, then we need + to add the target of the outgoing edge to the worklist. */ + && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest->aux == 0) + { + *qin++ = e->dest; + e->dest->aux = e; + qlen++; + if (qin >= qend) + qin = worklist; + } + } + + /* Computation of insertion and deletion points requires computing LATERIN + for the EXIT block. We allocated an extra entry in the LATERIN array + for just this purpose. */ + bitmap_ones (laterin[last_basic_block_for_fn (cfun)]); + FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds) + bitmap_and (laterin[last_basic_block_for_fn (cfun)], + laterin[last_basic_block_for_fn (cfun)], + later[(size_t) e->aux]); + + clear_aux_for_edges (); + free (worklist); +} + +/* Compute the insertion and deletion points for edge based LCM. */ + +static void +compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc, + sbitmap *later, sbitmap *laterin, sbitmap *insert, + sbitmap *del) +{ + int x; + basic_block bb; + + FOR_EACH_BB_FN (bb, cfun) + bitmap_and_compl (del[bb->index], antloc[bb->index], + laterin[bb->index]); + + for (x = 0; x < NUM_EDGES (edge_list); x++) + { + basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x); + + if (b == EXIT_BLOCK_PTR_FOR_FN (cfun)) + bitmap_and_compl (insert[x], later[x], + laterin[last_basic_block_for_fn (cfun)]); + else + bitmap_and_compl (insert[x], later[x], laterin[b->index]); + } +} + +/* 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. */ + +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) +{ + sbitmap *antin, *antout, *earliest; + sbitmap *later, *laterin; + struct edge_list *edge_list; + int num_edges; + + edge_list = create_edge_list (); + num_edges = NUM_EDGES (edge_list); + +#ifdef LCM_DEBUG_INFO + if (dump_file) + { + fprintf (dump_file, "Edge List:\n"); + verify_edge_list (dump_file, edge_list); + print_edge_list (dump_file, edge_list); + dump_bitmap_vector (dump_file, "transp", "", transp, + last_basic_block_for_fn (cfun)); + dump_bitmap_vector (dump_file, "antloc", "", antloc, + last_basic_block_for_fn (cfun)); + dump_bitmap_vector (dump_file, "avloc", "", avloc, + last_basic_block_for_fn (cfun)); + dump_bitmap_vector (dump_file, "kill", "", kill, + last_basic_block_for_fn (cfun)); + } +#endif + + /* Compute global availability. */ + compute_available (avloc, kill, avout, avin); + + /* Compute global anticipatability. */ + antin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs); + antout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs); + compute_antinout_edge (antloc, transp, antin, antout); + +#ifdef LCM_DEBUG_INFO + if (dump_file) + { + dump_bitmap_vector (dump_file, "antin", "", antin, + last_basic_block_for_fn (cfun)); + dump_bitmap_vector (dump_file, "antout", "", antout, + last_basic_block_for_fn (cfun)); + } +#endif + + /* Compute earliestness. */ + earliest = sbitmap_vector_alloc (num_edges, n_exprs); + compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest); + +#ifdef LCM_DEBUG_INFO + if (dump_file) + dump_bitmap_vector (dump_file, "earliest", "", earliest, num_edges); +#endif + + sbitmap_vector_free (antout); + sbitmap_vector_free (antin); + + later = sbitmap_vector_alloc (num_edges, n_exprs); + + /* Allocate an extra element for the exit block in the laterin vector. */ + laterin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun) + 1, + n_exprs); + compute_laterin (edge_list, earliest, antloc, later, laterin); + +#ifdef LCM_DEBUG_INFO + if (dump_file) + { + dump_bitmap_vector (dump_file, "laterin", "", laterin, + last_basic_block_for_fn (cfun) + 1); + dump_bitmap_vector (dump_file, "later", "", later, num_edges); + } +#endif + + sbitmap_vector_free (earliest); + + *insert = sbitmap_vector_alloc (num_edges, n_exprs); + *del = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs); + bitmap_vector_clear (*insert, num_edges); + bitmap_vector_clear (*del, last_basic_block_for_fn (cfun)); + compute_insert_delete (edge_list, antloc, later, laterin, *insert, *del); + + sbitmap_vector_free (laterin); + sbitmap_vector_free (later); + +#ifdef LCM_DEBUG_INFO + if (dump_file) + { + dump_bitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges); + dump_bitmap_vector (dump_file, "pre_delete_map", "", *del, + last_basic_block_for_fn (cfun)); + } +#endif + + return edge_list; +} + +/* Wrapper to allocate avin/avout and call pre_edge_lcm_avs. */ + +struct edge_list * +pre_edge_lcm (int n_exprs, sbitmap *transp, + sbitmap *avloc, sbitmap *antloc, sbitmap *kill, + sbitmap **insert, sbitmap **del) +{ + struct edge_list *edge_list; + sbitmap *avin, *avout; + + avin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs); + avout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs); + + edge_list = pre_edge_lcm_avs (n_exprs, transp, avloc, antloc, kill, + avin, avout, insert, del); + + sbitmap_vector_free (avout); + sbitmap_vector_free (avin); + + return edge_list; +} + +/* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors. + Return the number of passes we performed to iterate to a solution. */ + +void +compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout, + sbitmap *avin) +{ + edge e; + basic_block *worklist, *qin, *qout, *qend, bb; + unsigned int qlen; + edge_iterator ei; + + /* Allocate a worklist array/queue. Entries are only added to the + list if they were not already on the list. So the size is + bounded by the number of basic blocks. */ + qin = qout = worklist = + XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS); + + /* We want a maximal solution. */ + bitmap_vector_ones (avout, last_basic_block_for_fn (cfun)); + + /* Put every block on the worklist; this is necessary because of the + optimistic initialization of AVOUT above. Use inverted postorder + to make the dataflow problem require less iterations. */ + auto_vec<int, 20> postorder; + inverted_post_order_compute (&postorder); + for (unsigned int i = 0; i < postorder.length (); ++i) + { + bb = BASIC_BLOCK_FOR_FN (cfun, postorder[i]); + if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) + || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)) + continue; + *qin++ = bb; + bb->aux = bb; + } + + qin = worklist; + qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS]; + qlen = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; + + /* Mark blocks which are successors of the entry block so that we + can easily identify them below. */ + FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs) + e->dest->aux = ENTRY_BLOCK_PTR_FOR_FN (cfun); + + /* Iterate until the worklist is empty. */ + while (qlen) + { + /* Take the first entry off the worklist. */ + bb = *qout++; + qlen--; + + if (qout >= qend) + qout = worklist; + + /* If one of the predecessor blocks is the ENTRY block, then the + intersection of avouts is the null set. We can identify such blocks + by the special value in the AUX field in the block structure. */ + if (bb->aux == ENTRY_BLOCK_PTR_FOR_FN (cfun)) + /* Do not clear the aux field for blocks which are successors of the + ENTRY block. That way we never add then to the worklist again. */ + bitmap_clear (avin[bb->index]); + else + { + /* Clear the aux field of this block so that it can be added to + the worklist again if necessary. */ + bb->aux = NULL; + bitmap_intersection_of_preds (avin[bb->index], avout, bb); + } + + if (bitmap_ior_and_compl (avout[bb->index], avloc[bb->index], + avin[bb->index], kill[bb->index])) + /* If the out state of this block changed, then we need + to add the successors of this block to the worklist + if they are not already on the worklist. */ + FOR_EACH_EDGE (e, ei, bb->succs) + if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) + { + *qin++ = e->dest; + e->dest->aux = e; + qlen++; + + if (qin >= qend) + qin = worklist; + } + } + + clear_aux_for_edges (); + clear_aux_for_blocks (); + free (worklist); +} + +/* Compute the farthest vector for edge based lcm. */ + +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) +{ + int x, num_edges; + basic_block pred, succ; + + num_edges = NUM_EDGES (edge_list); + + auto_sbitmap difference (n_exprs), temp_bitmap (n_exprs); + for (x = 0; x < num_edges; x++) + { + pred = INDEX_EDGE_PRED_BB (edge_list, x); + succ = INDEX_EDGE_SUCC_BB (edge_list, x); + if (succ == EXIT_BLOCK_PTR_FOR_FN (cfun)) + bitmap_copy (farthest[x], st_avout[pred->index]); + else + { + if (pred == ENTRY_BLOCK_PTR_FOR_FN (cfun)) + bitmap_clear (farthest[x]); + else + { + bitmap_and_compl (difference, st_avout[pred->index], + st_antin[succ->index]); + bitmap_not (temp_bitmap, st_avin[succ->index]); + bitmap_and_or (farthest[x], difference, + kill[succ->index], temp_bitmap); + } + } + } +} + +/* 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. */ + +static void +compute_nearerout (struct edge_list *edge_list, sbitmap *farthest, + sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout) +{ + int num_edges, i; + edge e; + basic_block *worklist, *tos, bb; + edge_iterator ei; + + num_edges = NUM_EDGES (edge_list); + + /* Allocate a worklist array/queue. Entries are only added to the + list if they were not already on the list. So the size is + bounded by the number of basic blocks. */ + tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) + 1); + + /* Initialize NEARER for each edge and build a mapping from an edge to + its index. */ + for (i = 0; i < num_edges; i++) + INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i; + + /* We want a maximal solution. */ + bitmap_vector_ones (nearer, num_edges); + + /* Note that even though we want an optimistic setting of NEARER, we + do not want to be overly optimistic. Consider an incoming edge to + the exit block. That edge should always have a NEARER value the + same as FARTHEST for that edge. */ + FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds) + bitmap_copy (nearer[(size_t)e->aux], farthest[(size_t)e->aux]); + + /* Add all the blocks to the worklist. This prevents an early exit + from the loop given our optimistic initialization of NEARER. */ + FOR_EACH_BB_FN (bb, cfun) + { + *tos++ = bb; + bb->aux = bb; + } + + /* Iterate until the worklist is empty. */ + while (tos != worklist) + { + /* Take the first entry off the worklist. */ + bb = *--tos; + bb->aux = NULL; + + /* Compute the intersection of NEARER for each outgoing edge from B. */ + bitmap_ones (nearerout[bb->index]); + FOR_EACH_EDGE (e, ei, bb->succs) + bitmap_and (nearerout[bb->index], nearerout[bb->index], + nearer[(size_t) e->aux]); + + /* Calculate NEARER for all incoming edges. */ + FOR_EACH_EDGE (e, ei, bb->preds) + if (bitmap_ior_and_compl (nearer[(size_t) e->aux], + farthest[(size_t) e->aux], + nearerout[e->dest->index], + st_avloc[e->dest->index]) + /* If NEARER for an incoming edge was changed, then we need + to add the source of the incoming edge to the worklist. */ + && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) && e->src->aux == 0) + { + *tos++ = e->src; + e->src->aux = e; + } + } + + /* Computation of insertion and deletion points requires computing NEAREROUT + for the ENTRY block. We allocated an extra entry in the NEAREROUT array + for just this purpose. */ + bitmap_ones (nearerout[last_basic_block_for_fn (cfun)]); + FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs) + bitmap_and (nearerout[last_basic_block_for_fn (cfun)], + nearerout[last_basic_block_for_fn (cfun)], + nearer[(size_t) e->aux]); + + clear_aux_for_edges (); + free (tos); +} + +/* Compute the insertion and deletion points for edge based LCM. */ + +static void +compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *st_avloc, + sbitmap *nearer, sbitmap *nearerout, + sbitmap *insert, sbitmap *del) +{ + int x; + basic_block bb; + + FOR_EACH_BB_FN (bb, cfun) + bitmap_and_compl (del[bb->index], st_avloc[bb->index], + nearerout[bb->index]); + + for (x = 0; x < NUM_EDGES (edge_list); x++) + { + basic_block b = INDEX_EDGE_PRED_BB (edge_list, x); + if (b == ENTRY_BLOCK_PTR_FOR_FN (cfun)) + bitmap_and_compl (insert[x], nearer[x], + nearerout[last_basic_block_for_fn (cfun)]); + else + bitmap_and_compl (insert[x], nearer[x], nearerout[b->index]); + } +} + +/* 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. */ + +struct edge_list * +pre_edge_rev_lcm (int n_exprs, sbitmap *transp, + sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill, + sbitmap **insert, sbitmap **del) +{ + sbitmap *st_antin, *st_antout; + sbitmap *st_avout, *st_avin, *farthest; + sbitmap *nearer, *nearerout; + struct edge_list *edge_list; + int num_edges; + + edge_list = create_edge_list (); + num_edges = NUM_EDGES (edge_list); + + st_antin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs); + st_antout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs); + bitmap_vector_clear (st_antin, last_basic_block_for_fn (cfun)); + bitmap_vector_clear (st_antout, last_basic_block_for_fn (cfun)); + compute_antinout_edge (st_antloc, transp, st_antin, st_antout); + + /* Compute global anticipatability. */ + st_avout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs); + st_avin = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs); + compute_available (st_avloc, kill, st_avout, st_avin); + +#ifdef LCM_DEBUG_INFO + if (dump_file) + { + fprintf (dump_file, "Edge List:\n"); + verify_edge_list (dump_file, edge_list); + print_edge_list (dump_file, edge_list); + dump_bitmap_vector (dump_file, "transp", "", transp, + last_basic_block_for_fn (cfun)); + dump_bitmap_vector (dump_file, "st_avloc", "", st_avloc, + last_basic_block_for_fn (cfun)); + dump_bitmap_vector (dump_file, "st_antloc", "", st_antloc, + last_basic_block_for_fn (cfun)); + dump_bitmap_vector (dump_file, "st_antin", "", st_antin, + last_basic_block_for_fn (cfun)); + dump_bitmap_vector (dump_file, "st_antout", "", st_antout, + last_basic_block_for_fn (cfun)); + dump_bitmap_vector (dump_file, "st_kill", "", kill, + last_basic_block_for_fn (cfun)); + } +#endif + +#ifdef LCM_DEBUG_INFO + if (dump_file) + { + dump_bitmap_vector (dump_file, "st_avout", "", st_avout, last_basic_block_for_fn (cfun)); + dump_bitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block_for_fn (cfun)); + } +#endif + + /* Compute farthestness. */ + farthest = sbitmap_vector_alloc (num_edges, n_exprs); + compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin, + kill, farthest); + +#ifdef LCM_DEBUG_INFO + if (dump_file) + dump_bitmap_vector (dump_file, "farthest", "", farthest, num_edges); +#endif + + sbitmap_vector_free (st_antin); + sbitmap_vector_free (st_antout); + + sbitmap_vector_free (st_avin); + sbitmap_vector_free (st_avout); + + nearer = sbitmap_vector_alloc (num_edges, n_exprs); + + /* Allocate an extra element for the entry block. */ + nearerout = sbitmap_vector_alloc (last_basic_block_for_fn (cfun) + 1, + n_exprs); + compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout); + +#ifdef LCM_DEBUG_INFO + if (dump_file) + { + dump_bitmap_vector (dump_file, "nearerout", "", nearerout, + last_basic_block_for_fn (cfun) + 1); + dump_bitmap_vector (dump_file, "nearer", "", nearer, num_edges); + } +#endif + + sbitmap_vector_free (farthest); + + *insert = sbitmap_vector_alloc (num_edges, n_exprs); + *del = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), n_exprs); + compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout, + *insert, *del); + + sbitmap_vector_free (nearerout); + sbitmap_vector_free (nearer); + +#ifdef LCM_DEBUG_INFO + if (dump_file) + { + dump_bitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges); + dump_bitmap_vector (dump_file, "pre_delete_map", "", *del, + last_basic_block_for_fn (cfun)); + } +#endif + return edge_list; +} + |