[LLVMdev] [PATCH] Re: Pluggable Register Coalescers

[David Greene]

On Monday 16 July 2007 18:20, Evan Cheng wrote:

> > Does the current implementation follow a published algorithm?  If
> > so, do we
> > have a pointer to it?  The comments are rather sparse and it's
> > difficult to
> > figure out what's going on at times.
>
> I don't know. I suspect not. I agree the current implementation is a
> bit of a challenge to understand and modify.

I actually managed to factor out the code for merging live intervals and
remove copy instructions.  This code updates a bunch of dataflow information
so it's important that other register coalescers can use it.

During the course of this work, I noticed something odd.  In the current
coalescer, we have this sequence:


00298   if (JoinIntervals(DstInt, SrcInt)) {
[...]
00322   } else {
[...]
00332   }

Ok, at this point intervals were joined and in the process, DstInt and SrcInt
might have been swapped by LiveInterval::join.

00334   bool Swapped = repSrcReg == DstInt.reg;
00335   if (Swapped)
00336     std::swap(repSrcReg, repDstReg);
00337   assert(MRegisterInfo::isVirtualRegister(repSrcReg) &&
00338          "LiveInterval::join didn't work right!");

Ok, this code says that if the intervals were swapped, swap the register 
numbers we previously extracted from the live intervals before joining.
This makes things consistent so that repSrcReg is the register corresponding
to the new SrcInt and ditto with repDstReg.

[...]
00369   // If the intervals were swapped by Join, swap them back so that the 
register
00370   // mapping (in the r2i map) is correct.
00371   if (Swapped) SrcInt.swap(DstInt);

Whoops!  At this point repSrcReg is not consistent with SrcInt and the
same goes for repDstReg!

00372   li_->removeInterval(repSrcReg);
00373   r2rMap_[repSrcReg] = repDstReg;

Does this code get us into trouble due to the inconsistency created above?

Is this a bug?  There's a lot of indirection going on here and it's hard to 
keep track of it.

                                                        -Dave