Roman Levenstein
2006-Dec-21 21:15 UTC
[LLVMdev] Possible bug in the linear scan register allocator
Hi, I was working on extending soft-float support for handling expansion of i64 and f64 into i16, i.e. on supporting the expansion of long values of illegal types into more then two parts. For that I modified SelectionDAGLowering::getValue() and several other functions. This seems to work now on my test-cases, but while testing it I ran into a different problem. I have the impression that I found a bug in the linear-scan register allocator (local and simple allocators work just fine on the same code). The problem is that linear scan loops for ever under certain conditions. May be I overlook something in my target specific code, but I think that it is wrong in any case if a register allocator loops for ever. I attach a part of the log file produced with "llc -debug" where you can see reg.alloc related bits. Register naming convention is: rbN - for 8bit registers rwN - for 16bit registers rxN - for 32bit registers I also attach the C source file and the LLVM assembler file for your convenience. My personal understanding of what is going on is that it is due to the incorrect joining of live intervals. If I disable intervals joining by using --join-liveintervals=false, everything works fine. According to the log file, what happens during joining is the following: 1) some of the fixed registers intervals are merged with some virtual registers intervals 2) later there is a need to spill one of the allocated registers, but since all joined intervals are FIXED intervals now due to (1), they cannot be spilled. Therefore, the register allocator loops for ever. I would be grateful, if someone would confirm that this is a bug. And of course, it would be very nice if one of the RegAlloc Gurus could fix it ;) -Roman --- Evan Cheng <evan.cheng at apple.com> wrote:> > On Dec 20, 2006, at 2:06 PM, Roman Levenstein wrote: > > >> > >> This will probably require a slightly more extensive patch to > >> legalizer. The current mechanism assumes either 1->1 or 1->2 > >> expansion. > > > > Exactly. This is what I meant with "more chellenging";) It is > assumed > > at several places that 1->1 or 2->2 expanstions are taking place. A > > generic case is not handled yet. > > > >> It also assumes the result of expansion are of legal > >> types. > > > > Yes. And this is also a reason why it is not too obvious how to > handle > > f32->f64 promotion and later f64->i64 expansion on targets that > > support > > only f64 soft-floats. > > > > Chris Lattner wrote: > >> That would be recursively expanded to i64, then to 2x i32 if > needed. > > > > I tried to set getTypeToTransformTo(f32) to return f64, even when > f64 > > is illegal type. But this recursive expansion does not take place > with > > the current legalizer implementation. Currently, it is assumed that > > > the > > result of getTypeToTransformTo() is a legal type. For example, > > CreateRegForValue tries to create a register of such a promoted > type > > and fails in the above mentioned case. > > All of the issues can be solved by adding the logic to recursively > expand operands. They shouldn't be too complicated. > > > > > > > Evan wrote: > >> That means, you will have to either 1) modify ExpandOp() to > >> handle cases which need to be recursively expanded or 2) modify it > to > > > >> return a vector of SDOperand's. Solution one is what I would > pursue. > > > > Agreed. I also feel that some sort of recursive expansion is > required. > > > > I also have a feeling that getTypeToTransformTo(MVT::ValueType) > should > > probably also recurse until it finds a type T where > > getTypeToTransformTo(T) = T, i.e. it finds a legal type. This would > > almost solve the issue with f32->f64 promotion where both FP types > are > > illegal. The only concern here is that in this case > > getTypeToTransformTo(MVT::f32) would return MVT::i64 and therefore > the > > information about the fact that it should first be promoted to f64 > is > > lost. The problem is that getTypeToTransformTo() is used for two > > "different" goals: to tell which type to use for register mapping > and > > to tell which type to use for promotions/expansions for the sake of > > "type system correctness". May be it would even make sense to have > two > > different mappings because of this? One mapping will be used for > > allocation of virtual registers and the like and would always > return a > > legal type and the other will be used just as getTypeToTransformTo > > () in > > LegalizeOp(), ExpandOp() and PromoteOp() and can return also > illegal > > types? > > No need to change getTypeToTransformTo(). There is a > getTypeToExpandTo > () that is expand the type recursively until it find a legal type. > > > > >> It's not done simply because there isn't a need for it right now. > :-) > > > > Since I have this need, I'll try to find a solution for this issue > and > > to provide a patch. > > Great! There are a few spots where ExpandOp() are called recursively. > > It would be nice to remove those and use the general expansion > facility instead. > > Evan > > > > > -Roman > >__________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com -------------- next part -------------- An embedded and charset-unspecified text was scrubbed... Name: RegAlloc.txt URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20061221/286571b5/attachment.txt> -------------- next part -------------- A non-text attachment was scrubbed... Name: RegAllocTest.c Type: text/x-csrc Size: 121 bytes Desc: 3887521155-RegAllocTest.c URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20061221/286571b5/attachment.c> -------------- next part -------------- A non-text attachment was scrubbed... Name: RegAllocTest.ll Type: text/x-csrc Size: 1181 bytes Desc: 4270130418-RegAllocTest.ll URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20061221/286571b5/attachment-0001.c>
Roman Levenstein
2006-Dec-23 04:07 UTC
[LLVMdev] Possible bug in the linear scan register allocator
--- Chris Lattner <sabre at nondot.org> wrote:> On Thu, 21 Dec 2006, Roman Levenstein wrote: > > following: > > 1) some of the fixed registers intervals are merged with some > virtual > > registers intervals > > 2) later there is a need to spill one of the allocated registers, > but > > since all joined intervals are FIXED intervals now due to (1), they > > cannot be spilled. Therefore, the register allocator loops for > ever. > > > > I would be grateful, if someone would confirm that this is a bug. > And > > of course, it would be very nice if one of the RegAlloc Gurus could > fix > > it ;) > > This is likely a bug, probably PR711. > > Unfortunately, this isn't super easy to fix, I don't have plans to do > so in the near future...OK. I looked at the PR711 at http://llvm.org/bugs/show_bug.cgi?id=711 Indeed, it sounds as the same bug. Two questions: 1) At least, it would be better if LLVM would crash on an assertion instead of running for ever in such situations. I think this can be easily detected, since this is a case where nothing could be spilled. 2) You write in PR711:>This is due to the coallescer coallescing virtregs with both EAX and >EDX, which makes them unavailable to satisfy spills, causing the RA to >run out of registers. We want to coallesce physregs when possible, >but we cannot pin them in the spiller: >we have to be able to >uncoallesce them.First of all, I totally agree with "we have to be able to uncoallesce them". Linear Scan already does a backtracking in some situations. I'm wondering, if it is very difficult to implement the logic, where when it detects that it runs for ever (i.e. nothing can be spilled for some reason) it basically backtracks completely, does coallescing again but ignoring some selected virtual/physical registers (or any attempts to coalesce with physregs) and tries to allocate the whole function again? Alternatively, may be it would be possible to rerun the linear-scan pass without interval joining on a given function? This will probably produce a worse code, but it is better then crashing or looping for ever.> this isn't super easy to fixOK. Do you see any further problems that I have not mentioned above? Can you elaborate a bit? -Roman __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com