Re: [PATCH 1/2] sparse, llvm: group PHI nodes at the top of each BB

["Jonathan Neuschäfer" <j.neuschaefer@gmx.net>]

On Tue, Oct 16, 2012 at 08:59:27PM +0300, Pekka Enberg wrote:
> On Fri, Oct 12, 2012 at 9:25 PM, Pekka Enberg <penberg@kernel.org> wrote:
> > Sounds plausible but I'm still uneasy with the idea that LLVM backend
> > needs to reshuffle instructions like this.

Actually, the situation of Phi nodes in LLVM is actually slightly more
complex: They require "one pair (of value and BB) for each predecessor
basic block of the current block"[1]. This mean that we'll sometimes
need to insert phi nodes into BBs that don't directly use a value.
Consider the following piece of C code:

	extern int done(void);
	extern void foo(int);

	static void test(void) {
		int i;
		for (i = 0; ; i++) {
			if (done())
				break;
			foo(i);
		}
	}

Running it through test-linearize exhibits the problem:
[ I renamed the basic blocks to L0-L3 to increase readability. ]

	test:
	.L0:
		<entry-point>
		phisrc.32   %phi2(i) <- $0
		br          .L1

	.L1:
		call.32     %r1 <- done
		br          %r1, .L3, .L2

	.L2:
		phi.32      %r2(i) <- %phi2(i), %phi3(i)
		call        foo, %r2(i)
		add.32      %r4 <- %r2(i), $1
		phisrc.32   %phi3(i) <- %r4
		br          .L1

	.L3:
		ret

To comply with the "LLVM rules" we'd need to move the phi intruction up
into "L1".


regards,
Jonathan