RFC: LRA for x86/x86-64 [7/9]

[Richard Sandiford]

Richard Sandiford <rdsandiford@googlemail.com> writes:
>> +/* 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.

OK, so I start to read patch b and realise that this is only supposed to
handle non-overlapping live ranges.  It might be worth having a comment
and assert to that effect, for slow readers like me.

Although in that case the function feels a little more complicated than
it needs to be.  When we run out of R1 or R2, why not just use the other
one as the rest of the live range list?  Why is:

>> +	  if (r1 == NULL)
>> +	    {
>> +	      /* To try to merge with subsequent ranges in r2.	*/
>> +	      r1 = r2->next;
>> +	      r2->next = NULL;
>> +	    }

needed?

Richard