[LSR, linux kernel] llc -O1: Broken module found, compilation aborted!

[edwintorok]

Bugzilla Link	9259
Resolution	FIXED
Resolved on	Mar 01, 2011 19:34
Version	trunk
OS	Linux
Blocks	#4440
Attachments	testcase bitcode, preprocessed C source code for reference
CC	@tkremenek,@sunfishcode

Extended Description

While compiling dw2102.c from the Linux kernel:

opt -verify says the bitcode is good, and llc -O0 works too:
$ opt -verify bugpoint-reduced-simplified.bc
$ llc -O0 bugpoint-reduced-simplified.bc

llc -O1 breaks the bitcode though:
$ llc -O1 bugpoint-reduced-simplified.bc

Instruction does not dominate all uses!
%tmp3 = add i64 %indvar, %tmp2
%tmp4 = trunc i64 %tmp3 to i32
Instruction does not dominate all uses!
%tmp4 = trunc i64 %tmp3 to i32
%conv29 = trunc i32 %tmp4 to i16, !dbg !​7709
Instruction does not dominate all uses!
%conv29 = trunc i32 %tmp4 to i16, !dbg !​7709
%call34 = call fastcc i32 @​dw210x_op_rw(%struct.usb_device* undef, i8 zeroext -75, i16 zeroext %conv29, i16 zeroext 0, i8* undef, i16 zeroext 2, i32 0) optsize noredzone, !dbg !​7712
Broken module found, compilation aborted!
0 llc 0x0000000000b9a4cf
1 llc 0x0000000000b9c732
2 libpthread.so.0 0x0000003f36a0ef60
3 libc.so.6 0x0000003f35e32165 gsignal + 53
4 libc.so.6 0x0000003f35e34f70 abort + 384
5 llc 0x0000000000b101eb
6 llc 0x0000000000ae9d0d llvm::FPPassManager::runOnFunction(llvm::Function&) + 557
7 llc 0x0000000000ae9e0b llvm::FPPassManager::runOnModule(llvm::Module&) + 75
8 llc 0x0000000000ae9897 llvm::MPPassManager::runOnModule(llvm::Module&) + 503
9 llc 0x0000000000ae9a17 llvm::PassManagerImpl::run(llvm::Module&) + 167
10 llc 0x000000000050523d main + 3885
11 libc.so.6 0x0000003f35e1ec4d __libc_start_main + 253
12 llc 0x00000000005031c9
Stack dump:
0. Program arguments: llc bugpoint-reduced-simplified.bc -O1

1.  Running pass 'Function Pass Manager' on module 'bugpoint-reduced-simplified.bc'.
   

2.  Running pass 'Module Verifier' on function '@dw2102_i2c_transfer'
   

Aborted

[nlewycky]

reduced testcase .ll

[lattner]

Dan, can you take a look at this? LSR is introducing broken IR:

0x102d177d0 Executing Pass 'Loop Strength Reduction' on Loop 'for.body'...

LSR on loop %for.body:
LSR has identified the following interesting factors and types: 1, (i64), (i32)
LSR is examining the following fixup sites:
UserInst=store undef, OperandValToReplace=%arrayidx42, LUIdx=0
UserInst=%conv29, OperandValToReplace=%add, LUIdx=1
LSR found 2 uses:
LSR is examining the following uses:
LSR Use: Kind=Address of i8, Offsets={0}, widest fixup type: i8
reg({0,+,1}<%for.body>)
LSR Use: Kind=Basic, Offsets={0}, widest fixup type: i32
reg(((zext i16 {undef,+,0,+,1}<%for.body> to i32) + {0,+,1}<%for.body>))

After generating reuse formulae:
LSR is examining the following uses:
LSR Use: Kind=Address of i8, Offsets={0}, widest fixup type: i8*
reg({0,+,1}<%for.body>)
LSR Use: Kind=Basic, Offsets={0}, widest fixup type: i32
reg(((zext i16 {undef,+,0,+,1}<%for.body> to i32) + {0,+,1}<%for.body>))
reg({0,+,1}<%for.body>) + reg((zext i16 {undef,+,0,+,1}<%for.body> to i32))
reg({0,+,1}<%for.body>) + reg((zext i16 {undef,+,0,+,1}<%for.body> to i64))
Filtering for use LSR Use: Kind=Address of i8, Offsets={0}, widest fixup type: i8*
Filtering for use LSR Use: Kind=Basic, Offsets={0}, widest fixup type: i32
Filtering out formula reg({0,+,1}<%for.body>) + reg((zext i16 {undef,+,0,+,1}<%for.body> to i32))
in favor of formula reg(((zext i16 {undef,+,0,+,1}<%for.body> to i32) + {0,+,1}<%for.body>))

After filtering out undesirable candidates:
LSR is examining the following uses:
LSR Use: Kind=Address of i8, Offsets={0}, widest fixup type: i8*
reg({0,+,1}<%for.body>)
LSR Use: Kind=Basic, Offsets={0}, widest fixup type: i32
reg(((zext i16 {undef,+,0,+,1}<%for.body> to i32) + {0,+,1}<%for.body>))
reg({0,+,1}<%for.body>) + reg((zext i16 {undef,+,0,+,1}<%for.body> to i64))
New best at 2 regs, with addrec cost 1, plus 1 base add, plus 1 setup cost. Regs: {0,+,1}<%for.body> (zext i16 {undef,+,0,+,1}<%for.body> to i64)

The chosen solution requires 2 regs, with addrec cost 1, plus 1 base add, plus 1 setup cost:
LSR Use: Kind=Address of i8, Offsets={0}, widest fixup type: i8*
reg({0,+,1}<%for.body>)
LSR Use: Kind=Basic, Offsets={0}, widest fixup type: i32
reg({0,+,1}<%for.body>) + reg((zext i16 {undef,+,0,+,1}<%for.body> to i64))
0x102d177d0 Made Modification 'Loop Strength Reduction' on Loop 'for.body'...
0x102d177d0 Freeing Pass 'Loop Strength Reduction' on Loop 'for.body'...

0x102d177d0 Freeing Pass 'Loop Strength Reduction' on Loop 'for.body'...
0x102d177d0 Freeing Pass 'Induction Variable Users' on Loop 'for.body'...
0x102d177d0 Freeing Pass 'Canonicalize natural loops' on Loop 'for.body'...
0x102d177d0 Executing Pass 'Unnamed pass: implement Pass::getPassName()' on Loop 'for.body'...
*** IR Dump After Loop Strength Reduction ***
for.body: ; preds = %for.body, %for.body.lr.ph
%indvar = phi i64 [ 0, %for.body.lr.ph ], [ %tmp, %for.body ]
%value.0171 = phi i16 [ undef, %for.body.lr.ph ], [ %conv29, %for.body ]
%indvar1 = inttoptr i64 %indvar to i8*
%tmp = add i64 %indvar, 1
%tmp2 = zext i16 %value.0171 to i64
%tmp4 = trunc i64 %tmp3 to i32
%conv29 = trunc i32 %tmp4 to i16
%tmp3 = add i64 %indvar, %tmp2
%call34 = call fastcc i32 @​dw210x_op_rw(i8 zeroext -75, i16 zeroext %conv29, i16 zeroext 0, i8* undef, i16 zeroext 2, i32 0) optsize noredzone
store i8 undef, i8* %indvar1, align 1
br label %for.body

Here it introduced tmp3 after tmp4.

[lattner]

repro with:
llc -O1 pr9259.ll -debug-pass=Executions -debug -print-after-all

[sunfishcode]

Confirmed; the bug is in the code placement half of LSR, with the handling of non-linear expressions, which isn't a huge surprise.

While looking at this, I wonder if this isn't also a bug in the original code:

	/* read stv0299 register */
	request = 0xb5;
	value = msg[0].buf[0];/* register */
	for (i = 0; i < msg[1].len; i++) {
		value = value + i;
		ret = dw2102_op_rw(d->udev, 0xb5,
			value, buf6, 2, DW2102_READ_MSG);
		msg[1].buf[i] = buf6[0];

	}

I don't know anything about the hardware this driver is written for, but is 'value' really intended to increment quadratically? That seems suspicious. One wonders if the following is what was intended:

	[...]
	for (i = 0; i < msg[1].len; i++) {
		ret = dw2102_op_rw(d->udev, 0xb5,
			value + i, buf6, 2, DW2102_READ_MSG);
		msg[1].buf[i] = buf6[0];

	}

[tkremenek]

cloned to rdar://problem/9065752

[sunfishcode]

Fixed in r126812.