search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
29.17k stars 12.03k forks source link

[SelectionDAG] Seemingly incorrect updating of chains in UpdateChains() #35512

Closed JonPsson closed 6 years ago

JonPsson commented 6 years ago
Bugzilla Link 36164
Resolution FIXED
Resolved on Feb 06, 2018 09:15
Version trunk
OS Linux
Attachments reduced testcase
CC @hfinkel,@RKSimon,@JonPsson,@uweigand

Extended Description

Incorrect updating of DAG chains during Select(), which leads to a node having a deleted node as chain input.

Run with

llc -mtriple=s390x-linux-gnu -mcpu=z13 -disable-basicaa ./tc_DAG_badchain.ll

llc: lib/CodeGen/SelectionDAG/InstrEmitter.cpp:802: void llvm::InstrEmitter::EmitMachineNode(llvm::SDNode*, bool, bool, llvm::DenseMap<llvm::SDValue, unsigned int>&): Assertion `NumMIOperands >= II.getNumOperands() && NumMIOperands <= II.getNumOperands()\

Reduced DAG just before t50 gets selected:

t378: i64,ch = loadLD8[@g_938](tbaa=<0x51f0978)(dereferenceable)> t0, t402, undef:i64 t313: i32,ch = load<Volatile LD4[getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_8

t516: ch = TokenFactor t391:1, t513, t378:1

t520: i32,ch = load<Volatile LD4[getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @&#8203;g_832, i64 0, i32 0)](tbaa=<0x51f14b8>)(dereferenceable)> t517, t398, undef:i64

t521: ch = TokenFactor t516, t520:1 t518: ch = storeST4[@g_69](tbaa=<0x51f5db8)> t517, Constant:i32<3>, t400, undef:i64 t519: ch = TokenFactor t516, t518

t482: ch = TokenFactor t519, t521 t478: ch = TokenFactor t521, t519

t524: i32 = TargetConstant<1> t49: i64 = add t378, Constant:i64<24> t50: ch = storeST8[@g_938](tbaa=<0x51f0978)> t482, t49, t402, undef:i64

    t475: i32,ch = LRL<Mem:Volatile LD4[getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @&#8203;g_832, i64 0, i32 0)](tbaa=<0x51f14b8>)(dereferenceable)> TargetGlobalAddress:i64<%0* @&#8203;g_832> 0, t478

The DAG has many (volatile) memory accesses with multiple token factors (see below for full DAG)

The t378 load has one (value) use which is the t49 add which is then stored by t50.

The t50 store gets morphed (with load and add folded into it) to 't50: i32,ch = AGSI...', which is an addition of immediate to memory. This seems ok regarding the chains, but I'm not 100% sure...

The problem then is with t475, which was chained via t478 eventually up to t378. It does not seem to get the chain properly updated: After void SelectionDAGISel::UpdateChains(), it becomes

    t475: i32,ch = LRL<Mem:Volatile LD4[getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @&#8203;g_832, i64 0, i32 0)](tbaa=<0x51f14b8>)(dereferenceable)> TargetGlobalAddress:i64<%0* @&#8203;g_832> 0, <<Deleted Node!>>:ch

This later leads to an incorrect operand during instruction emission and the assert triggers for t475.

Complete DAG just before t50 gets selected:

CurDAG->dump() = SelectionDAG has 71 nodes: t0: ch = EntryToken t398: i64 = SystemZISD::PCREL_WRAPPER TargetGlobalAddress:i64<%0 @​g_832> 0 t400: i64 = SystemZISD::PCREL_WRAPPER TargetGlobalAddress:i64<i32 @​g_69> 0 t402: i64 = SystemZISD::PCREL_WRAPPER TargetGlobalAddress:i64<i64 @​g_938> 0 t378: i64,ch = loadLD8[@g_938](tbaa=<0x51f0978)(dereferenceable)> t0, t402, undef:i64 t313: i32,ch = load<Volatile LD4[getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0" @​g_832, i64 0, i32 0)](tbaa=<0x51f14b8>)(dereferenceable)> t0, t398, undef:i64 t315: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t313:1, t398, undef:i64 t318: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t315:1, t398, undef:i64 t321: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t318:1, t398, undef:i64 t324: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t321:1, t398, undef:i64 t327: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t324:1, t398, undef:i64 t330: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t327:1, t398, undef:i64 t333: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t330:1, t398, undef:i64 t336: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t333:1, t398, undef:i64 t339: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t336:1, t398, undef:i64 t342: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t339:1, t398, undef:i64 t345: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t342:1, t398, undef:i64 t348: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t345:1, t398, undef:i64 t351: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t348:1, t398, undef:i64 t354: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t351:1, t398, undef:i64 t358: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t354:1, t398, undef:i64 t361: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t358:1, t398, undef:i64 t364: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t361:1, t398, undef:i64 t387: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t364:1, t398, undef:i64 t391: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t387:1, t398, undef:i64 t404: i64 = SystemZISD::PCREL_WRAPPER TargetGlobalAddress:i64<i32 @​g_73> 0 t5: ch = storeST4[@g_73](tbaa=<0x51f5db8)> t0, Constant:i32<1>, t404, undef:i64 t381: ch = storeST4[@g_69](tbaa=<0x51f5db8)> t0, Constant:i32<1>, t400, undef:i64 t522: ch = TokenFactor t354:1, t5, t381 t493: ch = storeST4[@g_69](tbaa=<0x51f5db8)> t522, Constant:i32<2>, t400, undef:i64 t497: ch = TokenFactor t358:1, t493 t498: ch = storeST4[@g_69](tbaa=<0x51f5db8)> t497, Constant:i32<3>, t400, undef:i64 t502: ch = TokenFactor t361:1, t498 t503: ch = storeST4[@g_69](tbaa=<0x51f5db8)> t502, Constant:i32<0>, t400, undef:i64 t507: ch = TokenFactor t364:1, t503 t508: ch = storeST4[@g_69](tbaa=<0x51f5db8)> t507, Constant:i32<1>, t400, undef:i64 t512: ch = TokenFactor t387:1, t508 t513: ch = storeST4[@g_69](tbaa=<0x51f5db8)> t512, Constant:i32<2>, t400, undef:i64 t517: ch = TokenFactor t391:1, t513 t516: ch = TokenFactor t391:1, t513, t378:1 t520: i32,ch = load<Volatile LD4[getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0" @​g_832, i64 0, i32 0)](tbaa=<0x51f14b8>)(dereferenceable)> t517, t398, undef:i64 t521: ch = TokenFactor t516, t520:1 t518: ch = storeST4[@g_69](tbaa=<0x51f5db8)> t517, Constant:i32<3>, t400, undef:i64 t519: ch = TokenFactor t516, t518 t482: ch = TokenFactor t519, t521 t478: ch = TokenFactor t521, t519 t524: i32 = TargetConstant<1> t396: i64 = SystemZISD::PCREL_WRAPPER TargetGlobalAddress:i64<i1 @​g_11> 0 t49: i64 = add t378, Constant:i64<24> t50: ch = storeST8[@g_938](tbaa=<0x51f0978)> t482, t49, t402, undef:i64 t480: ch = STRLMem:ST4[@g_69](tbaa=<0x51f5db8)> Constant:i32<4>, TargetGlobalAddress:i64<i32 @​g_69> 0, t478 t481: ch = TokenFactor t482, t480 t475: i32,ch = LRL<Mem:Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> TargetGlobalAddress:i64<%0* @​g_832> 0, t478 t477: ch = TokenFactor t50, t481, t475:1 t394: ch = MVIMem:ST1[@g_11](align=4) t396, TargetConstant:i64<0>, TargetConstant:i64<1>, t477 t58: ch = J BasicBlock:ch< 0x524f328>, t394

Complete DAG just after t50 was selected:

CurDAG->dump() = SelectionDAG has 65 nodes: t0: ch = EntryToken t398: i64 = SystemZISD::PCREL_WRAPPER TargetGlobalAddress:i64<%0 @​g_832> 0 t400: i64 = SystemZISD::PCREL_WRAPPER TargetGlobalAddress:i64<i32 @​g_69> 0 t313: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t0, t398, undef:i64 t315: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t313:1, t398, undef:i64 t318: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t315:1, t398, undef:i64 t321: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t318:1, t398, undef:i64 t324: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t321:1, t398, undef:i64 t327: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t324:1, t398, undef:i64 t330: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t327:1, t398, undef:i64 t333: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t330:1, t398, undef:i64 t336: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t333:1, t398, undef:i64 t339: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t336:1, t398, undef:i64 t342: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t339:1, t398, undef:i64 t345: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t342:1, t398, undef:i64 t348: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t345:1, t398, undef:i64 t351: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t348:1, t398, undef:i64 t354: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t351:1, t398, undef:i64 t358: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t354:1, t398, undef:i64 t361: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t358:1, t398, undef:i64 t364: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t361:1, t398, undef:i64 t387: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t364:1, t398, undef:i64 t391: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t387:1, t398, undef:i64 t404: i64 = SystemZISD::PCREL_WRAPPER TargetGlobalAddress:i64<i32 @​g_73> 0 t5: ch = storeST4[@g_73](tbaa=<0x51f5db8)> t0, Constant:i32<1>, t404, undef:i64 t381: ch = storeST4[@g_69](tbaa=<0x51f5db8)> t0, Constant:i32<1>, t400, undef:i64 t522: ch = TokenFactor t354:1, t5, t381 t493: ch = storeST4[@g_69](tbaa=<0x51f5db8)> t522, Constant:i32<2>, t400, undef:i64 t497: ch = TokenFactor t358:1, t493 t498: ch = storeST4[@g_69](tbaa=<0x51f5db8)> t497, Constant:i32<3>, t400, undef:i64 t502: ch = TokenFactor t361:1, t498 t503: ch = storeST4[@g_69](tbaa=<0x51f5db8)> t502, Constant:i32<0>, t400, undef:i64 t507: ch = TokenFactor t364:1, t503 t508: ch = storeST4[@g_69](tbaa=<0x51f5db8)> t507, Constant:i32<1>, t400, undef:i64 t512: ch = TokenFactor t387:1, t508 t513: ch = storeST4[@g_69](tbaa=<0x51f5db8)> t512, Constant:i32<2>, t400, undef:i64 t517: ch = TokenFactor t391:1, t513 t402: i64 = SystemZISD::PCREL_WRAPPER TargetGlobalAddress:i64<i64 @​g_938> 0 t520: i32,ch = load<Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> t517, t398, undef:i64 t518: ch = storeST4[@g_69](tbaa=<0x51f5db8)> t517, Constant:i32<3>, t400, undef:i64 t526: ch = TokenFactor t0, t520:1, t518, t391:1, t513 t50: i32,ch = AGSIMem:ST8[@g_938](tbaa=<0x51f0978) LD8@g_938(dereferenceable)> t402, TargetConstant:i64<0>, TargetConstant:i64<24>, t526 t524: i32 = TargetConstant<1> t396: i64 = SystemZISD::PCREL_WRAPPER TargetGlobalAddress:i64<i1 @​g_11> 0 t480: ch = STRLMem:ST4[@g_69](tbaa=<0x51f5db8)> Constant:i32<4>, TargetGlobalAddress:i64<i32 @​g_69> 0, <<Deleted Node!>>:ch t481: ch = TokenFactor t50:1, t480 t475: i32,ch = LRL<Mem:Volatile LD4getelementptr inbounds (%"type 0x51ed1a0", %"type 0x51ed1a0"* @​g_832, i64 0, i32 0)(dereferenceable)> TargetGlobalAddress:i64<%0* @​g_832> 0, <<Deleted Node!>>:ch t477: ch = TokenFactor t50:1, t481, t475:1 t394: ch = MVIMem:ST1[@g_11](align=4) t396, TargetConstant:i64<0>, TargetConstant:i64<1>, t477 t58: ch = J BasicBlock:ch< 0x524f328>, t394

llvmbot commented 6 years ago

Landed @ rL323977

llvmbot commented 6 years ago

This is an issue with deleting matched TokenFactors without removing all references. This is resolved by the ISel change in D41293, but there's a simple fix here that can land now: https://reviews.llvm.org/D42754

What effect does D42701 have on this?

For what I could see, it does not help my test case.

JonPsson commented 6 years ago

What effect does D42701 have on this?

For what I could see, it does not help my test case.

RKSimon commented 6 years ago

What effect does D42701 have on this?