On 12-10-02 9:42 AM, Richard Sandiford wrote:
Vladimir Makarov <vmaka...@redhat.com> writes:
This is the major patch containing all new files. The patch also adds
necessary calls to LRA from IRA.As the patch is too big, it continues in
the next email.
2012-09-27 Vladimir Makarov <vmaka...@redhat.com>
* Makefile.in (LRA_INT_H): New.
(OBJS): Add lra.o, lra-assigns.o, lra-coalesce.o,
lra-constraints.o, lra-eliminations.o, lra-lives.o, and lra-spills.o.
(ira.o): Add dependence on lra.h.
(lra.o, lra-assigns.o, lra-coalesce.o, lra-constraints.o): New entries.
(lra-eliminations.o, lra-lives.o, lra-spills.o): Ditto.
* ira.c: Include lra.h.
(ira_init_once, ira_init, ira_finish_once): Call lra_start_once,
lra_init, lra_finish_once in anyway.
(lra_in_progress): Remove.
(do_reload): Call LRA.
* lra.h: New.
* lra-int.h: Ditto.
* lra.c: Ditto.
* lra-assigns.c: Ditto.
* lra-constraints.c: Ditto.
* lra-coalesce.c: Ditto.
* lra-eliminations.c: Ditto.
* lra-lives.c: Ditto.
* lra-spills.c: Ditto.
* doc/passes.texi: Describe LRA pass.
Comments on ira-lives.c. (Sorry for the split, had more time to look
at this than expected)
+/* Copy live range list given by its head R and return the result. */
+lra_live_range_t
+lra_copy_live_range_list (lra_live_range_t r)
+{
+ lra_live_range_t p, first, last;
+
+ if (r == NULL)
+ return NULL;
+ for (first = last = NULL; r != NULL; r = r->next)
+ {
+ p = copy_live_range (r);
+ if (first == NULL)
+ first = p;
+ else
+ last->next = p;
+ last = p;
+ }
+ return first;
+}
Maybe simpler as:
lra_live_range_t p, first, *chain;
first = NULL;
for (chain = &first; r != NULL; r = r->next)
{
p = copy_live_range (r);
*chain = p;
chain = &p->next;
}
return first;
OK.
+/* Merge ranges R1 and R2 and returns the result. The function
+ maintains the order of ranges and tries to minimize size of the
+ result range list. */
+lra_live_range_t
+lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2)
+{
+ lra_live_range_t first, last, temp;
+
+ if (r1 == NULL)
+ return r2;
+ if (r2 == NULL)
+ return r1;
+ for (first = last = NULL; r1 != NULL && r2 != NULL;)
+ {
+ if (r1->start < r2->start)
+ {
+ temp = r1;
+ r1 = r2;
+ r2 = temp;
+ }
+ if (r1->start <= r2->finish + 1)
+ {
+ /* Intersected ranges: merge r1 and r2 into r1. */
+ r1->start = r2->start;
+ if (r1->finish < r2->finish)
+ r1->finish = r2->finish;
+ temp = r2;
+ r2 = r2->next;
+ pool_free (live_range_pool, temp);
+ if (r2 == NULL)
+ {
+ /* To try to merge with subsequent ranges in r1. */
+ r2 = r1->next;
+ r1->next = NULL;
+ }
+ }
+ else
+ {
+ /* Add r1 to the result. */
+ if (first == NULL)
+ first = last = r1;
+ else
+ {
+ last->next = r1;
+ last = r1;
+ }
+ r1 = r1->next;
+ if (r1 == NULL)
+ {
+ /* To try to merge with subsequent ranges in r2. */
+ r1 = r2->next;
+ r2->next = NULL;
+ }
+ }
I might be misreading, but I'm not sure whether this handles merges like:
r1 = [6,7], [3,4]
r2 = [3,8], [0,1]
After the first iteration, it looks like we'll have:
r1 = [3,8], [3,4]
r2 = [0,1]
Then we'll add both [3,8] and [3,4] to the result.
Same chain pointer comment as for lra_merge_live_ranges.
+/* Return TRUE if live range R1 is in R2. */
+bool
+lra_live_range_in_p (lra_live_range_t r1, lra_live_range_t r2)
+{
+ /* Remember the live ranges are always kept ordered. */
+ while (r1 != NULL && r2 != NULL)
+ {
+ /* R1's element is in R2's element. */
+ if (r2->start <= r1->start && r1->finish <= r2->finish)
+ r1 = r1->next;
+ /* Intersection: R1's start is in R2. */
+ else if (r2->start <= r1->start && r1->start <= r2->finish)
+ return false;
+ /* Intersection: R1's finish is in R2. */
+ else if (r2->start <= r1->finish && r1->finish <= r2->finish)
+ return false;
+ else if (r1->start > r2->finish)
+ return false; /* No covering R2's element for R1's one. */
+ else
+ r2 = r2->next;
+ }
+ return r1 == NULL;
Does the inner bit reduce to:
/* R1's element is in R2's element. */
if (r2->start <= r1->start && r1->finish <= r2->finish)
r1 = r1->next;
/* All of R2's element comes after R1's element. */
else if (r2->start > r1->finish)
r2 = r2->next;
else
return false;
Yes. It seems to me the right change. I found that this function is not
used in LRA anymore. So I am just removing the function. Sorry for
wasting your time reviewing this.
I wrote this function when experimented with more sophisticated
algorithms of range compression. It might be needed in future. So I
keep it in my mind.
(Genuine question)
+/* Process the death of hard register REGNO. This updates
+ hard_regs_live and START_DYING. */
+static void
+make_hard_regno_dead (int regno)
+{
+ if (TEST_HARD_REG_BIT (lra_no_alloc_regs, regno)
+ || ! TEST_HARD_REG_BIT (hard_regs_live, regno))
+ return;
+ lra_assert (regno < FIRST_PSEUDO_REGISTER);
+ sparseset_set_bit (start_dying, regno);
+ CLEAR_HARD_REG_BIT (hard_regs_live, regno);
+}
Assert should be before the HARD_REG_SET stuff (like for
make_hard_regno_born).
Fixed. Thanks.
+ /* Check that source regno does not conflict with
+ destination regno to exclude most impossible
+ preferences. */
+ && ((((src_regno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
+ && ! sparseset_bit_p (pseudos_live, src_regno))
+ || (src_regno < FIRST_PSEUDO_REGISTER
+ && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
This is probably personal preference, but I think this would be more
readable with an inline utility function (regno_live_p, or whatever).
It might be. But as the code is only in one place, I'd rather not
change it.
+/* Compress pseudo live ranges by removing program points where
+ nothing happens. Complexity of many algorithms in LRA is linear
+ function of program points number. To speed up the code we try to
+ minimize the number of the program points here. */
+static void
+remove_some_program_points_and_update_live_ranges (void)
Genuine question, but could we do this on the fly instead,
by not incrementing curr_point if the current point had no value?
I suppose the main complication would be checking cases where
all births are recorded by extending the previous just-closed live
range rather than starting a new one, in which case it's the previous
point that needs to be reused. Hmm...
I thought about this when I wrote the code. I believed it is not
critical code and wrote it simple. Apparently I was wrong. Minimizing
ranges during creation is time critical for the huge tests. As you
probably saw, it was changed by recent patches. There are still a
potential to speed up this code even more for the huge functions.
