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 > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
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>
Chris Lattner
2006-Dec-22 23:06 UTC
[LLVMdev] Possible bug in the linear scan register allocator
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... -Chris> --- 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-Chris -- http://nondot.org/sabre/ http://llvm.org/