/* Integrated Register Allocator. Changing code and generating moves.
- Copyright (C) 2006, 2007, 2008
+ Copyright (C) 2006, 2007, 2008, 2009, 2010
Free Software Foundation, Inc.
Contributed by Vladimir Makarov <vmakarov@redhat.com>.
#include "tree-pass.h"
#include "output.h"
#include "reload.h"
-#include "errors.h"
#include "df.h"
#include "ira-int.h"
free_move_list (move_t head)
{
move_t next;
-
+
for (; head != NULL; head = next)
{
next = head->next;
return list1 == list2;
}
+/* Print move list LIST into file F. */
+static void
+print_move_list (FILE *f, move_t list)
+{
+ for (; list != NULL; list = list->next)
+ fprintf (f, " a%dr%d->a%dr%d",
+ ALLOCNO_NUM (list->from), ALLOCNO_REGNO (list->from),
+ ALLOCNO_NUM (list->to), ALLOCNO_REGNO (list->to));
+ fprintf (f, "\n");
+}
+
+extern void ira_debug_move_list (move_t list);
+
+/* Print move list LIST into stderr. */
+void
+ira_debug_move_list (move_t list)
+{
+ print_move_list (stderr, list);
+}
+
/* This recursive function changes pseudo-registers in *LOC if it is
necessary. The function returns TRUE if a change was done. */
static bool
}
}
-/* Return TRUE if move of SRC_ALLOCNO to DEST_ALLOCNO does not change
- value of the destination. One possible reason for this is the
- situation when SRC_ALLOCNO is not modified in the corresponding
- loop. */
+/* Return true if there is an entry to given loop not from its parent
+ (or grandparent) block. For example, it is possible for two
+ adjacent loops inside another loop. */
static bool
-not_modified_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
+entered_from_non_parent_p (ira_loop_tree_node_t loop_node)
+{
+ ira_loop_tree_node_t bb_node, src_loop_node, parent;
+ edge e;
+ edge_iterator ei;
+
+ for (bb_node = loop_node->children; bb_node != NULL; bb_node = bb_node->next)
+ if (bb_node->bb != NULL)
+ {
+ FOR_EACH_EDGE (e, ei, bb_node->bb->preds)
+ if (e->src != ENTRY_BLOCK_PTR
+ && (src_loop_node = IRA_BB_NODE (e->src)->parent) != loop_node)
+ {
+ for (parent = src_loop_node->parent;
+ parent != NULL;
+ parent = parent->parent)
+ if (parent == loop_node)
+ break;
+ if (parent != NULL)
+ /* That is an exit from a nested loop -- skip it. */
+ continue;
+ for (parent = loop_node->parent;
+ parent != NULL;
+ parent = parent->parent)
+ if (src_loop_node == parent)
+ break;
+ if (parent == NULL)
+ return true;
+ }
+ }
+ return false;
+}
+
+/* Set up ENTERED_FROM_NON_PARENT_P for each loop region. */
+static void
+setup_entered_from_non_parent_p (void)
+{
+ unsigned int i;
+ loop_p loop;
+
+ FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, i, loop)
+ if (ira_loop_nodes[i].regno_allocno_map != NULL)
+ ira_loop_nodes[i].entered_from_non_parent_p
+ = entered_from_non_parent_p (&ira_loop_nodes[i]);
+}
+
+/* Return TRUE if move of SRC_ALLOCNO (assigned to hard register) to
+ DEST_ALLOCNO (assigned to memory) can be removed beacuse it does
+ not change value of the destination. One possible reason for this
+ is the situation when SRC_ALLOCNO is not modified in the
+ corresponding loop. */
+static bool
+store_can_be_removed_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
{
int regno, orig_regno;
ira_allocno_t a;
for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno);
node != NULL;
node = node->parent)
- if ((a = node->regno_allocno_map[orig_regno]) == NULL)
- break;
- else if (REGNO (ALLOCNO_REG (a)) == (unsigned) regno)
- return true;
- else if (bitmap_bit_p (node->modified_regnos, orig_regno))
- return false;
- return node != NULL;
+ {
+ a = node->regno_allocno_map[orig_regno];
+ ira_assert (a != NULL);
+ if (REGNO (ALLOCNO_REG (a)) == (unsigned) regno)
+ /* We achieved the destination and everything is ok. */
+ return true;
+ else if (bitmap_bit_p (node->modified_regnos, orig_regno))
+ return false;
+ else if (node->entered_from_non_parent_p)
+ /* If there is a path from a destination loop block to the
+ source loop header containing basic blocks of non-parents
+ (grandparents) of the source loop, we should have checked
+ modifications of the pseudo on this path too to decide
+ about possibility to remove the store. It could be done by
+ solving a data-flow problem. Unfortunately such global
+ solution would complicate IR flattening. Therefore we just
+ prohibit removal of the store in such complicated case. */
+ return false;
+ }
+ /* It is actually a loop entry -- do not remove the store. */
+ return false;
}
/* Generate and attach moves to the edge E. This looks at the final
change_loop). */
if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
&& ALLOCNO_HARD_REGNO (src_allocno) >= 0
- && not_modified_p (src_allocno, dest_allocno))
+ && store_can_be_removed_p (src_allocno, dest_allocno))
{
ALLOCNO_MEM_OPTIMIZED_DEST (src_allocno) = dest_allocno;
ALLOCNO_MEM_OPTIMIZED_DEST_P (dest_allocno) = true;
if (node != ira_loop_tree_root)
{
-
+
if (node->bb != NULL)
{
FOR_BB_INSNS (node->bb, insn)
}
return;
}
-
+
if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
fprintf (ira_dump_file,
" Changing RTL for loop %d (header bb%d)\n",
node->loop->num, node->loop->header->index);
-
+
parent = ira_curr_loop_tree_node->parent;
map = parent->regno_allocno_map;
EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
regno = ALLOCNO_REGNO (allocno);
if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
continue;
- used_p = bitmap_bit_p (used_regno_bitmap, regno);
- bitmap_set_bit (used_regno_bitmap, regno);
+ used_p = !bitmap_set_bit (used_regno_bitmap, regno);
ALLOCNO_SOMEWHERE_RENAMED_P (allocno) = true;
if (! used_p)
continue;
modify_move_list (move_t list)
{
int i, n, nregs, hard_regno;
- ira_allocno_t to, from, new_allocno;
+ ira_allocno_t to, from;
move_t move, new_move, set_move, first, last;
if (list == NULL)
&& ALLOCNO_HARD_REGNO
(hard_regno_last_set[hard_regno + i]->to) >= 0)
{
+ int n, j;
+ ira_allocno_t new_allocno;
+
set_move = hard_regno_last_set[hard_regno + i];
/* It does not matter what loop_tree_node (of TO or
FROM) to use for the new allocno because of
ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
ira_set_allocno_cover_class
(new_allocno, ALLOCNO_COVER_CLASS (set_move->to));
+ ira_create_allocno_objects (new_allocno);
ALLOCNO_ASSIGNED_P (new_allocno) = true;
ALLOCNO_HARD_REGNO (new_allocno) = -1;
ALLOCNO_REG (new_allocno)
= create_new_reg (ALLOCNO_REG (set_move->to));
- ALLOCNO_CONFLICT_ID (new_allocno) = ALLOCNO_NUM (new_allocno);
+
/* Make it possibly conflicting with all earlier
created allocnos. Cases where temporary allocnos
created to remove the cycles are quite rare. */
- ALLOCNO_MIN (new_allocno) = 0;
- ALLOCNO_MAX (new_allocno) = ira_allocnos_num - 1;
+ n = ALLOCNO_NUM_OBJECTS (new_allocno);
+ gcc_assert (n == ALLOCNO_NUM_OBJECTS (set_move->to));
+ for (j = 0; j < n; j++)
+ {
+ ira_object_t new_obj = ALLOCNO_OBJECT (new_allocno, j);
+
+ OBJECT_MIN (new_obj) = 0;
+ OBJECT_MAX (new_obj) = ira_objects_num - 1;
+ }
+
new_move = create_move (set_move->to, new_allocno);
set_move->to = new_allocno;
VEC_safe_push (move_t, heap, move_vec, new_move);
}
else
{
- cost = ira_register_move_cost[mode][cover_class][cover_class] * freq;
+ cost = (ira_get_register_move_cost (mode, cover_class, cover_class)
+ * freq);
ira_shuffle_cost += cost;
}
ira_overall_cost += cost;
int start, n;
unsigned int regno;
move_t move;
- ira_allocno_t to, from, a;
+ ira_allocno_t a;
ira_copy_t cp;
- allocno_live_range_t r;
+ live_range_t r;
bitmap_iterator bi;
HARD_REG_SET hard_regs_live;
start = ira_max_point;
for (move = list; move != NULL; move = move->next)
{
- from = move->from;
- to = move->to;
- if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (to) == NULL)
- {
- if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
- fprintf (ira_dump_file, " Allocate conflicts for a%dr%d\n",
- ALLOCNO_NUM (to), REGNO (ALLOCNO_REG (to)));
- ira_allocate_allocno_conflicts (to, n);
- }
+ ira_allocno_t from = move->from;
+ ira_allocno_t to = move->to;
+ int nr, i;
+
bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
- IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (from), hard_regs_live);
- IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (to), hard_regs_live);
- IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (from),
- hard_regs_live);
- IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (to), hard_regs_live);
+
+ nr = ALLOCNO_NUM_OBJECTS (to);
+ for (i = 0; i < nr; i++)
+ {
+ ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
+ if (OBJECT_CONFLICT_ARRAY (to_obj) == NULL)
+ {
+ if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
+ fprintf (ira_dump_file, " Allocate conflicts for a%dr%d\n",
+ ALLOCNO_NUM (to), REGNO (ALLOCNO_REG (to)));
+ ira_allocate_object_conflicts (to_obj, n);
+ }
+ }
+ ior_hard_reg_conflicts (from, &hard_regs_live);
+ ior_hard_reg_conflicts (to, &hard_regs_live);
+
update_costs (from, true, freq);
update_costs (to, false, freq);
- cp = ira_add_allocno_copy (from, to, freq, move->insn, NULL);
+ cp = ira_add_allocno_copy (from, to, freq, false, move->insn, NULL);
if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
fprintf (ira_dump_file, " Adding cp%d:a%dr%d-a%dr%d\n",
cp->num, ALLOCNO_NUM (cp->first),
REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second),
REGNO (ALLOCNO_REG (cp->second)));
- r = ALLOCNO_LIVE_RANGES (from);
- if (r == NULL || r->finish >= 0)
+
+ nr = ALLOCNO_NUM_OBJECTS (from);
+ for (i = 0; i < nr; i++)
{
- ALLOCNO_LIVE_RANGES (from)
- = ira_create_allocno_live_range (from, start, ira_max_point, r);
- if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
- fprintf (ira_dump_file,
- " Adding range [%d..%d] to allocno a%dr%d\n",
- start, ira_max_point, ALLOCNO_NUM (from),
- REGNO (ALLOCNO_REG (from)));
+ ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
+ r = OBJECT_LIVE_RANGES (from_obj);
+ if (r == NULL || r->finish >= 0)
+ {
+ ira_add_live_range_to_object (from_obj, start, ira_max_point);
+ if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
+ fprintf (ira_dump_file,
+ " Adding range [%d..%d] to allocno a%dr%d\n",
+ start, ira_max_point, ALLOCNO_NUM (from),
+ REGNO (ALLOCNO_REG (from)));
+ }
+ else
+ {
+ r->finish = ira_max_point;
+ if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
+ fprintf (ira_dump_file,
+ " Adding range [%d..%d] to allocno a%dr%d\n",
+ r->start, ira_max_point, ALLOCNO_NUM (from),
+ REGNO (ALLOCNO_REG (from)));
+ }
}
- else
- r->finish = ira_max_point;
ira_max_point++;
- ALLOCNO_LIVE_RANGES (to)
- = ira_create_allocno_live_range (to, ira_max_point, -1,
- ALLOCNO_LIVE_RANGES (to));
+ nr = ALLOCNO_NUM_OBJECTS (to);
+ for (i = 0; i < nr; i++)
+ {
+ ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
+ ira_add_live_range_to_object (to_obj, ira_max_point, -1);
+ }
ira_max_point++;
}
for (move = list; move != NULL; move = move->next)
{
- r = ALLOCNO_LIVE_RANGES (move->to);
- if (r->finish < 0)
+ int nr, i;
+ nr = ALLOCNO_NUM_OBJECTS (move->to);
+ for (i = 0; i < nr; i++)
{
- r->finish = ira_max_point - 1;
- if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
- fprintf (ira_dump_file,
- " Adding range [%d..%d] to allocno a%dr%d\n",
- r->start, r->finish, ALLOCNO_NUM (move->to),
- REGNO (ALLOCNO_REG (move->to)));
+ ira_object_t to_obj = ALLOCNO_OBJECT (move->to, i);
+ r = OBJECT_LIVE_RANGES (to_obj);
+ if (r->finish < 0)
+ {
+ r->finish = ira_max_point - 1;
+ if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
+ fprintf (ira_dump_file,
+ " Adding range [%d..%d] to allocno a%dr%d\n",
+ r->start, r->finish, ALLOCNO_NUM (move->to),
+ REGNO (ALLOCNO_REG (move->to)));
+ }
}
}
EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
{
+ ira_allocno_t to;
+ int nr, i;
+
a = node->regno_allocno_map[regno];
- if (ALLOCNO_MEM_OPTIMIZED_DEST (a) == NULL)
+ if ((to = ALLOCNO_MEM_OPTIMIZED_DEST (a)) != NULL)
+ a = to;
+ nr = ALLOCNO_NUM_OBJECTS (a);
+ for (i = 0; i < nr; i++)
{
- ALLOCNO_LIVE_RANGES (a)
- = ira_create_allocno_live_range (a, start, ira_max_point - 1,
- ALLOCNO_LIVE_RANGES (a));
- if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
- fprintf
- (ira_dump_file,
- " Adding range [%d..%d] to live through allocno a%dr%d\n",
- start, ira_max_point - 1, ALLOCNO_NUM (a),
- REGNO (ALLOCNO_REG (a)));
+ ira_object_t obj = ALLOCNO_OBJECT (a, i);
+ ira_add_live_range_to_object (obj, start, ira_max_point - 1);
}
+ if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
+ fprintf
+ (ira_dump_file,
+ " Adding range [%d..%d] to live through %s allocno a%dr%d\n",
+ start, ira_max_point - 1,
+ to != NULL ? "upper level" : "",
+ ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)));
}
}
ira_emit (bool loops_p)
{
basic_block bb;
+ rtx insn;
edge_iterator ei;
edge e;
ira_allocno_t a;
ira_free_bitmap (used_regno_bitmap);
ira_free_bitmap (renamed_regno_bitmap);
ira_free_bitmap (local_allocno_bitmap);
+ setup_entered_from_non_parent_p ();
FOR_EACH_BB (bb)
{
at_bb_start[bb->index] = NULL;
ira_free (allocno_last_set_check);
ira_free (allocno_last_set);
commit_edge_insertions ();
+ /* Fix insn codes. It is necessary to do it before reload because
+ reload assumes initial insn codes defined. The insn codes can be
+ invalidated by CFG infrastructure for example in jump
+ redirection. */
+ FOR_EACH_BB (bb)
+ FOR_BB_INSNS_REVERSE (bb, insn)
+ if (INSN_P (insn))
+ recog_memoized (insn);
ira_free (at_bb_end);
ira_free (at_bb_start);
}
OSDN Git Service
