[LLVMdev] problem trying to write an LLVM register-allocation pass
Susan Horwitz
horwitz at cs.wisc.edu
Mon Nov 5 14:58:38 PST 2012
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 --------------
A non-text attachment was scrubbed...
Name: Gcra.cpp
Type: text/x-c++src
Size: 6275 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121105/757e150a/attachment.cpp>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bug1.c
Type: text/x-csrc
Size: 250 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121105/757e150a/attachment.c>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bug1.bc
Type: application/octet-stream
Size: 736 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121105/757e150a/attachment.obj>
More information about the llvm-dev
mailing list