/* Generic partial redundancy elimination with lazy code motion support.
- Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
+ Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
-This file is part of GNU CC.
+This file is part of GCC.
-GNU CC 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 2, or (at your option)
-any later version.
+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 2, or (at your option) any later
+version.
-GNU CC 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.
+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 GNU CC; see the file COPYING. If not, write to
-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA. */
/* These routines are meant to be used by various optimization
- passes which can be modeled as lazy code motion problems.
+ passes which can be modeled as lazy code motion problems.
Including, but not limited to:
* Traditional partial redundancy elimination.
\f
/* 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.
+/* 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
*qin++ = BASIC_BLOCK (bb);
BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
}
-
+
qin = worklist;
qend = &worklist[n_basic_blocks];
qlen = n_basic_blocks;
}
}
+ clear_aux_for_edges ();
+ clear_aux_for_blocks ();
free (worklist);
}
sbitmap *antin, *antout, *avout, *kill, *earliest;
{
sbitmap difference, temp_bitmap;
- int x, num_edges;
+ int x, num_edges;
basic_block pred, succ;
num_edges = NUM_EDGES (edge_list);
sbitmap_copy (earliest[x], antin[succ->index]);
else
{
- if (succ == EXIT_BLOCK_PTR)
+ /* We refer to the EXIT_BLOCK index, instead of testing for
+ EXIT_BLOCK_PTR, so that EXIT_BLOCK_PTR's index can be
+ changed so as to pretend it's a regular block, so that
+ its antin can be taken into account. */
+ if (succ->index == EXIT_BLOCK)
sbitmap_zero (earliest[x]);
else
{
- sbitmap_difference (difference, antin[succ->index],
- avout[pred->index]);
+ sbitmap_difference (difference, antin[succ->index],
+ avout[pred->index]);
sbitmap_not (temp_bitmap, antout[pred->index]);
sbitmap_a_and_b_or_c (earliest[x], difference,
kill[pred->index], temp_bitmap);
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 (edge_list, earliest, antloc, later, laterin)
struct edge_list *edge_list;
qin = worklist;
/* Note that we do not use the last allocated element for our queue,
as EXIT_BLOCK is never inserted into it. In fact the above allocation
- of n_basic_blocks + 1 elements is not encessary. */
+ of n_basic_blocks + 1 elements is not encessary. */
qend = &worklist[n_basic_blocks];
qlen = n_basic_blocks;
laterin[n_basic_blocks],
later[(size_t) e->aux]);
+ clear_aux_for_edges ();
free (worklist);
}
for (x = 0; x < n_basic_blocks; x++)
sbitmap_difference (delete[x], antloc[x], laterin[x]);
-
+
for (x = 0; x < NUM_EDGES (edge_list); x++)
{
basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
avin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
avout = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
compute_available (avloc, kill, avout, avin);
- free (avin);
+ sbitmap_vector_free (avin);
/* Compute global anticipatability. */
antin = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
dump_sbitmap_vector (file, "earliest", "", earliest, num_edges);
#endif
- free (antout);
- free (antin);
- free (avout);
+ sbitmap_vector_free (antout);
+ sbitmap_vector_free (antin);
+ sbitmap_vector_free (avout);
later = sbitmap_vector_alloc (num_edges, n_exprs);
}
#endif
- free (earliest);
+ sbitmap_vector_free (earliest);
*insert = sbitmap_vector_alloc (num_edges, n_exprs);
*delete = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
compute_insert_delete (edge_list, antloc, later, laterin, *insert, *delete);
- free (laterin);
- free (later);
+ sbitmap_vector_free (laterin);
+ sbitmap_vector_free (later);
#ifdef LCM_DEBUG_INFO
if (file)
void
compute_available (avloc, kill, avout, avin)
- sbitmap *avloc, *kill, *avout, *avin;
+ sbitmap *avloc, *kill, *avout, *avin;
{
int bb;
edge e;
*qin++ = BASIC_BLOCK (bb);
BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
}
-
+
qin = worklist;
qend = &worklist[n_basic_blocks];
qlen = n_basic_blocks;
}
}
+ clear_aux_for_edges ();
+ clear_aux_for_blocks ();
free (worklist);
}
/* Compute the farthest vector for edge based lcm. */
static void
-compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
+compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
kill, farthest)
struct edge_list *edge_list;
int n_exprs;
sbitmap *st_avout, *st_avin, *st_antin, *kill, *farthest;
{
sbitmap difference, temp_bitmap;
- int x, num_edges;
+ int x, num_edges;
basic_block pred, succ;
num_edges = NUM_EDGES (edge_list);
sbitmap_zero (farthest[x]);
else
{
- sbitmap_difference (difference, st_avout[pred->index],
+ sbitmap_difference (difference, st_avout[pred->index],
st_antin[succ->index]);
sbitmap_not (temp_bitmap, st_avin[succ->index]);
- sbitmap_a_and_b_or_c (farthest[x], difference,
+ sbitmap_a_and_b_or_c (farthest[x], difference,
kill[succ->index], temp_bitmap);
}
}
*tos++ = b;
b->aux = b;
}
-
+
/* Iterate until the worklist is empty. */
while (tos != worklist)
{
nearerout[n_basic_blocks],
nearer[(size_t) e->aux]);
+ clear_aux_for_edges ();
free (tos);
}
for (x = 0; x < n_basic_blocks; x++)
sbitmap_difference (delete[x], st_avloc[x], nearerout[x]);
-
+
for (x = 0; x < NUM_EDGES (edge_list); x++)
{
basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
}
}
-/* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
+/* 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 (file, n_exprs, transp, st_avloc, st_antloc, kill,
+pre_edge_rev_lcm (file, n_exprs, transp, st_avloc, st_antloc, kill,
insert, delete)
FILE *file ATTRIBUTE_UNUSED;
int n_exprs;
/* Compute farthestness. */
farthest = sbitmap_vector_alloc (num_edges, n_exprs);
- compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
+ compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
kill, farthest);
#ifdef LCM_DEBUG_INFO
dump_sbitmap_vector (file, "farthest", "", farthest, num_edges);
#endif
- free (st_avin);
- free (st_avout);
+ 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);
#ifdef LCM_DEBUG_INFO
if (file)
{
- dump_sbitmap_vector (file, "nearerout", "", nearerout,
+ dump_sbitmap_vector (file, "nearerout", "", nearerout,
n_basic_blocks + 1);
dump_sbitmap_vector (file, "nearer", "", nearer, num_edges);
}
#endif
- free (farthest);
+ sbitmap_vector_free (farthest);
*insert = sbitmap_vector_alloc (num_edges, n_exprs);
*delete = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
*insert, *delete);
- free (nearerout);
- free (nearer);
+ sbitmap_vector_free (nearerout);
+ sbitmap_vector_free (nearer);
#ifdef LCM_DEBUG_INFO
if (file)
n_basic_blocks);
}
#endif
-
return edge_list;
}
More details are located in the code for optimize_mode_switching(). */
/* This structure contains the information for each insn which requires
- either single or double mode to be set.
+ either single or double mode to be set.
MODE is the mode this insn must be executed in.
INSN_PTR is the insn to be executed (may be the note that marks the
beginning of a basic block).
BBNUM is the flow graph basic block this insn occurs in.
NEXT is the next insn in the same basic block. */
-struct seginfo
+struct seginfo
{
int mode;
rtx insn_ptr;
return ptr;
}
-/* Add a seginfo element to the end of a list.
+/* Add a seginfo element to the end of a list.
HEAD is a pointer to the list beginning.
INFO is the structure to be linked in. */
{
rtx insn;
int bb, e;
- edge eg;
int need_commit = 0;
sbitmap *kill;
struct edge_list *edge_list;
- static int num_modes[] = NUM_MODES_FOR_MODE_SWITCHING;
+ static const int num_modes[] = NUM_MODES_FOR_MODE_SWITCHING;
#define N_ENTITIES (sizeof num_modes / sizeof (int))
int entity_map[N_ENTITIES];
struct bb_info *bb_info[N_ENTITIES];
int i, j;
int n_entities;
int max_num_modes = 0;
+ bool emited = false;
+
+#ifdef NORMAL_MODE
+ /* Increment n_basic_blocks before allocating bb_info. */
+ n_basic_blocks++;
+#endif
for (e = N_ENTITIES - 1, n_entities = 0; e >= 0; e--)
if (OPTIMIZE_MODE_SWITCHING (e))
max_num_modes = num_modes[e];
}
+#ifdef NORMAL_MODE
+ /* Decrement it back in case we return below. */
+ n_basic_blocks--;
+#endif
+
if (! n_entities)
return 0;
+#ifdef NORMAL_MODE
+ /* We're going to pretend the EXIT_BLOCK is a regular basic block,
+ so that switching back to normal mode when entering the
+ EXIT_BLOCK isn't optimized away. We do this by incrementing the
+ basic block count, growing the VARRAY of basic_block_info and
+ appending the EXIT_BLOCK_PTR to it. */
+ n_basic_blocks++;
+ if (VARRAY_SIZE (basic_block_info) < n_basic_blocks)
+ VARRAY_GROW (basic_block_info, n_basic_blocks);
+ BASIC_BLOCK (n_basic_blocks - 1) = EXIT_BLOCK_PTR;
+ EXIT_BLOCK_PTR->index = n_basic_blocks - 1;
+#endif
+
/* Create the bitmap vectors. */
antic = sbitmap_vector_alloc (n_basic_blocks, n_entities);
REG_SET_TO_HARD_REG_SET (live_now,
BASIC_BLOCK (bb)->global_live_at_start);
- for (insn = BLOCK_HEAD (bb);
+ for (insn = BLOCK_HEAD (bb);
insn != NULL && insn != NEXT_INSN (BLOCK_END (bb));
insn = NEXT_INSN (insn))
{
}
}
- /* If this is a predecessor of the exit block, and we must
- force a mode on exit, make note of that. */
-#ifdef NORMAL_MODE
- if (NORMAL_MODE (e) != no_mode && last_mode != NORMAL_MODE (e))
- for (eg = BASIC_BLOCK (bb)->succ; eg; eg = eg->succ_next)
- if (eg->dest == EXIT_BLOCK_PTR)
- {
- rtx insn = BLOCK_END (bb);
-
- /* Find the last insn before a USE and/or JUMP. */
- while ((GET_CODE (insn) == INSN
- && GET_CODE (PATTERN (insn)) == USE)
- || GET_CODE (insn) == JUMP_INSN)
- insn = PREV_INSN (insn);
- if (insn != BLOCK_END (bb) && NEXT_INSN (insn))
- insn = NEXT_INSN (insn);
- last_mode = NORMAL_MODE (e);
- add_seginfo (info + bb,
- new_seginfo (last_mode, insn, bb, live_now));
- RESET_BIT (transp[bb], j);
- }
-#endif
-
info[bb].computing = last_mode;
/* Check for blocks without ANY mode requirements. */
if (last_mode == no_mode)
if (mode != no_mode)
{
+ edge eg;
+
for (eg = ENTRY_BLOCK_PTR->succ; eg; eg = eg->succ_next)
{
bb = eg->dest->index;
info[bb].seginfo->mode = no_mode;
}
}
+
+ bb = n_basic_blocks - 1;
+ info[bb].seginfo->mode = mode;
}
}
#endif /* NORMAL_MODE */
{
int m = current_mode[j] = MODE_PRIORITY_TO_MODE (entity_map[j], i);
struct bb_info *info = bb_info[j];
-
+
for (bb = 0 ; bb < n_basic_blocks; bb++)
{
if (info[bb].seginfo->mode == m)
mode_set = gen_sequence ();
end_sequence ();
- /* If this is an abnormal edge, we'll insert at the end of the
- previous block. */
+ /* Do not bother to insert empty sequence. */
+ if (GET_CODE (mode_set) == SEQUENCE
+ && !XVECLEN (mode_set, 0))
+ continue;
+
+ /* If this is an abnormal edge, we'll insert at the end
+ of the previous block. */
if (eg->flags & EDGE_ABNORMAL)
{
+ emited = true;
if (GET_CODE (src_bb->end) == JUMP_INSN)
emit_insn_before (mode_set, src_bb->end);
+ /* It doesn't make sense to switch to normal mode
+ after a CALL_INSN, so we're going to abort if we
+ find one. The cases in which a CALL_INSN may
+ have an abnormal edge are sibcalls and EH edges.
+ In the case of sibcalls, the dest basic-block is
+ the EXIT_BLOCK, that runs in normal mode; it is
+ assumed that a sibcall insn requires normal mode
+ itself, so no mode switch would be required after
+ the call (it wouldn't make sense, anyway). In
+ the case of EH edges, EH entry points also start
+ in normal mode, so a similar reasoning applies. */
+ else if (GET_CODE (src_bb->end) == INSN)
+ emit_insn_after (mode_set, src_bb->end);
else
- src_bb->end = emit_insn_after (mode_set, src_bb->end);
+ abort ();
bb_info[j][src_bb->index].computing = mode;
RESET_BIT (transp[src_bb->index], j);
}
}
}
+ clear_aux_for_edges ();
free_edge_list (edge_list);
}
+#ifdef NORMAL_MODE
+ /* Restore the special status of EXIT_BLOCK. */
+ n_basic_blocks--;
+ VARRAY_POP (basic_block_info);
+ EXIT_BLOCK_PTR->index = EXIT_BLOCK;
+#endif
+
/* Now output the remaining mode sets in all the segments. */
for (j = n_entities - 1; j >= 0; j--)
{
int no_mode = num_modes[entity_map[j]];
+#ifdef NORMAL_MODE
+ if (bb_info[j][n_basic_blocks].seginfo->mode != no_mode)
+ {
+ edge eg;
+ struct seginfo *ptr = bb_info[j][n_basic_blocks].seginfo;
+
+ for (eg = EXIT_BLOCK_PTR->pred; eg; eg = eg->pred_next)
+ {
+ rtx mode_set;
+
+ if (bb_info[j][eg->src->index].computing == ptr->mode)
+ continue;
+
+ start_sequence ();
+ EMIT_MODE_SET (entity_map[j], ptr->mode, ptr->regs_live);
+ mode_set = gen_sequence ();
+ end_sequence ();
+
+ /* Do not bother to insert empty sequence. */
+ if (GET_CODE (mode_set) == SEQUENCE
+ && !XVECLEN (mode_set, 0))
+ continue;
+
+ /* If this is an abnormal edge, we'll insert at the end of the
+ previous block. */
+ if (eg->flags & EDGE_ABNORMAL)
+ {
+ emited = true;
+ if (GET_CODE (eg->src->end) == JUMP_INSN)
+ emit_insn_before (mode_set, eg->src->end);
+ else if (GET_CODE (eg->src->end) == INSN)
+ emit_insn_after (mode_set, eg->src->end);
+ else
+ abort ();
+ }
+ else
+ {
+ need_commit = 1;
+ insert_insn_on_edge (mode_set, eg);
+ }
+ }
+
+ }
+#endif
+
for (bb = n_basic_blocks - 1; bb >= 0; bb--)
{
struct seginfo *ptr, *next;
mode_set = gen_sequence ();
end_sequence ();
+ /* Do not bother to insert empty sequence. */
+ if (GET_CODE (mode_set) == SEQUENCE
+ && !XVECLEN (mode_set, 0))
+ continue;
+
+ emited = true;
if (GET_CODE (ptr->insn_ptr) == NOTE
&& (NOTE_LINE_NUMBER (ptr->insn_ptr)
== NOTE_INSN_BASIC_BLOCK))
- emit_block_insn_after (mode_set, ptr->insn_ptr,
- BASIC_BLOCK (ptr->bbnum));
+ emit_insn_after (mode_set, ptr->insn_ptr);
else
- emit_block_insn_before (mode_set, ptr->insn_ptr,
- BASIC_BLOCK (ptr->bbnum));
+ emit_insn_before (mode_set, ptr->insn_ptr);
}
free (ptr);
}
/* Finished. Free up all the things we've allocated. */
-
+
sbitmap_vector_free (kill);
sbitmap_vector_free (antic);
sbitmap_vector_free (transp);
if (need_commit)
commit_edge_insertions ();
+ if (!need_commit && !emited)
+ return 0;
+
/* Ideally we'd figure out what blocks were affected and start from
there, but this is enormously complicated by commit_edge_insertions,
- which would screw up any indicies we'd collected, and also need to
+ which would screw up any indices we'd collected, and also need to
be involved in the update. Bail and recompute global life info for
everything. */
OSDN Git Service
