pass: unexpected register allocation failure

[mmcloughlin]

@klauspost reported an unxepected register allocation failure in the following slack thread:

https://gophers.slack.com/archives/C6WDZJ70S/p1576430114006900?thread_ts=1576361104.001800&cid=C6WDZJ70S

The following code illustrates the problem (look for the FIXME comments)

https://github.com/klauspost/compress/pull/186/files#diff-60d6e6209d2fc7873851f07b946a5dc7R230

After an initial analysis using the experimental debug printer #6 it appears we are getting duplicate entries in the live register sets, for example <virtual:20:1:8> below.

...
		instruction {
			addr        = 0x0xc00010ed20
			opcode      = "CMPB"
			terminal    = false
			branch      = false
			conditional = false
			operands {
				0: CL
				1: DL
			}
			inputs {
				0: <virtual:22:1:1>
				1: <virtual:23:1:1>
			}
			outputs {
			}
			pred {
				0x0xc00010ec80
			}
			succ {
				0x0xc00010edc0
			}
			livein {
				size = 14
				<virtual:30:1:1>
				<virtual:20:1:8>
				<virtual:21:1:8>
				FP
				<virtual:20:1:8>
				<virtual:22:1:1>
				<virtual:30:1:4>
				SP
				<virtual:19:1:8>
				<virtual:29:1:2>
				<virtual:23:1:1>
				<virtual:29:1:4>
				<virtual:6:1:8>
				<virtual:29:1:1>
			}
			liveout {
				size = 12
				<virtual:19:1:8>
				<virtual:21:1:8>
				<virtual:20:1:8>
				<virtual:29:1:1>
				<virtual:29:1:4>
				<virtual:29:1:2>
				<virtual:6:1:8>
				<virtual:30:1:1>
				<virtual:30:1:4>
				<virtual:20:1:8>
				SP
				FP
			}
		}
...

Related #43 #65

[mmcloughlin]

In the below, the t.As64() call causes this avo program to fail register allocation.

func main() {
	TEXT("Issue100", NOSPLIT, "func() uint64")
	x := GP64()
	XORQ(x, x)
	for i := 1; i <= 100; i++ {
		t := GP64()
		MOVQ(U32(i), t)
		ADDQ(t.As64(), x)
	}
	Store(x, ReturnIndex(0))
	RET()
	Generate()
}

[klauspost]

@mmcloughlin I don't want to pressure, but it would help me a lot if you have any sort of outlook on this issue.

This is a hard blocker for me since I can't see a way to reasonably work around it.

[mmcloughlin]

@mmcloughlin I don't want to pressure, but it would help me a lot if you have any sort of outlook on this issue.

This is a hard blocker for me since I can't see a way to reasonably work around it.

Apologies for this. I haven't had a lot of time to devote to this with some recent travel. I'll should have some time this week.

Previously it had been possible to work around this by lifting some "local" registers to containing scopes. Is that no longer possible? It's not elegant I know.

[klauspost]

Previously it had been possible to work around this by lifting some "local" registers to containing scopes.

Not really. It would give false dependencies on these registers and they wouldn't be seen as free when they aren't used. The parser fairly enough just checks for references, not if the previous value is actually used.

This means that functions in-between cannot use the physical register. I tried to do this by never reusing registers unless I need to re-use the data.

For instance, if I need more registers I will spill values to the stack, I can store the register on stack, never use the virtual register again, and create a new virtual register when I reload the value.

If I move the virtual register out in scope and re-use it, the parser will never free the register and I am unable to gain anything from spilling it to the stack.

[klauspost]

It does seem that this is the intent, but there is just something that prevents .AsXX to properly de-reference the register, as nicely shown by your reproducer.

For example. If I go for the "allocate up front", I will keep the regs alive between uses which is not my intention.

tmp := GP64()
{
   MOVQ(U8(2), tmp)
   // do stuff with tmp...
}
{
   //... some unrelated code....
}
{
   XORQ(tmp, tmp)
   // do stuff with tmp...
}

Now tmp is kept alive across the entire section. If I allocate a tmp in the first and last block, the compiler should be able to reuse the register inbetween. Does that make sense?

Instead I would like to:

{
   tmp := GP64()
   MOVQ(U8(2), tmp)
   // do stuff with tmp...
}
{
   //... some unrelated code....
}
{
   tmp := GP64()
   XORQ(tmp, tmp)
   // do stuff with tmp...
}

This makes it clear that tmp is unused between the two blocks.

[mmcloughlin]

Thanks for the additional information. I definitely understand why you are using local registers, I was just hoping that might be a short-term fix for you.

I think I have a decent idea of where the problem is, but it's going to be a bit more of a far-reaching refactor than I had hoped. That was the main reason for introducing additional integration testing based on third-party packages #103. This will allow me to make the fix with greater confidence.

[mmcloughlin]

I made some decent progress on this today. After hacking and slashing for a while I have a refactored allocator that handles aliased registers fundamentally differently. I should have done it this way the first time, but I kind of "bolted on" register aliasing late in the game and hence ended up with this flaw.

At the moment the code works on ./examples/... and ./tests/..., as well as the reproducer I gave earlier in this issue (#100 (comment)) and another synthetic test I made up (e221927). I'm going to test it more thoroughly tomorrow. Unit tests are also broken and there's other cleanup required, but barring a major problem I could land this tomorrow.

cc @klauspost

[mmcloughlin]

@klauspost I optimistically closed this after landing #121, but obviously feel free to re-open this or file another issue if you are still seeing problems.

[klauspost]

Awesome, thanks!