[LLVMdev] problem trying to write an LLVM register-allocation pass

[Susan Horwitz]

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

[Lang Hames]

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. 

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Susan Horwitz]

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 <hor...@cs.wisc.edu
> <mailto:hor...@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

> LLV...@cs.uiuc.edu <mailto:LLV...@cs.uiuc.edu> http://llvm.cs.uiuc.edu

[Lang Hames]

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.

[Susan Horwitz]

Lang -

My previous problem (the failed assertion due to a vreg that was not
used or defined) was because I was using a debugging version of LLVM
with assertions enabled. It seems that there are "extra" assertions in
that version.

When I run my register allocator in the "normal" version of LLVM, there
is no problem with that simple example.

However, for other examples that have instructions that do use/define
virtual registers, I'm getting bad assembly code.

I would really like to avoid changing to the "indirect" approach to
register mapping that you suggest (if possible). My code using the
"direct" approach worked fine with an old version of LLVM, and I would
like to get it to work with llvm-3.1.

I wrote a very simple register allocator (attached) that just replaces
each vreg in the code with the first preg in its class. I understand
that this is not going to give me correct register usage, but it should
at least give me assembly code that can be assembled. However, it does
not. I get this error from the assembler:

Error: Incorrect register `%rax' used with `l' suffix

cause by this instruction:

cmpl $1, %rax

The input is tst.c (also attached).

Any help you can provide in understanding what is causing this problem
would be much appreciated. I'm not even sure which instance of a vreg
is causing the problem. I used to be able to print machine instructions
by just using <<, but that no longer works. So even help with that
aspect of the problem would be very helpful.

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 <hor...@cs.wisc.edu
> <mailto:hor...@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

> <mailto:LLV...@cs.uiuc.edu <mailto:LLV...@cs.uiuc.edu>>

> http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/ mailman/listinfo/llvmdev

> <http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
>
>
>
>

[Susan Horwitz]

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 <hor...@cs.wisc.edu
> <mailto:hor...@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

> <mailto:LLV...@cs.uiuc.edu <mailto:LLV...@cs.uiuc.edu>>

> http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/ mailman/listinfo/llvmdev

> <http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
>
>
>
>

[Lang Hames]

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.

[Susan Horwitz]

I still get a coredump:

0 libLLVM-3.1.so 0x00007f0158a4e67f
1 libLLVM-3.1.so 0x00007f0158a500ca
2 libpthread.so.0 0x0000003a86c0f500
3 libLLVM-3.1.so 0x00007f01583c346c
4 libLLVM-3.1.so 0x00007f0158546349
llvm::FPPassManager::runOnFunction(llvm::Function&) + 521
5 libLLVM-3.1.so 0x00007f01585463e3
llvm::FPPassManager::runOnModule(llvm::Module&) + 51
6 libLLVM-3.1.so 0x00007f0158545fae
llvm::MPPassManager::runOnModule(llvm::Module&) + 462
7 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,
>

> <http://lists.cs.uiuc.edu/__mailman/listinfo/llvmdev
> <http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>>
>
>
>
>
>
>

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Lang Hames]

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.

[Susan Horwitz]

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

[Lang Hames]

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.

[Susan Horwitz]

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

[Lang Hames]

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.

[Susan Horwitz]

Lang -

This is very helpful! Now all my small tests work. However, large
tests are still failing. For example, with a debugging version of
LLVM-3.1 I am getting this failed assertion:
8-bit H register can not be copied outside GR8_NOREX

It seems that there are restrictions on register use that I don't know
about. Can you tell me what the above means and/or where I can look to
understand what the problem is and how to deal with this issue?

Thanks much!!

Susan

On 11/04/2012 06:19 PM, Lang Hames wrote:
> Hi Susan,
>

>>> 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>

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Susan Horwitz]

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,
>

>>> 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>

[Lang Hames]

Hi Susan,

Sorry for the delayed response. Thanks for the test cases - I'm looking in to this now.

- Lang.

[Lang Hames]

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.

[Susan Horwitz]

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

[Lang Hames]

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.

[Susan Horwitz]

Sorry about that.  I created the assembly file and attached it (as math.txt).

Susan

[Susan Horwitz]

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.

>>> <mailto:hor...@cs.wisc.edu
>>> <mailto:hor...@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>

[Lang Hames]

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.

[Lang Hames]

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.

[Susan Horwitz]

Lang -

Attached is a new example for which I still get assembler errors.

Susan

On 11/14/2012 12:45 AM, Lang Hames wrote:
> 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 <hor...@cs.wisc.edu

> <mailto:hor...@cs.wisc.edu>> wrote:
>
> Lang -
>

> <mailto:hor...@cs.wisc.edu <mailto:hor...@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
> <hor...@cs.wisc.edu <mailto:hor...@cs.wisc.edu>

> (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
> <lha...@gmail.com <mailto:lha...@gmail.com>

> <mailto:lha...@gmail.com <mailto:lha...@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
> <hor...@cs.wisc.edu <mailto:hor...@cs.wisc.edu>

> <mailto:hor...@cs.wisc.edu <mailto:hor...@cs.wisc.edu>
> <mailto:hor...@cs.wisc.edu
> <mailto:hor...@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://lists.cs.uiuc.edu/__mailman/listinfo/llvmdev>

[Jakob Stoklund Olesen]

On Nov 15, 2012, at 7:53 AM, Susan Horwitz <hor...@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

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Lang Hames]

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.

[Lang Hames]

Hi Susan,

Jakob just pointed me to 'MachineOperand::substPhysReg(unsigned preg, const TargetRegisterInfo& TRI)'. That substitutes the given physreg for a virtreg operand, taking the subregister index into account. That is what my examples have been doing manually. Using substPhysReg would allow you to tidy the Gcra code up slightly.

- Lang.

[Susan Horwitz]

Thanks Lang, I'll try substPhysReg.

I did try your latest code, and although it made the assembler errors go
away, now some of my tests produce bad output when executed. I need to
look into that some more... (I did change my "usedPregSet" to be ALL
pregs used in the whole function, not just those in the current
instruction, so the problem should not be the erroneous over-writing of
a live preg.)

Also, I'm confused about the code that gets a preg for a given vreg.
Previously,you gave me code that takes into account the "allocation
order" and the "reserved regs", including the following:
BitVector reservedRegs = TRI->getReservedRegs(Fn);

ArrayRef<uint16_t> rawOrder = trc->getRawAllocationOrder(Fn);
ArrayRef<uint16_t>::iterator rItr = rawOrder.begin();

while (rItr != rawOrder.end()) {
while (rItr != rawOrder.end() && reservedRegs.test(*rItr)) {
++rItr;
}

As I recall, this prevented some failed assertion. Why has that code
gone away?

Susan

[Lang Hames]

Hi Susan,

It looks like the allocation-order aware code didn't make it into your email on November 7th, and I didn't think to add it back in. This code is important, and its omission could be the cause of the errors your seeing.

- Lang.

[Susan Horwitz]

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

[Lang Hames]

Hi Susan,

To my knowledge the verifier doesn't produce false positives with any of the in-tree allocators. If it is raising an error that is worth investigating. Is it raising an error on any simple test cases? Can you share the failing case?

- Lang.

[Lang Hames]

Hi Susan,

Jakob pointed out to me that the Gcra.cpp allocator doesn't record basic-block live-ins, which are used by the verifier to check correctness.

You can record which variables are live into a basic block with MachineBasicBlock::addLiveIn(unsigned physReg). I don't know the verifier well, but if it's using other built in infrastructure for register allocation then it may not be a good fit for your allocator.

I'll try to find time to look at the example files you sent in the next couple of days.

Cheers,

Lang.

On Thu, Nov 15, 2012 at 5:21 PM, Susan Horwitz <hor...@cs.wisc.edu> wrote:

Well, now I can't reproduce what I thought I had before (an example that works fine with your code except when using that flag).  I do have a small example that works fine with *my* code except when using that flag.  I've attached the source (.c), the assembly that my code produces w/o using the "verify" flag (.s), the output of trying to create assembly *with* the "verify" flag (.out), and the .bc file used as input to my register allocator.  If you can identify a problem by looking at these files, that would be great!

I can supply my register allocator if you'd like to have it, but it involves a number of (longish) files.

Thanks for any insights you can provide on this!

Susan

On 11/15/2012 06:45 PM, Lang Hames wrote:

Hi Susan,

To my knowledge the verifier doesn't produce false positives with any of
the in-tree allocators. If it is raising an error that is worth
investigating. Is it raising an error on any simple test cases? Can you
share the failing case?

- Lang.


On Thu, Nov 15, 2012 at 2:44 PM, Susan Horwitz <hor...@cs.wisc.edu

<mailto:hor...@cs.wisc.edu>> wrote:

    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<hor...@cs.wisc.edu

        <mailto:hor...@cs.wisc.edu>>

[Jakob Stoklund Olesen]

On Nov 15, 2012, at 8:04 PM, Lang Hames <lha...@gmail.com> wrote:

> Jakob pointed out to me that the Gcra.cpp allocator doesn't record basic-block live-ins, which are used by the verifier to check correctness.
>
> You can record which variables are live into a basic block with MachineBasicBlock::addLiveIn(unsigned physReg). I don't know the verifier well, but if it's using other built in infrastructure for register allocation then it may not be a good fit for your allocator.

To clarify, the live-in lists are not there for the verifier's benefit. They are used by various post-RA passes that care about register liveness, so they are required to be correct.

[hor...@cs.wisc.edu]

Lang -

I used addLiveIn and that fixed almost all of the problems with the verify
flag, including the example I sent previously, so no need to look into
that. I still have a few cases where I'm getting "verify" errors, though
they don't seem to affect the correctness of the final code. I will send
an example ASAP.

Thanks for all your help!

Susan

[Susan Horwitz]

I have a new problem: Register RBP is used in a function foo. (I am not
allocating RBP to any virtual register, the instances of RBP in function
foo are in the machine code when my register allocator starts.)

Function foo calls function bar. Register RBP is not saved across the
call, though it is live after the call. Function bar includes a virtual
register. The code that I'm using to find the registers available to be
allocated to that virtual register includes EBP in that available-preg
set. This is a disaster, since writing into EBP clobbers RBP.

I tried to add code to save all live physical registers across calls,
but I don't know how to get the appropriate TargetRegisterClass (needed
to call CreateSpillStackObject).

Is there a different way to save/restore RBP across calls? Or a way to
get its TargetRegisterClass?

Susan

[Lang Hames]

Hi Susan,

RBP is used as the frame pointer on x86 (hence its automatic appearance in your code), and shouldn't be allocated to any vreg in function bar. Loading/saving RBP should be managed by the stack frame setup/teardown code.

If it doesn't already, your allocator should filter out reserved registers (See MachineRegisterInfo::isReserved(unsigned preg)) when assigning physregs.

ArrayRef<MCPhysReg> pregs = TRC->getRawAllocationOrder(&MF);

for (int i = 0; i < pregs.size(); ++i) {

  if (MRI->isReserved(pregs[i]))

    continue;

  // use preg...

}

You could also use the AllocationOrder class to simplify the task of finding valid pregs, though it does require you to use VirtRegMap. 

If you are already checking the reserved regs then I've misdiagnosed the problem. I'd be happy to dig further if you can point me to a copy of your allocator and a test case.

Cheers,

Lang.

[Susan Horwitz]

On 11/30/2012 6:36 PM, Lang Hames wrote:

RBP is used as the frame pointer on x86 (hence its automatic appearance in your code), and shouldn't be allocated to any vreg in function bar. Loading/saving RBP should be managed by the stack frame setup/teardown code.

If it doesn't already, your allocator should filter out reserved registers (See MachineRegisterInfo::isReserved(unsigned preg)) when assigning physregs.

I AM filtering out reserved registers.

I am not allocating RBP in function bar, I am allocating EBP, because it is NOT in the list of reserved registers for function bar.

Neither register RBP nor register EBP is saved/restored across the call from foo to bar, either by the code for the call or the code for entry to bar.

The input C file that is causing this problem is flex.c (attached).� The calling function is "yyparse" and the called function is "scinstal".

Here are the reserved registers for yyparse: { 7 44 54 106 111 114 118 }

Here are the reserved registers for scinstal: { 54 111 114 }

Register EBP is preg 44, which is NOT in the reserved list for scinstal (nor is it an alias of any of those reserved registers; the aliases are� { 50 64 117 118 }).� I don;t know which preg corresponds to RBP.

You say that RBP should be saved/restored across the call.� I tried to generate that code, but, as I said in my previous mail,� I don't know how to get the appropriate TargetRegisterClass (needed to call CreateSpillStackObject).�� Should I instead be generating code to save register EBP at the start of scinstal, restoring it at the end of that function?

Susan

ArrayRef<MCPhysReg> pregs = TRC->getRawAllocationOrder(&MF);

for (int i = 0; i < pregs.size(); ++i) {

� if (MRI->isReserved(pregs[i]))

� � continue;

� // use preg...

}

You could also use the AllocationOrder class to simplify the task of finding valid pregs, though it does require you to use VirtRegMap.�

If you are already checking the reserved regs then I've misdiagnosed the problem. I'd be happy to dig further if you can point me to a copy of your allocator and a test case.

Cheers,

Lang.

On Thu, Nov 29, 2012 at 3:49 PM, Susan Horwitz <hor...@cs.wisc.edu> wrote:

I have a new problem: Register RBP is used in a function foo. �(I am not allocating RBP to any virtual register, the instances of RBP in function foo are in the machine code when my register allocator starts.)

Function foo calls function bar. �Register RBP is not saved across the call, though it is live after the call. �Function bar includes a virtual register. �The code that I'm using to find the registers available to be allocated to that virtual register includes EBP in that available-preg set. �This is a disaster, since writing into EBP clobbers RBP.

I tried to add code to save all live physical registers across calls, but I don't know how to get the appropriate TargetRegisterClass (needed to call CreateSpillStackObject).

Is there a different way to save/restore RBP across calls? �Or a way to get its TargetRegisterClass?

Susan

[Joerg Sonnenberger]

On Sat, Dec 01, 2012 at 11:31:06AM -0600, Susan Horwitz wrote:
> I am not allocating RBP in function bar, I am allocating EBP,
> because it is NOT in the list of reserved registers for function
> bar.

rbp is callee-saved. If you want to use it or part of it in bar, you are
responsible for saving and restoring it.

Joerg

[Lang Hames]

Hi Susan,

Thanks for the clarification, and the test case. I think I know what the problem is now. Saving and restoring RBP is the job of the PEI (PrologEpilogInsertion) pass, which runs after register allocation. To determine which callee-saved physregs actually need to be saved it checks MachineRegisterInfo::isPhysRegOrOverlapUsed(unsigned reg). Your register allocator needs to notify MachineRegisterInfo about the physical registers that have been assigned by calling MachineRegisterInfo::setPhysRegUsed(unsigned reg).

You only need to call setPhysRegUsed for the physregs that you actually use. You do not need to specify the aliasing registers.

Hope this helps!

Regards,

Lang.

On Sat, Dec 1, 2012 at 9:31 AM, Susan Horwitz <hor...@cs.wisc.edu> wrote:

On 11/30/2012 6:36 PM, Lang Hames wrote:

RBP is used as the frame pointer on x86 (hence its automatic appearance in your code), and shouldn't be allocated to any vreg in function bar. Loading/saving RBP should be managed by the stack frame setup/teardown code.

If it doesn't already, your allocator should filter out reserved registers (See MachineRegisterInfo::isReserved(unsigned preg)) when assigning physregs.

I AM filtering out reserved registers.

I am not allocating RBP in function bar, I am allocating EBP, because it is NOT in the list of reserved registers for function bar.

Neither register RBP nor register EBP is saved/restored across the call from foo to bar, either by the code for the call or the code for entry to bar.

The input C file that is causing this problem is flex.c (attached).  The calling function is "yyparse" and the called function is "scinstal".

Here are the reserved registers for yyparse: { 7 44 54 106 111 114 118 }

Here are the reserved registers for scinstal: { 54 111 114 }

Register EBP is preg 44, which is NOT in the reserved list for scinstal (nor is it an alias of any of those reserved registers; the aliases are  { 50 64 117 118 }).  I don;t know which preg corresponds to RBP.

You say that RBP should be saved/restored across the call.  I tried to generate that code, but, as I said in my previous mail,  I don't know how to get the appropriate TargetRegisterClass (needed to call CreateSpillStackObject).   Should I instead be generating code to save register EBP at the start of scinstal, restoring it at the end of that function?

Susan

ArrayRef<MCPhysReg> pregs = TRC->getRawAllocationOrder(&MF);

for (int i = 0; i < pregs.size(); ++i) {

  if (MRI->isReserved(pregs[i]))

    continue;

  // use preg...

}

You could also use the AllocationOrder class to simplify the task of finding valid pregs, though it does require you to use VirtRegMap. 

If you are already checking the reserved regs then I've misdiagnosed the problem. I'd be happy to dig further if you can point me to a copy of your allocator and a test case.

Cheers,

Lang.

On Thu, Nov 29, 2012 at 3:49 PM, Susan Horwitz <hor...@cs.wisc.edu> wrote:

I have a new problem: Register RBP is used in a function foo.  (I am not allocating RBP to any virtual register, the instances of RBP in function foo are in the machine code when my register allocator starts.)

Function foo calls function bar.  Register RBP is not saved across the call, though it is live after the call.  Function bar includes a virtual register.  The code that I'm using to find the registers available to be allocated to that virtual register includes EBP in that available-preg set.  This is a disaster, since writing into EBP clobbers RBP.

I tried to add code to save all live physical registers across calls, but I don't know how to get the appropriate TargetRegisterClass (needed to call CreateSpillStackObject).

Is there a different way to save/restore RBP across calls?  Or a way to get its TargetRegisterClass?

Susan

[Susan Horwitz]

Aha, yes, this is definitely helpful!

Is there documentation on all this somewhere?  I still have errors for some large test inputs, and it would be nice if I didn't have to keep bugging you for information.

Thanks!

Susan

[Lang Hames]

Hi Susan,

There is some high level documentation about the target independent code generator here, but it doesn't contain the specifics needed to build an allocator from scratch (e.g, it doesn't describe the issue you just encountered). In my experience the best option has been to just read the existing allocators and see how they work.

If your allocator project yields any documentation on building an LLVM register allocator, patches to our documentation are always welcome. Otherwise, I'll try to find time to distill the lessons from this thread and add them to the target independent code generator document. 

Cheers,

Lang.