Vladimir Makarov <[email protected]> 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 <[email protected]>
>
> * 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;
> +/* 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;
(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).
> + /* 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).
> +/* 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...
Richard
