/* 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
+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 (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
+ 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
-not_modified_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
+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;
+ }
+ gcc_unreachable ();
}
/* 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,
}
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;
REGNO (ALLOCNO_REG (from)));
}
else
- r->finish = ira_max_point;
+ {
+ 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)));
+ }
ira_max_point++;
ALLOCNO_LIVE_RANGES (to)
= ira_create_allocno_live_range (to, ira_max_point, -1,
EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
{
a = node->regno_allocno_map[regno];
- if (ALLOCNO_MEM_OPTIMIZED_DEST (a) == NULL)
- {
- 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)));
- }
+ if ((to = ALLOCNO_MEM_OPTIMIZED_DEST (a)) != NULL)
+ a = to;
+ 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 %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);
}