/* Generic partial redundancy elimination with lazy code motion support.
- Copyright (C) 1998-2013 Free Software Foundation, Inc.
+ Copyright (C) 1998-2015 Free Software Foundation, Inc.
This file is part of GCC.
#include "flags.h"
#include "insn-config.h"
#include "recog.h"
+#include "predict.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfganal.h"
+#include "lcm.h"
#include "basic-block.h"
#include "tm_p.h"
-#include "function.h"
#include "sbitmap.h"
#include "dumpfile.h"
/* We want a maximal solution, so make an optimistic initialization of
ANTIN. */
- bitmap_vector_ones (antin, last_basic_block);
+ 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. */
- FOR_EACH_BB_REVERSE (bb)
+ 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];
/* Add all the blocks to the worklist. This prevents an early exit from
the loop given our optimistic initialization of LATER above. */
- FOR_EACH_BB (bb)
+ int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
+ int postorder_num = inverted_post_order_compute (postorder);
+ for (int i = 0; i < postorder_num; ++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;
}
+ free (postorder);
/* Note that we do not use the last allocated element for our queue,
as EXIT_BLOCK is never inserted into it. */
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]);
+ 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[e->src->index],
- antloc[e->src->index])
+ 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)
/* 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]);
+ 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],
- laterin[last_basic_block],
- later[(size_t) e->aux]);
+ 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);
int x;
basic_block bb;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
bitmap_and_compl (del[bb->index], antloc[bb->index],
laterin[bb->index]);
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]);
+ 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, AVOUT, KILL return the insert and
- delete vectors for edge based LCM. Returns an edgelist which is used to
+/* 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 (int n_exprs, sbitmap *transp,
+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 *avin, *avout;
sbitmap *later, *laterin;
struct edge_list *edge_list;
int num_edges;
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);
- dump_bitmap_vector (dump_file, "antloc", "", antloc, last_basic_block);
- dump_bitmap_vector (dump_file, "avloc", "", avloc, last_basic_block);
- dump_bitmap_vector (dump_file, "kill", "", kill, last_basic_block);
+ 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. */
- avin = sbitmap_vector_alloc (last_basic_block, n_exprs);
- avout = sbitmap_vector_alloc (last_basic_block, n_exprs);
compute_available (avloc, kill, avout, avin);
- sbitmap_vector_free (avin);
/* Compute global anticipatability. */
- antin = sbitmap_vector_alloc (last_basic_block, n_exprs);
- antout = sbitmap_vector_alloc (last_basic_block, n_exprs);
+ 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);
- dump_bitmap_vector (dump_file, "antout", "", antout, last_basic_block);
+ 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
sbitmap_vector_free (antout);
sbitmap_vector_free (antin);
- sbitmap_vector_free (avout);
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 + 1, n_exprs);
+ 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 + 1);
+ 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, 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);
+ bitmap_vector_clear (*del, last_basic_block_for_fn (cfun));
compute_insert_delete (edge_list, antloc, later, laterin, *insert, *del);
sbitmap_vector_free (laterin);
{
dump_bitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
dump_bitmap_vector (dump_file, "pre_delete_map", "", *del,
- last_basic_block);
+ 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. */
XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
/* We want a maximal solution. */
- bitmap_vector_ones (avout, last_basic_block);
+ 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. */
- FOR_EACH_BB (bb)
+ optimistic initialization of AVOUT above. Use inverted postorder
+ to make the dataflow problem require less iterations. */
+ int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
+ int postorder_num = inverted_post_order_compute (postorder);
+ for (int i = 0; i < postorder_num; ++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;
}
+ free (postorder);
qin = worklist;
qend = &worklist[n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS];
/* Add all the blocks to the worklist. This prevents an early exit
from the loop given our optimistic initialization of NEARER. */
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
*tos++ = bb;
bb->aux = bb;
/* 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]);
+ 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],
- nearerout[last_basic_block],
+ 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 ();
int x;
basic_block bb;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
bitmap_and_compl (del[bb->index], st_avloc[bb->index],
nearerout[bb->index]);
{
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]);
+ 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]);
}
edge_list = create_edge_list ();
num_edges = NUM_EDGES (edge_list);
- st_antin = sbitmap_vector_alloc (last_basic_block, n_exprs);
- st_antout = sbitmap_vector_alloc (last_basic_block, n_exprs);
- bitmap_vector_clear (st_antin, last_basic_block);
- bitmap_vector_clear (st_antout, last_basic_block);
+ 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, n_exprs);
- st_avin = sbitmap_vector_alloc (last_basic_block, n_exprs);
+ 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
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);
- dump_bitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block);
- dump_bitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
- dump_bitmap_vector (dump_file, "st_antin", "", st_antin, last_basic_block);
- dump_bitmap_vector (dump_file, "st_antout", "", st_antout, last_basic_block);
- dump_bitmap_vector (dump_file, "st_kill", "", kill, last_basic_block);
+ 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);
- dump_bitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block);
+ 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
nearer = sbitmap_vector_alloc (num_edges, n_exprs);
/* Allocate an extra element for the entry block. */
- nearerout = sbitmap_vector_alloc (last_basic_block + 1, n_exprs);
+ 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 + 1);
+ 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, 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);
{
dump_bitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
dump_bitmap_vector (dump_file, "pre_delete_map", "", *del,
- last_basic_block);
+ last_basic_block_for_fn (cfun));
}
#endif
return edge_list;
projects / gcc.git / blobdiff