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
On Jul 17, 2007, at 9:28 AM, David Greene wrote:> > [...] > 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.I am not sure. I will poke at it a bit. Thanks. Evan> > -Dave > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On Jul 18, 2007, at 11:19 AM, Evan Cheng wrote:> > On Jul 17, 2007, at 9:28 AM, David Greene wrote: >> >> [...] >> 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. > > I am not sure. I will poke at it a bit. Thanks.It's not a bug. In most cases the coalescer merges the live interval of the RHS of the copy to LHS. If not, they are swapped. At this point repSrcReg is indeed the register that represent the register that's being merged. This code is really hard to follow, I know. <sigh> Evan> > Evan > >> >> -Dave >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev