Lang Hames
2012-Nov-13 07:20 UTC
[LLVMdev] problem trying to write an LLVM register-allocation pass
Hi Susan, The problem is that the allocator is re-using the 'preg', which is calculated for an operand that may have a subreg index, for loads and stores to a stack-slot. The stack slot always has the same width as vreg (which is the right behavior), but for operands with subreg indexes, 'preg''s class will be different from 'vreg', in which case you get the mismatched loads/stores you were seeing. I've attached an updated copy of Gcra.cpp that doesn't exhibit this bug. In the new version the loads and stores always reference 'preg', which is always a physical register of the same class as 'vreg'. The update adds a new variable, preg_op, to hold the subregister of preg that will be used for the operand currently being rewritten, and preg_op will be set to a subreg of preg where appropriate. - Lang. On Sun, Nov 11, 2012 at 10:30 AM, Susan Horwitz <horwitz at cs.wisc.edu> wrote:> Sorry about that. I created the assembly file and attached it (as > math.txt). > > Susan > > On 11/11/2012 12:41 AM, Lang Hames wrote: > > Hi Susan, > > It looks like the bitcode you have attached is corrupted. You should > make sure to attach it as a binary file. Alternatively you can attach the > LLVM assembly as text. You can generate an assembly file from bitcode with: > > llvm-dis -o <asm file> <bitcode> > > Regards, > Lang. > > > On Fri, Nov 9, 2012 at 11:15 AM, Susan Horwitz <horwitz at cs.wisc.edu>wrote: > >> Thanks Lang, we are making progress! I no longer get the failed >> assertion, but the code I'm using for vregs that don't get allocated a >> preg, and thus need to be spilled and re-loaded is causing assembler errors. >> >> I suspect the problem is my code for allocating space in the stack, but I >> don't know how to fix it. >> >> I've attached a new version of the simple register-allocation code, a >> test program that causes the bad assembler to be produced, and the bc >> file. (I had to name everything with a .txt extension to copy the files to >> my laptop.) >> >> As always, thank you for your help! >> >> Susan >> >> >> On 11/7/2012 7:31 PM, Lang Hames wrote: >> >> Hi Susan, >> >> In x86-64 the REX prefix must be used to access an extended register >> (r8-r15 and their aliases), but cannot be used when accessing the high byte >> of the ABCD regs (AH, BH, CH, DH). In your test case you have hardcoded >> %vreg1 to R8B, and %vreg15 to AH, and the test case contains a copy between >> these registers. The copy simultaneously must have a REX prefix, and cannot >> have a REX prefix, hence the assertion. >> >> The problem is that not all registers in a class are allocable for all >> vregs. As you can see from the above constraint, which pregs are valid >> varies dynamically depending on the context that the register is used. The >> trick is to query the "allocation order" for a class (and as an added >> headache filter out any reserved registers). I've attached a test-case >> where I do this somewhat manually. In short: >> >> int regClass = MRI->getRegClass(vreg)->getID(); >> const TargetRegisterClass *trc = TRI->getRegClass(regClass); >> ArrayRef<uint16_t> rawOrder = trc->getRawAllocationOrder(Fn); >> ArrayRef<uint16_t>::iterator rItr = rawOrder.begin(); >> while (reservedRegs.test(*rItr)) >> ++rItr; >> preg = *rItr; >> >> Alternatively, you could use the AllocationOrder class >> (lib/CodeGen/AllocationOrder.h). This has the benefit of considering >> register hints for improved coalescing too. It does, however, require you >> to use VirtRegMap. >> >> Hope this helps! >> >> Cheers, >> Lang. >> >> >> >> On Wed, Nov 7, 2012 at 2:56 PM, Lang Hames <lhames at gmail.com> wrote: >> >>> Hi Susan, >>> >>> Sorry for the delayed response. Thanks for the test cases - I'm >>> looking in to this now. >>> >>> - Lang. >>> >>> >>> On Mon, Nov 5, 2012 at 2:58 PM, Susan Horwitz <horwitz at cs.wisc.edu>wrote: >>> >>>> Hi Lang, >>>> >>>> I looked more into one of the problems I'm now having, and I've >>>> attached 3 files: >>>> >>>> Gcra.cpp is like your version except that for two specific vregs it >>>> uses hard-coded pregs instead of the first in the corresponding class. >>>> >>>> bug1.c is an input that causes the failed assertion for me. If I use >>>> the non-debug version of LLVM-3.1 I instead get assembler errors like this: >>>> Error: can't encode register '%ah' in an instruction requiring >>>> REX prefix. >>>> >>>> bug1.bc is my bitcode version of bug1.c. >>>> >>>> The problematic vregs are both in register class 0. One is replaced >>>> with preg 1 and the other with preg 74. Those are both in register class >>>> 0, and are not aliased. Any idea why using those pregs causes trouble? >>>> >>>> Thanks! >>>> >>>> Susan >>>> >>>> >>>> On 11/04/2012 06:19 PM, Lang Hames wrote: >>>> >>>>> Hi Susan, >>>>> >>>>> With your bitcode file I am now able to reproduce the issue you're >>>>> seeing. It looks like this is a problem with the naive rewriting from >>>>> virtregs to physregs. It appears that the subreg field of physreg >>>>> operands is ignored post-register allocation. In your testcase >>>>> %vreg11:sub32 is being rewritten to RBX:sub32, but the :sub32 part is >>>>> being quietly dropped when the assembly is written out. If this is >>>>> expected behaviour, and is still happening in the development branch, >>>>> then I'll add some sort of verification to catch it. >>>>> >>>>> The VirtRegMap::rewrite() method sidesteps this issue by rewriting >>>>> physreg operands to remove the subreg field. The code for this is in >>>>> VirtRegMap.cpp, around line 165. In short: >>>>> >>>>> PhysReg = MO.getReg(); >>>>> if (MO.getSubReg() != 0) { >>>>> PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg()); >>>>> MO.setSubReg(0); >>>>> } >>>>> MO.setReg(PhysReg); >>>>> >>>>> Adding this code to Gcra fixes the assembly issue for me. I've attached >>>>> my updated copy. Hope this helps. >>>>> >>>>> Cheers, >>>>> Lang. >>>>> >>>>> >>>>> On Sun, Nov 4, 2012 at 2:08 PM, Susan Horwitz <horwitz at cs.wisc.edu >>>>> <mailto:horwitz at cs.wisc.edu>> wrote: >>>>> >>>>> My tst.bc is attached. I had to use ssh to copy it from my office >>>>> machine to my home laptop. In case that corrupts it, I also put a >>>>> copy here: >>>>> http://pages.cs.wisc.edu/~horwitz/LANG/tst.bc >>>>> >>>>> I created the file like this: >>>>> >>>>> clang -emit-llvm -O0 -c tst.c -o tst.bc >>>>> opt -mem2reg tst.bc > tst.mem2reg >>>>> mv tst.mem2reg tst.bc >>>>> >>>>> >>>>> Susan >>>>> >>>>> >>>>> On 11/4/2012 3:27 PM, Lang Hames wrote: >>>>> >>>>>> Hi Susan, >>>>>> >>>>>> I tested the version of Gcra.cpp that I sent you on x86-64 systems >>>>>> running MacOS 10.8 and Ubuntu 12.04 (Linux 3.2.0). >>>>>> >>>>>> Could you send me the bitcode file you're compiling? Different >>>>>> bitcodes (due to different clang versions or applied >>>>>> optimizations) could account for the different results we're >>>>>> seeing. For reference I've attached the *.ll file that I have >>>>>> tested with, which was compiled from your tst.c file with: >>>>>> >>>>>> clang -O0 -emit-llvm -S -o tst.ll tst.c >>>>>> >>>>>> My clang version was built from a recent checkout from subversion. >>>>>> >>>>>> It's unlikely that there is any fundamental problem with the >>>>>> register allocation APIs or the code generator that would prevent >>>>>> you from building a working allocator. The APIs certainly could >>>>>> have changed in a way that would break existing allocators though. >>>>>> >>>>>> - Lang. >>>>>> >>>>>> >>>>>> On Sat, Nov 3, 2012 at 4:34 PM, Susan Horwitz < >>>>>> horwitz at cs.wisc.edu >>>>>> <mailto:horwitz at cs.wisc.edu>> wrote: >>>>>> >>>>>> Lang - >>>>>> >>>>>> Your version does NOT work for me (i.e., I still get an error >>>>>> from the assembler when I run your code on my tst.c) unless I >>>>>> force compilation and assembly for a 32-bit X86 machine: >>>>>> >>>>>> llc -march=x86 -regalloc=gc tst.bc >>>>>> gcc -m32 tst.s >>>>>> >>>>>> My machine is a 64-bit machine. Maybe you are working with a >>>>>> different architecture and that's why it worked for you? >>>>>> >>>>>> I would be happy if the above worked in general, but when I >>>>>> try other C code (with my "real" register allocator, not the >>>>>> naive one I sent you) I get assembly that includes >>>>>> >>>>>> %r8d >>>>>> >>>>>> which seems to be invalid for a 32-bit machine. Sigh. It >>>>>> looks to me like there's a problem with the LLVM-3.1 API for >>>>>> register allocation and/or the code-generation phase. What do >>>>>> you think? >>>>>> >>>>>> Susan >>>>>> >>>>>> >>>>>> On 11/1/2012 5:28 PM, Lang Hames wrote: >>>>>> >>>>>>> Hi Susan, >>>>>>> >>>>>>> Without debugging symbols I can't make much out of that stack >>>>>>> trace I'm afraid. >>>>>>> >>>>>>> I've attached my modified version of Gcra.cpp. I built llvm >>>>>>> 3.1 by dropping this file into lib/CodeGen, and adding >>>>>>> references to createGcra to include/lib/CodeGen/Passes.h and >>>>>>> include/lib/CodeGen/LinkAllCodeGenComponents.h. (If you >>>>>>> search for createRegAllocPBQP you'll see where to add the >>>>>>> declarations). >>>>>>> >>>>>>> With that setup, running your allocator on the tst.c file you >>>>>>> attached previously yielded a sane assembly file. >>>>>>> >>>>>>> Cheers, >>>>>>> Lang. >>>>>>> >>>>>>> On Thu, Nov 1, 2012 at 3:13 PM, Susan Horwitz >>>>>>> <horwitz at cs.wisc.edu <mailto:horwitz at cs.wisc.edu>> wrote: >>>>>>> >>>>>>> I still get a coredump: >>>>>>> >>>>>>> 0 libLLVM-3.1.so <http://libLLVM-3.1.so> >>>>>>> 0x00007f0158a4e67f >>>>>>> 1 libLLVM-3.1.so <http://libLLVM-3.1.so> >>>>>>> 0x00007f0158a500ca >>>>>>> 2 libpthread.so.0 0x0000003a86c0f500 >>>>>>> >>>>>>> 3 libLLVM-3.1.so <http://libLLVM-3.1.so> >>>>>>> 0x00007f01583c346c >>>>>>> 4 libLLVM-3.1.so <http://libLLVM-3.1.so> >>>>>>> 0x00007f0158546349 >>>>>>> llvm::FPPassManager::runOnFunction(llvm::Function&) + 521 >>>>>>> 5 libLLVM-3.1.so <http://libLLVM-3.1.so> >>>>>>> >>>>>>> 0x00007f01585463e3 >>>>>>> llvm::FPPassManager::runOnModule(llvm::Module&) + 51 >>>>>>> 6 libLLVM-3.1.so <http://libLLVM-3.1.so> >>>>>>> >>>>>>> 0x00007f0158545fae >>>>>>> llvm::MPPassManager::runOnModule(llvm::Module&) + 462 >>>>>>> 7 libLLVM-3.1.so <http://libLLVM-3.1.so> >>>>>>> >>>>>>> 0x00007f01585460bd >>>>>>> llvm::PassManagerImpl::run(llvm::Module&) + 125 >>>>>>> 8 llc 0x000000000040b012 main + 5218 >>>>>>> 9 libc.so.6 0x0000003a8601ecdd __libc_start_main >>>>>>> + 253 >>>>>>> 10 llc 0x0000000000407d79 >>>>>>> Stack dump: >>>>>>> 0. Program arguments: llc -load Debug/lib/P4.so >>>>>>> -regalloc=gc tst.bc >>>>>>> 1. Running pass 'Function Pass Manager' on module >>>>>>> 'tst.bc'. >>>>>>> 2. Running pass 'Machine Loop Invariant Code Motion' >>>>>>> on function '@main' >>>>>>> make: *** [tst.reg] Segmentation fault (core dumped) >>>>>>> >>>>>>> >>>>>>> >>>>>>> On 11/01/2012 04:59 PM, Lang Hames wrote: >>>>>>> >>>>>>> Hi Susan, >>>>>>> >>>>>>> Sorry - I had missed that you're using llvm-3.1, >>>>>>> rather than the >>>>>>> development branch. We encourage people to live on >>>>>>> top-of-tree - it's >>>>>>> well tested, easier for active developers to offer >>>>>>> help with, and >>>>>>> keeping up with incremental changes is often easier >>>>>>> than porting between >>>>>>> stable versions. >>>>>>> >>>>>>> It also sounds like you were building a Release >>>>>>> version of LLVM. That >>>>>>> will not have any asserts enabled (though it will >>>>>>> have some other >>>>>>> diagnostics). You will probably want to work with a >>>>>>> Debug+Asserts >>>>>>> version (<src>/configure --disable-optimized >>>>>>> --enable-assertions) while >>>>>>> you're developing your allocator and watch for any >>>>>>> asserts that trigger. >>>>>>> >>>>>>> In your case the Assertion that is triggering in PEI >>>>>>> indicates that the >>>>>>> MachineRegisterInfo object still contained some >>>>>>> virtregs post >>>>>>> register-allocation. You need to call >>>>>>> MRI->clearVirtRegs() at the end of >>>>>>> your allocator. >>>>>>> >>>>>>> Hope this helps! >>>>>>> >>>>>>> Cheers, >>>>>>> Lang. >>>>>>> >>>>>>> On Thu, Nov 1, 2012 at 2:41 PM, Susan Horwitz >>>>>>> <horwitz at cs.wisc.edu <mailto:horwitz at cs.wisc.edu> >>>>>>> <mailto:horwitz at cs.wisc.edu >>>>>>> <mailto:horwitz at cs.wisc.edu>>> wrote: >>>>>>> >>>>>>> Hi again Lang, >>>>>>> >>>>>>> I decided to try the approach you proposed to see >>>>>>> whether it makes >>>>>>> the assembly-code problem go away. Again, I >>>>>>> tried a very simple >>>>>>> register allocator (attached) that just calls >>>>>>> vrm.assignVirt2Phys >>>>>>> for every vreg in each function, mapping the vreg >>>>>>> to the first preg >>>>>>> in the register class. I tried two versions: one >>>>>>> maps *every* vreg, >>>>>>> and the other only maps those for which >>>>>>> MRI->reg_empty(vreg) returns >>>>>>> false. In both cases I get a core dump somewhere >>>>>>> after my >>>>>>> reg-allocation pass has run (when I use the >>>>>>> "tst.c" file that I sent >>>>>>> last time as input). >>>>>>> >>>>>>> Note also that there is no VirtRegMap.h in the >>>>>>> "include" directory >>>>>>> of my installed llvm-3.1. I had to copy that >>>>>>> file from the source >>>>>>> directory. That seems suspicious. >>>>>>> >>>>>>> Any thoughts? >>>>>>> >>>>>>> Thanks! >>>>>>> >>>>>>> Susan >>>>>>> >>>>>>> >>>>>>> On 10/31/2012 07:51 PM, Lang Hames wrote: >>>>>>> >>>>>>> Hi Susan, >>>>>>> >>>>>>> I'm having trouble reproducing that error on >>>>>>> my end, but I think the >>>>>>> problem is probably that you're not using the >>>>>>> VirtRegRewriter >>>>>>> infrastructure. What your allocator needs to >>>>>>> do is populate the >>>>>>> virtual >>>>>>> register mapping (VirtRegMap pass) with your >>>>>>> allocation, rather than >>>>>>> rewriting the registers directly through >>>>>>> MachineRegisterInfo. >>>>>>> >>>>>>> Have your allocator require and preserve the >>>>>>> VirtRegMap pass, >>>>>>> then in >>>>>>> your runOnMachineFunction pass grab a >>>>>>> reference to the pass with: >>>>>>> >>>>>>> VirtRegMap &vrm = getAnalysis<VirtRegMap>(); >>>>>>> >>>>>>> You can then describe your register >>>>>>> allocations with: >>>>>>> >>>>>>> vrm.assignVirt2Phys(<virtreg>, <physreg>) >>>>>>> >>>>>>> The VirtRegRewriter pass (in VirtRegMap.cpp) >>>>>>> will run after your >>>>>>> allocator and apply the mapping that you >>>>>>> described in the >>>>>>> VirtRegMap. >>>>>>> >>>>>>> I hope this helps. Let me know if it doesn't >>>>>>> fix your issue. >>>>>>> >>>>>>> Cheers, >>>>>>> Lang. >>>>>>> >>>>>>> On Wed, Oct 31, 2012 at 3:54 PM, Susan >>>>>>> Horwitz >>>>>>> <horwitz at cs.wisc.edu <mailto:horwitz at cs.wisc.edu> >>>>>>> <mailto:horwitz at cs.wisc.edu <mailto: >>>>>>> horwitz at cs.wisc.edu>> >>>>>>> <mailto:horwitz at cs.wisc.edu >>>>>>> <mailto:horwitz at cs.wisc.edu> >>>>>>> <mailto:horwitz at cs.wisc.edu >>>>>>> <mailto:horwitz at cs.wisc.edu>>>> wrote: >>>>>>> >>>>>>> Thanks Lang! >>>>>>> >>>>>>> Here's another question: I'm trying to >>>>>>> process this input: >>>>>>> >>>>>>> int main() { >>>>>>> return 0; >>>>>>> } >>>>>>> >>>>>>> but I'm getting an error >>>>>>> Assertion `!Fn.getRegInfo(). >>>>>>> getNumVirtRegs() && >>>>>>> "Regalloc must >>>>>>> >>>>>>> assign all vregs"' failed. >>>>>>> >>>>>>> At the start of runOnMachineFunction I >>>>>>> call Fn.getRegInfo(). >>>>>>> getNumVirtRegs(); >>>>>>> and find that there is 1 virtual >>>>>>> register. However, >>>>>>> MRI->reg_empty(vreg) >>>>>>> tells me that it is not used or defined. >>>>>>> So my >>>>>>> register-allocation >>>>>>> code never sees it, and thus can't >>>>>>> allocate a preg for it. >>>>>>> I tried >>>>>>> using MRI->replaceRegWith(vreg, preg); >>>>>>> (where preg is available to vreg's >>>>>>> register class) but that >>>>>>> didn't >>>>>>> work. When I look, the number of vregs >>>>>>> in the function is >>>>>>> still 1. >>>>>>> >>>>>>> Can you help with this? >>>>>>> >>>>>>> Thanks again! >>>>>>> >>>>>>> Susan >>>>>>> >>>>>>> >>>>>>> On 10/31/2012 04:55 PM, Lang Hames >>>>>>> wrote: >>>>>>> >>>>>>> Hi Susan, >>>>>>> >>>>>>> The meaning of "addRequired(X)" is >>>>>>> that your pass needs >>>>>>> X to be >>>>>>> run, and >>>>>>> for X to be preserved by all passes >>>>>>> that run after X >>>>>>> and before your >>>>>>> pass. The PHIElemination and >>>>>>> TwoAddressInstruction >>>>>>> passes do not >>>>>>> preserve each other, hence there's >>>>>>> no way for the pass >>>>>>> manager to >>>>>>> schedule them for you if you >>>>>>> addRequire(...) them. >>>>>>> >>>>>>> The trick is that CodeGen will >>>>>>> schedule both of these >>>>>>> passes to >>>>>>> be run >>>>>>> before _any_ register allocation >>>>>>> pass (see Passes.cpp), >>>>>>> so you >>>>>>> needn't >>>>>>> require them explicitly - you can >>>>>>> just assume they have >>>>>>> been >>>>>>> run. If you >>>>>>> just remove those lines from your >>>>>>> getAnalysisUsage >>>>>>> method your pass >>>>>>> should now run as you expect. >>>>>>> >>>>>>> Cheers, >>>>>>> Lang. >>>>>>> >>>>>>> On Wed, Oct 31, 2012 at 1:46 PM, >>>>>>> Susan Horwitz >>>>>>> <horwitz at cs.wisc.edu <mailto:horwitz at cs.wisc.edu> >>>>>>> <mailto:horwitz at cs.wisc.edu <mailto: >>>>>>> horwitz at cs.wisc.edu>> >>>>>>> <mailto:horwitz at cs.wisc.edu >>>>>>> <mailto:horwitz at cs.wisc.edu> >>>>>>> <mailto:horwitz at cs.wisc.edu >>>>>>> <mailto:horwitz at cs.wisc.edu>>> >>>>>>> <mailto:horwitz at cs.wisc.edu >>>>>>> <mailto:horwitz at cs.wisc.edu> >>>>>>> <mailto:horwitz at cs.wisc.edu <mailto: >>>>>>> horwitz at cs.wisc.edu>> >>>>>>> <mailto:horwitz at cs.wisc.edu >>>>>>> <mailto:horwitz at cs.wisc.edu> >>>>>>> <mailto:horwitz at cs.wisc.edu >>>>>>> <mailto:horwitz at cs.wisc.edu>>>>> wrote: >>>>>>> >>>>>>> I'm trying to write a >>>>>>> MachineFunctionPass to do >>>>>>> register >>>>>>> allocation. >>>>>>> I have code that worked with >>>>>>> an old version of >>>>>>> LLVM. It >>>>>>> does not >>>>>>> work with llvm-3.1. (or various >>>>>>> other versions >>>>>>> that I've >>>>>>> tried). >>>>>>> >>>>>>> The first problem is that >>>>>>> including this line: >>>>>>> >>>>>>> AU.addRequiredID(__ >>>>>>> TwoAddressInstructionPassID); >>>>>>> >>>>>>> >>>>>>> in method getAnalysisUsage >>>>>>> causes a runtime error: >>>>>>> >>>>>>> Unable to schedule 'Eliminate >>>>>>> PHI nodes for register >>>>>>> allocation' >>>>>>> required by 'Unnamed pass: >>>>>>> implement >>>>>>> Pass::getPassName()' >>>>>>> Unable to schedule pass >>>>>>> UNREACHABLE executed at ... >>>>>>> >>>>>>> I'm invoking the pass like this >>>>>>> (given input file >>>>>>> foo.c): >>>>>>> >>>>>>> clang -emit-llvm -O0 -c foo.c >>>>>>> -o foo.bc >>>>>>> opt -mem2reg foo.bc > foo.ssa >>>>>>> mv foo.ssa foo.bc >>>>>>> llc -load Debug/lib/P4.so >>>>>>> -regalloc=gc foo.bc >>>>>>> >>>>>>> >>>>>>> I've attached my entire file >>>>>>> (it's very short). >>>>>>> Any help >>>>>>> would be >>>>>>> much appreciated! >>>>>>> >>>>>>> Susan Horwitz >>>>>>> >>>>>>> ______________________________ >>>>>>> _________________ >>>>>>> LLVM Developers mailing list >>>>>>> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu> >>>>>>> <mailto:LLVMdev at cs.uiuc.edu <mailto: >>>>>>> LLVMdev at cs.uiuc.edu>> >>>>>>> <mailto:LLVMdev at cs.uiuc.edu >>>>>>> <mailto:LLVMdev at cs.uiuc.edu> >>>>>>> <mailto:LLVMdev at cs.uiuc.edu >>>>>>> <mailto:LLVMdev at cs.uiuc.edu>>> >>>>>>> <mailto:LLVMdev at cs.uiuc.edu >>>>>>> <mailto:LLVMdev at cs.uiuc.edu> >>>>>>> <mailto:LLVMdev at cs.uiuc.edu <mailto: >>>>>>> LLVMdev at cs.uiuc.edu>> >>>>>>> <mailto:LLVMdev at cs.uiuc.edu >>>>>>> <mailto:LLVMdev at cs.uiuc.edu> >>>>>>> <mailto:LLVMdev at cs.uiuc.edu >>>>>>> <mailto:LLVMdev at cs.uiuc.edu>>>> >>>>>>> >>>>>>> http://llvm.cs.uiuc.edu >>>>>>> http://lists.cs.uiuc.edu/ mailman/listinfo/llvmdev >>>>>>> <http://lists.cs.uiuc.edu/__mailman/listinfo/llvmdev >>>>>>> <http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>> >>>>>> >>>>> >>>>> >>>> >>> >> >> > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121112/297909d0/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: Gcra.cpp Type: text/x-c++src Size: 8207 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121112/297909d0/attachment.cpp>
Susan Horwitz
2012-Nov-13 22:58 UTC
[LLVMdev] problem trying to write an LLVM register-allocation pass
Lang - Your fix does prevent the assembler errors, but it doesn't seem to produce correct assembly. I created a slightly modified version that, for each instruction that includes a vreg, adds a check that the preg selected is not already in that instruction. I've attached that version. I think that this version of Gcra.cpp should produce correct assembler, since it's allocating one stackframe for each vreg and always loading/storing from/to that stackframe. I've attached a simpler version of the test input (now called bug.c) plus the .bc file and the .s file produced by the new code. When I assemble and run I get this output: x: 1001 x: 200 x: 40 x: 8 while the correct output is x: 1001 x: 100 x: 10 Susan On 11/13/2012 01:20 AM, Lang Hames wrote:> Hi Susan, > > The problem is that the allocator is re-using the 'preg', which is > calculated for an operand that may have a subreg index, for loads and > stores to a stack-slot. The stack slot always has the same width as vreg > (which is the right behavior), but for operands with subreg indexes, > 'preg''s class will be different from 'vreg', in which case you get the > mismatched loads/stores you were seeing. > > I've attached an updated copy of Gcra.cpp that doesn't exhibit this bug. > In the new version the loads and stores always reference 'preg', which > is always a physical register of the same class as 'vreg'. The update > adds a new variable, preg_op, to hold the subregister of preg that will > be used for the operand currently being rewritten, and preg_op will be > set to a subreg of preg where appropriate. > > - Lang. > > > On Sun, Nov 11, 2012 at 10:30 AM, Susan Horwitz <horwitz at cs.wisc.edu > <mailto:horwitz at cs.wisc.edu>> wrote: > > Sorry about that. I created the assembly file and attached it (as > math.txt). > > Susan > > On 11/11/2012 12:41 AM, Lang Hames wrote: >> Hi Susan, >> >> It looks like the bitcode you have attached is corrupted. You >> should make sure to attach it as a binary file. Alternatively you >> can attach the LLVM assembly as text. You can generate an assembly >> file from bitcode with: >> >> llvm-dis -o <asm file> <bitcode> >> >> Regards, >> Lang. >> >> >> On Fri, Nov 9, 2012 at 11:15 AM, Susan Horwitz >> <horwitz at cs.wisc.edu <mailto:horwitz at cs.wisc.edu>> wrote: >> >> Thanks Lang, we are making progress! I no longer get the >> failed assertion, but the code I'm using for vregs that don't >> get allocated a preg, and thus need to be spilled and >> re-loaded is causing assembler errors. >> >> I suspect the problem is my code for allocating space in the >> stack, but I don't know how to fix it. >> >> I've attached a new version of the simple register-allocation >> code, a test program that causes the bad assembler to be >> produced, and the bc file. (I had to name everything with a >> .txt extension to copy the files to my laptop.) >> >> As always, thank you for your help! >> >> Susan >> >> >> On 11/7/2012 7:31 PM, Lang Hames wrote: >>> Hi Susan, >>> >>> In x86-64 the REX prefix must be used to access an extended >>> register (r8-r15 and their aliases), but cannot be used when >>> accessing the high byte of the ABCD regs (AH, BH, CH, DH). In >>> your test case you have hardcoded %vreg1 to R8B, and %vreg15 >>> to AH, and the test case contains a copy between these >>> registers. The copy simultaneously must have a REX prefix, >>> and cannot have a REX prefix, hence the assertion. >>> >>> The problem is that not all registers in a class are >>> allocable for all vregs. As you can see from the above >>> constraint, which pregs are valid varies dynamically >>> depending on the context that the register is used. The trick >>> is to query the "allocation order" for a class (and as an >>> added headache filter out any reserved registers). I've >>> attached a test-case where I do this somewhat manually. In short: >>> >>> int regClass = MRI->getRegClass(vreg)->getID(); >>> const TargetRegisterClass *trc = TRI->getRegClass(regClass); >>> ArrayRef<uint16_t> rawOrder = trc->getRawAllocationOrder(Fn); >>> ArrayRef<uint16_t>::iterator rItr = rawOrder.begin(); >>> while (reservedRegs.test(*rItr)) >>> ++rItr; >>> preg = *rItr; >>> >>> Alternatively, you could use the AllocationOrder class >>> (lib/CodeGen/AllocationOrder.h). This has the benefit of >>> considering register hints for improved coalescing too. It >>> does, however, require you to use VirtRegMap. >>> >>> Hope this helps! >>> >>> Cheers, >>> Lang. >>> >>> >>> >>> On Wed, Nov 7, 2012 at 2:56 PM, Lang Hames <lhames at gmail.com >>> <mailto:lhames at gmail.com>> wrote: >>> >>> Hi Susan, >>> >>> Sorry for the delayed response. Thanks for the test cases >>> - I'm looking in to this now. >>> >>> - Lang. >>> >>> >>> On Mon, Nov 5, 2012 at 2:58 PM, Susan Horwitz >>> <horwitz at cs.wisc.edu <mailto:horwitz at cs.wisc.edu>> wrote: >>> >>> Hi Lang, >>> >>> I looked more into one of the problems I'm now >>> having, and I've attached 3 files: >>> >>> Gcra.cpp is like your version except that for two >>> specific vregs it uses hard-coded pregs instead of >>> the first in the corresponding class. >>> >>> bug1.c is an input that causes the failed assertion >>> for me. If I use the non-debug version of LLVM-3.1 I >>> instead get assembler errors like this: >>> Error: can't encode register '%ah' in an >>> instruction requiring REX prefix. >>> >>> bug1.bc is my bitcode version of bug1.c. >>> >>> The problematic vregs are both in register class 0. >>> One is replaced with preg 1 and the other with preg >>> 74. Those are both in register class 0, and are not >>> aliased. Any idea why using those pregs causes trouble? >>> >>> Thanks! >>> >>> Susan >>> >>> >>> On 11/04/2012 06:19 PM, Lang Hames wrote: >>> >>> Hi Susan, >>> >>> With your bitcode file I am now able to reproduce >>> the issue you're >>> seeing. It looks like this is a problem with the >>> naive rewriting from >>> virtregs to physregs. It appears that the subreg >>> field of physreg >>> operands is ignored post-register allocation. In >>> your testcase >>> %vreg11:sub32 is being rewritten to RBX:sub32, >>> but the :sub32 part is >>> being quietly dropped when the assembly is >>> written out. If this is >>> expected behaviour, and is still happening in the >>> development branch, >>> then I'll add some sort of verification to catch it. >>> >>> The VirtRegMap::rewrite() method sidesteps this >>> issue by rewriting >>> physreg operands to remove the subreg field. The >>> code for this is in >>> VirtRegMap.cpp, around line 165. In short: >>> >>> PhysReg = MO.getReg(); >>> if (MO.getSubReg() != 0) { >>> PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg()); >>> MO.setSubReg(0); >>> } >>> MO.setReg(PhysReg); >>> >>> Adding this code to Gcra fixes the assembly issue >>> for me. I've attached >>> my updated copy. Hope this helps. >>> >>> Cheers, >>> Lang. >>> >>> >>> On Sun, Nov 4, 2012 at 2:08 PM, Susan Horwitz >>> <horwitz at cs.wisc.edu <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>>> wrote: >>> >>> My tst.bc is attached. I had to use ssh to >>> copy it from my office >>> machine to my home laptop. In case that >>> corrupts it, I also put a >>> copy here: >>> http://pages.cs.wisc.edu/~horwitz/LANG/tst.bc >>> <http://pages.cs.wisc.edu/%7Ehorwitz/LANG/tst.bc> >>> >>> I created the file like this: >>> >>> clang -emit-llvm -O0 -c tst.c -o tst.bc >>> opt -mem2reg tst.bc > tst.mem2reg >>> mv tst.mem2reg tst.bc >>> >>> >>> Susan >>> >>> >>> On 11/4/2012 3:27 PM, Lang Hames wrote: >>> >>> Hi Susan, >>> >>> I tested the version of Gcra.cpp that I >>> sent you on x86-64 systems >>> running MacOS 10.8 and Ubuntu 12.04 >>> (Linux 3.2.0). >>> >>> Could you send me the bitcode file you're >>> compiling? Different >>> bitcodes (due to different clang versions >>> or applied >>> optimizations) could account for the >>> different results we're >>> seeing. For reference I've attached the >>> *.ll file that I have >>> tested with, which was compiled from your >>> tst.c file with: >>> >>> clang -O0 -emit-llvm -S -o tst.ll tst.c >>> >>> My clang version was built from a recent >>> checkout from subversion. >>> >>> It's unlikely that there is any >>> fundamental problem with the >>> register allocation APIs or the code >>> generator that would prevent >>> you from building a working allocator. >>> The APIs certainly could >>> have changed in a way that would break >>> existing allocators though. >>> >>> - Lang. >>> >>> >>> On Sat, Nov 3, 2012 at 4:34 PM, Susan >>> Horwitz <horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>>> wrote: >>> >>> Lang - >>> >>> Your version does NOT work for me >>> (i.e., I still get an error >>> from the assembler when I run your >>> code on my tst.c) unless I >>> force compilation and assembly for a >>> 32-bit X86 machine: >>> >>> llc -march=x86 -regalloc=gc tst.bc >>> gcc -m32 tst.s >>> >>> My machine is a 64-bit machine. >>> Maybe you are working with a >>> different architecture and that's why >>> it worked for you? >>> >>> I would be happy if the above worked >>> in general, but when I >>> try other C code (with my "real" >>> register allocator, not the >>> naive one I sent you) I get assembly >>> that includes >>> >>> %r8d >>> >>> which seems to be invalid for a >>> 32-bit machine. Sigh. It >>> looks to me like there's a problem >>> with the LLVM-3.1 API for >>> register allocation and/or the >>> code-generation phase. What do >>> you think? >>> >>> Susan >>> >>> >>> On 11/1/2012 5:28 PM, Lang Hames wrote: >>> >>> Hi Susan, >>> >>> Without debugging symbols I can't >>> make much out of that stack >>> trace I'm afraid. >>> >>> I've attached my modified version >>> of Gcra.cpp. I built llvm >>> 3.1 by dropping this file into >>> lib/CodeGen, and adding >>> references to createGcra to >>> include/lib/CodeGen/Passes.h and >>> >>> include/lib/CodeGen/LinkAllCodeGenComponents.h. >>> (If you >>> search for createRegAllocPBQP >>> you'll see where to add the >>> declarations). >>> >>> With that setup, running your >>> allocator on the tst.c file you >>> attached previously yielded a >>> sane assembly file. >>> >>> Cheers, >>> Lang. >>> >>> On Thu, Nov 1, 2012 at 3:13 PM, >>> Susan Horwitz >>> <horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>>> wrote: >>> >>> I still get a coredump: >>> >>> 0 libLLVM-3.1.so >>> <http://libLLVM-3.1.so> >>> <http://libLLVM-3.1.so> 0x00007f0158a4e67f >>> 1 libLLVM-3.1.so >>> <http://libLLVM-3.1.so> >>> <http://libLLVM-3.1.so> 0x00007f0158a500ca >>> 2 libpthread.so.0 >>> 0x0000003a86c0f500 >>> >>> 3 libLLVM-3.1.so >>> <http://libLLVM-3.1.so> >>> <http://libLLVM-3.1.so> 0x00007f01583c346c >>> 4 libLLVM-3.1.so >>> <http://libLLVM-3.1.so> >>> <http://libLLVM-3.1.so> >>> 0x00007f0158546349 >>> >>> llvm::FPPassManager::runOnFunction(llvm::Function&) >>> + 521 >>> 5 libLLVM-3.1.so >>> <http://libLLVM-3.1.so> >>> <http://libLLVM-3.1.so> >>> >>> 0x00007f01585463e3 >>> >>> llvm::FPPassManager::runOnModule(llvm::Module&) >>> + 51 >>> 6 libLLVM-3.1.so >>> <http://libLLVM-3.1.so> >>> <http://libLLVM-3.1.so> >>> >>> 0x00007f0158545fae >>> >>> llvm::MPPassManager::runOnModule(llvm::Module&) >>> + 462 >>> 7 libLLVM-3.1.so >>> <http://libLLVM-3.1.so> >>> <http://libLLVM-3.1.so> >>> >>> 0x00007f01585460bd >>> >>> llvm::PassManagerImpl::run(llvm::Module&) >>> + 125 >>> 8 llc >>> 0x000000000040b012 main + 5218 >>> 9 libc.so.6 >>> 0x0000003a8601ecdd __libc_start_main + 253 >>> 10 llc >>> 0x0000000000407d79 >>> Stack dump: >>> 0. Program arguments: >>> llc -load Debug/lib/P4.so >>> -regalloc=gc tst.bc >>> 1. Running pass >>> 'Function Pass Manager' on module >>> 'tst.bc'. >>> 2. Running pass 'Machine >>> Loop Invariant Code Motion' >>> on function '@main' >>> make: *** [tst.reg] >>> Segmentation fault (core dumped) >>> >>> >>> >>> On 11/01/2012 04:59 PM, Lang >>> Hames wrote: >>> >>> Hi Susan, >>> >>> Sorry - I had missed that >>> you're using llvm-3.1, >>> rather than the >>> development branch. We >>> encourage people to live on >>> top-of-tree - it's >>> well tested, easier for >>> active developers to offer >>> help with, and >>> keeping up with >>> incremental changes is often easier >>> than porting between >>> stable versions. >>> >>> It also sounds like you >>> were building a Release >>> version of LLVM. That >>> will not have any asserts >>> enabled (though it will >>> have some other >>> diagnostics). You will >>> probably want to work with a >>> Debug+Asserts >>> version (<src>/configure >>> --disable-optimized >>> --enable-assertions) while >>> you're developing your >>> allocator and watch for any >>> asserts that trigger. >>> >>> In your case the >>> Assertion that is triggering in PEI >>> indicates that the >>> MachineRegisterInfo >>> object still contained some >>> virtregs post >>> register-allocation. You >>> need to call >>> MRI->clearVirtRegs() at >>> the end of >>> your allocator. >>> >>> Hope this helps! >>> >>> Cheers, >>> Lang. >>> >>> On Thu, Nov 1, 2012 at >>> 2:41 PM, Susan Horwitz >>> <horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>>>> wrote: >>> >>> Hi again Lang, >>> >>> I decided to try the >>> approach you proposed to see >>> whether it makes >>> the assembly-code >>> problem go away. Again, I >>> tried a very simple >>> register allocator >>> (attached) that just calls >>> vrm.assignVirt2Phys >>> for every vreg in >>> each function, mapping the vreg >>> to the first preg >>> in the register >>> class. I tried two versions: one >>> maps *every* vreg, >>> and the other only >>> maps those for which >>> MRI->reg_empty(vreg) returns >>> false. In both cases >>> I get a core dump somewhere >>> after my >>> reg-allocation pass >>> has run (when I use the >>> "tst.c" file that I sent >>> last time as input). >>> >>> Note also that there >>> is no VirtRegMap.h in the >>> "include" directory >>> of my installed >>> llvm-3.1. I had to copy that >>> file from the source >>> directory. That >>> seems suspicious. >>> >>> Any thoughts? >>> >>> Thanks! >>> >>> Susan >>> >>> >>> On 10/31/2012 07:51 >>> PM, Lang Hames wrote: >>> >>> Hi Susan, >>> >>> I'm having >>> trouble reproducing that error on >>> my end, but I think the >>> problem is >>> probably that you're not using the >>> VirtRegRewriter >>> infrastructure. >>> What your allocator needs to >>> do is populate the >>> virtual >>> register mapping >>> (VirtRegMap pass) with your >>> allocation, rather than >>> rewriting the >>> registers directly through >>> MachineRegisterInfo. >>> >>> Have your >>> allocator require and preserve the >>> VirtRegMap pass, >>> then in >>> your >>> runOnMachineFunction pass grab a >>> reference to the pass with: >>> >>> VirtRegMap &vrm >>> getAnalysis<VirtRegMap>(); >>> >>> You can then >>> describe your register >>> allocations with: >>> >>> >>> vrm.assignVirt2Phys(<virtreg>, <physreg>) >>> >>> The >>> VirtRegRewriter pass (in VirtRegMap.cpp) >>> will run after your >>> allocator and >>> apply the mapping that you >>> described in the >>> VirtRegMap. >>> >>> I hope this >>> helps. Let me know if it doesn't >>> fix your issue. >>> >>> Cheers, >>> Lang. >>> >>> On Wed, Oct 31, >>> 2012 at 3:54 PM, Susan Horwitz >>> <horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>>> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>>>>> wrote: >>> >>> Thanks Lang! >>> >>> Here's >>> another question: I'm trying to >>> process this input: >>> >>> int main() { >>> return 0; >>> } >>> >>> but I'm >>> getting an error >>> Assertion >>> `!Fn.getRegInfo(). >>> getNumVirtRegs() && >>> "Regalloc must >>> >>> assign all >>> vregs"' failed. >>> >>> At the start >>> of runOnMachineFunction I >>> call Fn.getRegInfo(). >>> >>> getNumVirtRegs(); >>> and find >>> that there is 1 virtual >>> register. However, >>> >>> MRI->reg_empty(vreg) >>> tells me >>> that it is not used or defined. >>> So my >>> register-allocation >>> code never >>> sees it, and thus can't >>> allocate a preg for it. >>> I tried >>> using >>> MRI->replaceRegWith(vreg, preg); >>> (where preg >>> is available to vreg's >>> register class) but that >>> didn't >>> work. When >>> I look, the number of vregs >>> in the function is >>> still 1. >>> >>> Can you help >>> with this? >>> >>> Thanks again! >>> >>> Susan >>> >>> >>> On >>> 10/31/2012 04:55 PM, Lang Hames wrote: >>> >>> Hi Susan, >>> >>> The >>> meaning of "addRequired(X)" is >>> that your pass needs >>> X to be >>> run, and >>> for X to >>> be preserved by all passes >>> that run after X >>> and before your >>> pass. >>> The PHIElemination and >>> TwoAddressInstruction >>> passes do not >>> preserve >>> each other, hence there's >>> no way for the pass >>> manager to >>> schedule >>> them for you if you >>> addRequire(...) them. >>> >>> The >>> trick is that CodeGen will >>> schedule both of these >>> passes to >>> be run >>> before >>> _any_ register allocation >>> pass (see Passes.cpp), >>> so you >>> needn't >>> require >>> them explicitly - you can >>> just assume they have >>> been >>> run. If you >>> just >>> remove those lines from your >>> getAnalysisUsage >>> method your pass >>> should >>> now run as you expect. >>> >>> Cheers, >>> Lang. >>> >>> On Wed, >>> Oct 31, 2012 at 1:46 PM, >>> Susan Horwitz >>> <horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>>> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>>>> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>>> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu> >>> <mailto:horwitz at cs.wisc.edu >>> <mailto:horwitz at cs.wisc.edu>>>>>> wrote: >>> >>> I'm >>> trying to write a >>> MachineFunctionPass to do >>> register >>> allocation. >>> I >>> have code that worked with >>> an old version of >>> LLVM. It >>> does not >>> >>> work with llvm-3.1. (or various >>> other versions >>> that I've >>> tried). >>> >>> The >>> first problem is that >>> including this line: >>> >>> >>> AU.addRequiredID(__ >>> TwoAddressInstructionPassID); >>> >>> >>> in >>> method getAnalysisUsage >>> causes a runtime error: >>> >>> >>> Unable to schedule 'Eliminate >>> PHI nodes for register >>> allocation' >>> >>> required by 'Unnamed pass: >>> implement >>> Pass::getPassName()' >>> >>> Unable to schedule pass >>> >>> UNREACHABLE executed at ... >>> >>> I'm >>> invoking the pass like this >>> (given input file >>> foo.c): >>> >>> >>> clang -emit-llvm -O0 -c foo.c >>> -o foo.bc >>> opt >>> -mem2reg foo.bc > foo.ssa >>> mv >>> foo.ssa foo.bc >>> llc >>> -load Debug/lib/P4.so >>> -regalloc=gc foo.bc >>> >>> >>> >>> I've attached my entire file >>> (it's very short). >>> Any help >>> would be >>> >>> much appreciated! >>> >>> >>> Susan Horwitz >>> >>> >>> ______________________________ >>> _________________ >>> >>> LLVM Developers mailing list >>> LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu> >>> <mailto:LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu>> >>> <mailto:LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu> >>> <mailto:LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu>>> >>> <mailto:LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu> >>> <mailto:LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu>> >>> <mailto:LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu> >>> <mailto:LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu>>>> >>> <mailto:LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu> >>> <mailto:LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu>> >>> <mailto:LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu> >>> <mailto:LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu>>> >>> <mailto:LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu> >>> <mailto:LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu>> >>> <mailto:LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu> >>> <mailto:LLVMdev at cs.uiuc.edu >>> <mailto:LLVMdev at cs.uiuc.edu>>>>> >>> >>> http://llvm.cs.uiuc.edu >>> http://lists.cs.uiuc.edu/ >>> mailman/listinfo/llvmdev >>> <http://lists.cs.uiuc.edu/__mailman/listinfo/llvmdev >>> <http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >> >> > >-------------- next part -------------- A non-text attachment was scrubbed... Name: Gcra.cpp Type: text/x-c++src Size: 9295 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121113/b904e8c0/attachment.cpp> -------------- next part -------------- A non-text attachment was scrubbed... Name: bug.bc Type: application/octet-stream Size: 760 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121113/b904e8c0/attachment.obj> -------------- next part -------------- A non-text attachment was scrubbed... Name: bug.c Type: text/x-csrc Size: 170 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121113/b904e8c0/attachment.c> -------------- next part -------------- An embedded and charset-unspecified text was scrubbed... Name: bug.s URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121113/b904e8c0/attachment.ksh>
Lang Hames
2012-Nov-14 06:45 UTC
[LLVMdev] problem trying to write an LLVM register-allocation pass
Hi Susan, The problem now is the usedPregSet. Take the instruction: %vreg13:sub_32bit<def> = ADD32rr %vreg13:sub_32bit, %EAX<kill>, %EFLAGS<imp-def,dead> %EAX will be added to usedPregSet when the instruction is encountered, but %vreg13 is a different class (64bit registers), so none of its candidates will conflict. In addition to checking membership of usedPregSet, you need to check all aliases of the elements of usedPregSet. The attached Gcra includes code for this. It also moves the erasure of the subreg index out of the inner loop so that if a vreg appears multiple times in an instruction all subreg indexes will be cleared. - Lang. On Tue, Nov 13, 2012 at 2:58 PM, Susan Horwitz <horwitz at cs.wisc.edu> wrote:> Lang - > > Your fix does prevent the assembler errors, but it doesn't seem to produce > correct assembly. > > I created a slightly modified version that, for each instruction that > includes a vreg, adds a check that the preg selected is not already in that > instruction. I've attached that version. > > I think that this version of Gcra.cpp should produce correct assembler, > since it's allocating one stackframe for each vreg and always > loading/storing from/to that stackframe. > > I've attached a simpler version of the test input (now called bug.c) plus > the .bc file and the .s file produced by the new code. When I assemble and > run I get this output: > > x: 1001 > x: 200 > x: 40 > x: 8 > > while the correct output is > > x: 1001 > x: 100 > x: 10 > > Susan > > > On 11/13/2012 01:20 AM, Lang Hames wrote: > >> Hi Susan, >> >> The problem is that the allocator is re-using the 'preg', which is >> calculated for an operand that may have a subreg index, for loads and >> stores to a stack-slot. The stack slot always has the same width as vreg >> (which is the right behavior), but for operands with subreg indexes, >> 'preg''s class will be different from 'vreg', in which case you get the >> mismatched loads/stores you were seeing. >> >> I've attached an updated copy of Gcra.cpp that doesn't exhibit this bug. >> In the new version the loads and stores always reference 'preg', which >> is always a physical register of the same class as 'vreg'. The update >> adds a new variable, preg_op, to hold the subregister of preg that will >> be used for the operand currently being rewritten, and preg_op will be >> set to a subreg of preg where appropriate. >> >> - Lang. >> >> >> On Sun, Nov 11, 2012 at 10:30 AM, Susan Horwitz <horwitz at cs.wisc.edu >> <mailto:horwitz at cs.wisc.edu>> wrote: >> >> Sorry about that. I created the assembly file and attached it (as >> math.txt). >> >> Susan >> >> On 11/11/2012 12:41 AM, Lang Hames wrote: >> >>> Hi Susan, >>> >>> It looks like the bitcode you have attached is corrupted. You >>> should make sure to attach it as a binary file. Alternatively you >>> can attach the LLVM assembly as text. You can generate an assembly >>> file from bitcode with: >>> >>> llvm-dis -o <asm file> <bitcode> >>> >>> Regards, >>> Lang. >>> >>> >>> On Fri, Nov 9, 2012 at 11:15 AM, Susan Horwitz >>> <horwitz at cs.wisc.edu <mailto:horwitz at cs.wisc.edu>> wrote: >>> >>> Thanks Lang, we are making progress! I no longer get the >>> failed assertion, but the code I'm using for vregs that don't >>> get allocated a preg, and thus need to be spilled and >>> re-loaded is causing assembler errors. >>> >>> I suspect the problem is my code for allocating space in the >>> stack, but I don't know how to fix it. >>> >>> I've attached a new version of the simple register-allocation >>> code, a test program that causes the bad assembler to be >>> produced, and the bc file. (I had to name everything with a >>> .txt extension to copy the files to my laptop.) >>> >>> As always, thank you for your help! >>> >>> Susan >>> >>> >>> On 11/7/2012 7:31 PM, Lang Hames wrote: >>> >>>> Hi Susan, >>>> >>>> In x86-64 the REX prefix must be used to access an extended >>>> register (r8-r15 and their aliases), but cannot be used when >>>> accessing the high byte of the ABCD regs (AH, BH, CH, DH). In >>>> your test case you have hardcoded %vreg1 to R8B, and %vreg15 >>>> to AH, and the test case contains a copy between these >>>> registers. The copy simultaneously must have a REX prefix, >>>> and cannot have a REX prefix, hence the assertion. >>>> >>>> The problem is that not all registers in a class are >>>> allocable for all vregs. As you can see from the above >>>> constraint, which pregs are valid varies dynamically >>>> depending on the context that the register is used. The trick >>>> is to query the "allocation order" for a class (and as an >>>> added headache filter out any reserved registers). I've >>>> attached a test-case where I do this somewhat manually. In >>>> short: >>>> >>>> int regClass = MRI->getRegClass(vreg)->getID(**); >>>> const TargetRegisterClass *trc = TRI->getRegClass(regClass); >>>> ArrayRef<uint16_t> rawOrder = trc->getRawAllocationOrder(Fn)**; >>>> ArrayRef<uint16_t>::iterator rItr = rawOrder.begin(); >>>> while (reservedRegs.test(*rItr)) >>>> ++rItr; >>>> preg = *rItr; >>>> >>>> Alternatively, you could use the AllocationOrder class >>>> (lib/CodeGen/AllocationOrder.**h). This has the benefit of >>>> considering register hints for improved coalescing too. It >>>> does, however, require you to use VirtRegMap. >>>> >>>> Hope this helps! >>>> >>>> Cheers, >>>> Lang. >>>> >>>> >>>> >>>> On Wed, Nov 7, 2012 at 2:56 PM, Lang Hames <lhames at gmail.com >>>> <mailto:lhames at gmail.com>> wrote: >>>> >>>> Hi Susan, >>>> >>>> Sorry for the delayed response. Thanks for the test cases >>>> - I'm looking in to this now. >>>> >>>> - Lang. >>>> >>>> >>>> On Mon, Nov 5, 2012 at 2:58 PM, Susan Horwitz >>>> <horwitz at cs.wisc.edu <mailto:horwitz at cs.wisc.edu>> wrote: >>>> >>>> Hi Lang, >>>> >>>> I looked more into one of the problems I'm now >>>> having, and I've attached 3 files: >>>> >>>> Gcra.cpp is like your version except that for two >>>> specific vregs it uses hard-coded pregs instead of >>>> the first in the corresponding class. >>>> >>>> bug1.c is an input that causes the failed assertion >>>> for me. If I use the non-debug version of LLVM-3.1 I >>>> instead get assembler errors like this: >>>> Error: can't encode register '%ah' in an >>>> instruction requiring REX prefix. >>>> >>>> bug1.bc is my bitcode version of bug1.c. >>>> >>>> The problematic vregs are both in register class 0. >>>> One is replaced with preg 1 and the other with preg >>>> 74. Those are both in register class 0, and are not >>>> aliased. Any idea why using those pregs causes trouble? >>>> >>>> Thanks! >>>> >>>> Susan >>>> >>>> >>>> On 11/04/2012 06:19 PM, Lang Hames wrote: >>>> >>>> Hi Susan, >>>> >>>> With your bitcode file I am now able to reproduce >>>> the issue you're >>>> seeing. It looks like this is a problem with the >>>> naive rewriting from >>>> virtregs to physregs. It appears that the subreg >>>> field of physreg >>>> operands is ignored post-register allocation. In >>>> your testcase >>>> %vreg11:sub32 is being rewritten to RBX:sub32, >>>> but the :sub32 part is >>>> being quietly dropped when the assembly is >>>> written out. If this is >>>> expected behaviour, and is still happening in the >>>> development branch, >>>> then I'll add some sort of verification to catch it. >>>> >>>> The VirtRegMap::rewrite() method sidesteps this >>>> issue by rewriting >>>> physreg operands to remove the subreg field. The >>>> code for this is in >>>> VirtRegMap.cpp, around line 165. In short: >>>> >>>> PhysReg = MO.getReg(); >>>> if (MO.getSubReg() != 0) { >>>> PhysReg = TRI->getSubReg(PhysReg, >>>> MO.getSubReg()); >>>> MO.setSubReg(0); >>>> } >>>> MO.setReg(PhysReg); >>>> >>>> Adding this code to Gcra fixes the assembly issue >>>> for me. I've attached >>>> my updated copy. Hope this helps. >>>> >>>> Cheers, >>>> Lang. >>>> >>>> >>>> On Sun, Nov 4, 2012 at 2:08 PM, Susan Horwitz >>>> <horwitz at cs.wisc.edu <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>>> wrote: >>>> >>>> My tst.bc is attached. I had to use ssh to >>>> copy it from my office >>>> machine to my home laptop. In case that >>>> corrupts it, I also put a >>>> copy here: >>>> http://pages.cs.wisc.edu/~**horwitz/LANG/tst.bc<http://pages.cs.wisc.edu/~horwitz/LANG/tst.bc> >>>> <http://pages.cs.wisc.edu/%**7Ehorwitz/LANG/tst.bc<http://pages.cs.wisc.edu/%7Ehorwitz/LANG/tst.bc> >>>> > >>>> >>>> >>>> I created the file like this: >>>> >>>> clang -emit-llvm -O0 -c tst.c -o tst.bc >>>> opt -mem2reg tst.bc > tst.mem2reg >>>> mv tst.mem2reg tst.bc >>>> >>>> >>>> Susan >>>> >>>> >>>> On 11/4/2012 3:27 PM, Lang Hames wrote: >>>> >>>> Hi Susan, >>>> >>>> I tested the version of Gcra.cpp that I >>>> sent you on x86-64 systems >>>> running MacOS 10.8 and Ubuntu 12.04 >>>> (Linux 3.2.0). >>>> >>>> Could you send me the bitcode file you're >>>> compiling? Different >>>> bitcodes (due to different clang versions >>>> or applied >>>> optimizations) could account for the >>>> different results we're >>>> seeing. For reference I've attached the >>>> *.ll file that I have >>>> tested with, which was compiled from your >>>> tst.c file with: >>>> >>>> clang -O0 -emit-llvm -S -o tst.ll tst.c >>>> >>>> My clang version was built from a recent >>>> checkout from subversion. >>>> >>>> It's unlikely that there is any >>>> fundamental problem with the >>>> register allocation APIs or the code >>>> generator that would prevent >>>> you from building a working allocator. >>>> The APIs certainly could >>>> have changed in a way that would break >>>> existing allocators though. >>>> >>>> - Lang. >>>> >>>> >>>> On Sat, Nov 3, 2012 at 4:34 PM, Susan >>>> Horwitz <horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>>> wrote: >>>> >>>> Lang - >>>> >>>> Your version does NOT work for me >>>> (i.e., I still get an error >>>> from the assembler when I run your >>>> code on my tst.c) unless I >>>> force compilation and assembly for a >>>> 32-bit X86 machine: >>>> >>>> llc -march=x86 -regalloc=gc tst.bc >>>> gcc -m32 tst.s >>>> >>>> My machine is a 64-bit machine. >>>> Maybe you are working with a >>>> different architecture and that's why >>>> it worked for you? >>>> >>>> I would be happy if the above worked >>>> in general, but when I >>>> try other C code (with my "real" >>>> register allocator, not the >>>> naive one I sent you) I get assembly >>>> that includes >>>> >>>> %r8d >>>> >>>> which seems to be invalid for a >>>> 32-bit machine. Sigh. It >>>> looks to me like there's a problem >>>> with the LLVM-3.1 API for >>>> register allocation and/or the >>>> code-generation phase. What do >>>> you think? >>>> >>>> Susan >>>> >>>> >>>> On 11/1/2012 5:28 PM, Lang Hames wrote: >>>> >>>> Hi Susan, >>>> >>>> Without debugging symbols I can't >>>> make much out of that stack >>>> trace I'm afraid. >>>> >>>> I've attached my modified version >>>> of Gcra.cpp. I built llvm >>>> 3.1 by dropping this file into >>>> lib/CodeGen, and adding >>>> references to createGcra to >>>> include/lib/CodeGen/Passes.h and >>>> >>>> include/lib/CodeGen/** >>>> LinkAllCodeGenComponents.h. >>>> (If you >>>> search for createRegAllocPBQP >>>> you'll see where to add the >>>> declarations). >>>> >>>> With that setup, running your >>>> allocator on the tst.c file you >>>> attached previously yielded a >>>> sane assembly file. >>>> >>>> Cheers, >>>> Lang. >>>> >>>> On Thu, Nov 1, 2012 at 3:13 PM, >>>> Susan Horwitz >>>> <horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>>> wrote: >>>> >>>> I still get a coredump: >>>> >>>> 0 libLLVM-3.1.so >>>> <http://libLLVM-3.1.so> >>>> <http://libLLVM-3.1.so> 0x00007f0158a4e67f >>>> 1 libLLVM-3.1.so >>>> <http://libLLVM-3.1.so> >>>> <http://libLLVM-3.1.so> 0x00007f0158a500ca >>>> 2 libpthread.so.0 >>>> 0x0000003a86c0f500 >>>> >>>> 3 libLLVM-3.1.so >>>> <http://libLLVM-3.1.so> >>>> <http://libLLVM-3.1.so> 0x00007f01583c346c >>>> 4 libLLVM-3.1.so >>>> <http://libLLVM-3.1.so> >>>> <http://libLLVM-3.1.so> >>>> 0x00007f0158546349 >>>> >>>> llvm::FPPassManager::** >>>> runOnFunction(llvm::Function&) >>>> + 521 >>>> 5 libLLVM-3.1.so >>>> <http://libLLVM-3.1.so> >>>> <http://libLLVM-3.1.so> >>>> >>>> 0x00007f01585463e3 >>>> >>>> llvm::FPPassManager::** >>>> runOnModule(llvm::Module&) >>>> + 51 >>>> 6 libLLVM-3.1.so >>>> <http://libLLVM-3.1.so> >>>> <http://libLLVM-3.1.so> >>>> >>>> 0x00007f0158545fae >>>> >>>> llvm::MPPassManager::** >>>> runOnModule(llvm::Module&) >>>> + 462 >>>> 7 libLLVM-3.1.so >>>> <http://libLLVM-3.1.so> >>>> <http://libLLVM-3.1.so> >>>> >>>> 0x00007f01585460bd >>>> >>>> llvm::PassManagerImpl::run(**llvm::Module&) >>>> + 125 >>>> 8 llc >>>> 0x000000000040b012 main + 5218 >>>> 9 libc.so.6 >>>> 0x0000003a8601ecdd __libc_start_main + 253 >>>> 10 llc >>>> 0x0000000000407d79 >>>> Stack dump: >>>> 0. Program arguments: >>>> llc -load Debug/lib/P4.so >>>> -regalloc=gc tst.bc >>>> 1. Running pass >>>> 'Function Pass Manager' on module >>>> 'tst.bc'. >>>> 2. Running pass 'Machine >>>> Loop Invariant Code Motion' >>>> on function '@main' >>>> make: *** [tst.reg] >>>> Segmentation fault (core dumped) >>>> >>>> >>>> >>>> On 11/01/2012 04:59 PM, Lang >>>> Hames wrote: >>>> >>>> Hi Susan, >>>> >>>> Sorry - I had missed that >>>> you're using llvm-3.1, >>>> rather than the >>>> development branch. We >>>> encourage people to live on >>>> top-of-tree - it's >>>> well tested, easier for >>>> active developers to offer >>>> help with, and >>>> keeping up with >>>> incremental changes is often easier >>>> than porting between >>>> stable versions. >>>> >>>> It also sounds like you >>>> were building a Release >>>> version of LLVM. That >>>> will not have any asserts >>>> enabled (though it will >>>> have some other >>>> diagnostics). You will >>>> probably want to work with a >>>> Debug+Asserts >>>> version (<src>/configure >>>> --disable-optimized >>>> --enable-assertions) while >>>> you're developing your >>>> allocator and watch for any >>>> asserts that trigger. >>>> >>>> In your case the >>>> Assertion that is triggering in PEI >>>> indicates that the >>>> MachineRegisterInfo >>>> object still contained some >>>> virtregs post >>>> register-allocation. You >>>> need to call >>>> MRI->clearVirtRegs() at >>>> the end of >>>> your allocator. >>>> >>>> Hope this helps! >>>> >>>> Cheers, >>>> Lang. >>>> >>>> On Thu, Nov 1, 2012 at >>>> 2:41 PM, Susan Horwitz >>>> <horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>>>**> wrote: >>>> >>>> Hi again Lang, >>>> >>>> I decided to try the >>>> approach you proposed to see >>>> whether it makes >>>> the assembly-code >>>> problem go away. Again, I >>>> tried a very simple >>>> register allocator >>>> (attached) that just calls >>>> vrm.assignVirt2Phys >>>> for every vreg in >>>> each function, mapping the vreg >>>> to the first preg >>>> in the register >>>> class. I tried two versions: one >>>> maps *every* vreg, >>>> and the other only >>>> maps those for which >>>> MRI->reg_empty(vreg) returns >>>> false. In both cases >>>> I get a core dump somewhere >>>> after my >>>> reg-allocation pass >>>> has run (when I use the >>>> "tst.c" file that I sent >>>> last time as input). >>>> >>>> Note also that there >>>> is no VirtRegMap.h in the >>>> "include" directory >>>> of my installed >>>> llvm-3.1. I had to copy that >>>> file from the source >>>> directory. That >>>> seems suspicious. >>>> >>>> Any thoughts? >>>> >>>> Thanks! >>>> >>>> Susan >>>> >>>> >>>> On 10/31/2012 07:51 >>>> PM, Lang Hames wrote: >>>> >>>> Hi Susan, >>>> >>>> I'm having >>>> trouble reproducing that error on >>>> my end, but I think the >>>> problem is >>>> probably that you're not using the >>>> VirtRegRewriter >>>> infrastructure. >>>> What your allocator needs to >>>> do is populate the >>>> virtual >>>> register mapping >>>> (VirtRegMap pass) with your >>>> allocation, rather than >>>> rewriting the >>>> registers directly through >>>> MachineRegisterInfo. >>>> >>>> Have your >>>> allocator require and preserve the >>>> VirtRegMap pass, >>>> then in >>>> your >>>> runOnMachineFunction pass grab a >>>> reference to the pass with: >>>> >>>> VirtRegMap &vrm >>>> getAnalysis<VirtRegMap>(); >>>> >>>> You can then >>>> describe your register >>>> allocations with: >>>> >>>> >>>> vrm.assignVirt2Phys(<virtreg>, <physreg>) >>>> >>>> The >>>> VirtRegRewriter pass (in VirtRegMap.cpp) >>>> will run after your >>>> allocator and >>>> apply the mapping that you >>>> described in the >>>> VirtRegMap. >>>> >>>> I hope this >>>> helps. Let me know if it doesn't >>>> fix your issue. >>>> >>>> Cheers, >>>> Lang. >>>> >>>> On Wed, Oct 31, >>>> 2012 at 3:54 PM, Susan Horwitz >>>> <horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>>> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>>>**>> wrote: >>>> >>>> Thanks Lang! >>>> >>>> Here's >>>> another question: I'm trying to >>>> process this input: >>>> >>>> int main() { >>>> return 0; >>>> } >>>> >>>> but I'm >>>> getting an error >>>> Assertion >>>> `!Fn.getRegInfo(). >>>> getNumVirtRegs() && >>>> "Regalloc must >>>> >>>> assign all >>>> vregs"' failed. >>>> >>>> At the start >>>> of runOnMachineFunction I >>>> call Fn.getRegInfo(). >>>> >>>> getNumVirtRegs(); >>>> and find >>>> that there is 1 virtual >>>> register. However, >>>> >>>> MRI->reg_empty(vreg) >>>> tells me >>>> that it is not used or defined. >>>> So my >>>> register-allocation >>>> code never >>>> sees it, and thus can't >>>> allocate a preg for it. >>>> I tried >>>> using >>>> MRI->replaceRegWith(vreg, preg); >>>> (where preg >>>> is available to vreg's >>>> register class) but that >>>> didn't >>>> work. When >>>> I look, the number of vregs >>>> in the function is >>>> still 1. >>>> >>>> Can you help >>>> with this? >>>> >>>> Thanks again! >>>> >>>> Susan >>>> >>>> >>>> On >>>> 10/31/2012 04:55 PM, Lang Hames wrote: >>>> >>>> Hi Susan, >>>> >>>> The >>>> meaning of "addRequired(X)" is >>>> that your pass needs >>>> X to be >>>> run, and >>>> for X to >>>> be preserved by all passes >>>> that run after X >>>> and before your >>>> pass. >>>> The PHIElemination and >>>> TwoAddressInstruction >>>> passes do not >>>> preserve >>>> each other, hence there's >>>> no way for the pass >>>> manager to >>>> schedule >>>> them for you if you >>>> addRequire(...) them. >>>> >>>> The >>>> trick is that CodeGen will >>>> schedule both of these >>>> passes to >>>> be run >>>> before >>>> _any_ register allocation >>>> pass (see Passes.cpp), >>>> so you >>>> needn't >>>> require >>>> them explicitly - you can >>>> just assume they have >>>> been >>>> run. If you >>>> just >>>> remove those lines from your >>>> getAnalysisUsage >>>> method your pass >>>> should >>>> now run as you expect. >>>> >>>> Cheers, >>>> Lang. >>>> >>>> On Wed, >>>> Oct 31, 2012 at 1:46 PM, >>>> Susan Horwitz >>>> <horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>>> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>>>**> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>>> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu> >>>> <mailto:horwitz at cs.wisc.edu >>>> <mailto:horwitz at cs.wisc.edu>>>**>>> wrote: >>>> >>>> I'm >>>> trying to write a >>>> MachineFunctionPass to do >>>> register >>>> allocation. >>>> I >>>> have code that worked with >>>> an old version of >>>> LLVM. It >>>> does not >>>> >>>> work with llvm-3.1. (or various >>>> other versions >>>> that I've >>>> tried). >>>> >>>> The >>>> first problem is that >>>> including this line: >>>> >>>> >>>> AU.addRequiredID(__ >>>> >>>> TwoAddressInstructionPassID); >>>> >>>> >>>> in >>>> method getAnalysisUsage >>>> causes a runtime error: >>>> >>>> >>>> Unable to schedule 'Eliminate >>>> PHI nodes for register >>>> allocation' >>>> >>>> required by 'Unnamed pass: >>>> implement >>>> Pass::getPassName()' >>>> >>>> Unable to schedule pass >>>> >>>> UNREACHABLE executed at ... >>>> >>>> I'm >>>> invoking the pass like this >>>> (given input file >>>> foo.c): >>>> >>>> >>>> clang -emit-llvm -O0 -c foo.c >>>> -o foo.bc >>>> opt >>>> -mem2reg foo.bc > foo.ssa >>>> mv >>>> foo.ssa foo.bc >>>> llc >>>> -load Debug/lib/P4.so >>>> -regalloc=gc foo.bc >>>> >>>> >>>> >>>> I've attached my entire file >>>> (it's very short). >>>> Any help >>>> would be >>>> >>>> much appreciated! >>>> >>>> >>>> Susan Horwitz >>>> >>>> >>>> ______________________________ >>>> _________________ >>>> >>>> LLVM Developers mailing list >>>> LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu> >>>> <mailto:LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu>> >>>> <mailto:LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu> >>>> <mailto:LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu>>> >>>> <mailto:LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu> >>>> <mailto:LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu>> >>>> <mailto:LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu> >>>> <mailto:LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu>>>**> >>>> <mailto:LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu> >>>> <mailto:LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu>> >>>> <mailto:LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu> >>>> <mailto:LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu>>> >>>> <mailto:LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu> >>>> <mailto:LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu>> >>>> <mailto:LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu> >>>> <mailto:LLVMdev at cs.uiuc.edu >>>> <mailto:LLVMdev at cs.uiuc.edu>>>**>> >>>> >>>> http://llvm.cs.uiuc.edu >>>> http://lists.cs.uiuc.edu/ >>>> mailman/listinfo/llvmdev >>>> <http://lists.cs.uiuc.edu/__** >>>> mailman/listinfo/llvmdev<http://lists.cs.uiuc.edu/__mailman/listinfo/llvmdev> >>>> <http://lists.cs.uiuc.edu/** >>>> mailman/listinfo/llvmdev<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev> >>>> >> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>>> >>> >>> >> >> > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121113/d1fe0f73/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: Gcra.cpp Type: text/x-c++src Size: 9916 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121113/d1fe0f73/attachment.cpp>
Jakob Stoklund Olesen
2012-Nov-15 19:13 UTC
[LLVMdev] problem trying to write an LLVM register-allocation pass
On Nov 15, 2012, at 7:53 AM, Susan Horwitz <horwitz at cs.wisc.edu> wrote:> Lang - > > Attached is a new example for which I still get assembler errors. > > SusanHi Susan, You should never be getting assembler errors if 'llc -verify-machineinstrs' approves of your machine code. It might give you better error messages than the assembler. /jakob
Lang Hames
2012-Nov-15 19:21 UTC
[LLVMdev] problem trying to write an LLVM register-allocation pass
Thanks Jakob. I should have mentioned that earlier. :) When you see mismatched sizes on operands it's a fair bet that the subreg rewriting has gone wrong. I should have pulled that entirely out of the preg search loop in the previous example. Fixed version attached. - Lang. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121115/35fae7e7/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: Gcra.cpp Type: text/x-c++src Size: 9561 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121115/35fae7e7/attachment.cpp>
Susan Horwitz
2012-Nov-15 22:44 UTC
[LLVMdev] problem trying to write an LLVM register-allocation pass
I tried using this flag and it gave me errors on code that otherwise assembles and runs just fine (using the version of Gcra.cpp that Lang wrote). So I'm wondering if I should really be using the flag? I'm using it like this: llc -verify-machineinstrs -load Debug/lib/P4.so -regalloc=gc xxx.bc Susan On 11/15/2012 01:13 PM, Jakob Stoklund Olesen wrote:> > On Nov 15, 2012, at 7:53 AM, Susan Horwitz<horwitz at cs.wisc.edu> > wrote: > >> Lang - >> >> Attached is a new example for which I still get assembler errors. >> >> Susan > > Hi Susan, > > You should never be getting assembler errors if 'llc > -verify-machineinstrs' approves of your machine code. It might give > you better error messages than the assembler. > > /jakob >
Possibly Parallel Threads
- [LLVMdev] problem trying to write an LLVM register-allocation pass
- [LLVMdev] problem trying to write an LLVM register-allocation pass
- [LLVMdev] problem trying to write an LLVM register-allocation pass
- [LLVMdev] problem trying to write an LLVM register-allocation pass
- [LLVMdev] problem trying to write an LLVM register-allocation pass