search

llvm / llvm-project

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

Instcombine enters an infinite loop when optimizing IR #44884

Closed llvmbot closed 4 years ago

llvmbot commented 4 years ago
Bugzilla Link 45539
Resolution FIXED
Resolved on Jun 23, 2020 22:36
Version trunk
OS Linux
Blocks llvm/llvm-project#44654
Attachments IR reduction
Reporter LLVM Bugzilla Contributor
CC @LebedevRI,@nikic,@rotateright,@tstellar
Fixed by commit(s) 01bcc3e93714 be4501f6e48

Extended Description

The core LLVM transformation libraries enter an infinite loop in the instcombine pass while optimizing this IR in -O2 or above.

tstellar commented 4 years ago

Merged: be4501f6e48

rotateright commented 4 years ago

Sanjay, this does not cherry-pick cleanly on the release/10.x branch. Could you either attach a patch or create a pull request against my personal fork: tstellar/llvm-project release/10.x.

I'm still fumbling around with git/github - please see attachment and let me know if that works for you.

rotateright commented 4 years ago

release 10.x patch The regression test part of the patch needed an edit to apply cleanly to the branch version of the file.

tstellar commented 4 years ago

Sanjay, this does not cherry-pick cleanly on the release/10.x branch. Could you either attach a patch or create a pull request against my personal fork: tstellar/llvm-project release/10.x.

tstellar commented 4 years ago

Constant expressions again...there have been messages on llvm-dev recently suggesting that those were a mistake.

To get this bug off the queue and not add risk to D68408, I pushed the usual 1-line fix here with a further reduced test: https://reviews.llvm.org/rG01bcc3e93714

David, is this OK to backport?

rotateright commented 4 years ago

Based on: https://godbolt.org/z/cKUN9i This started failing sometime between the 8.0 and 9.0 releases, but the fix should likely be included in 10.0.1, so reopening and blocking bug 45309.

rotateright commented 4 years ago

Constant expressions again...there have been messages on llvm-dev recently suggesting that those were a mistake.

To get this bug off the queue and not add risk to D68408, I pushed the usual 1-line fix here with a further reduced test: https://reviews.llvm.org/rG01bcc3e93714

There's another transform just below the changed code that seems like it could hit the same problem...but I didn't see a conflicting transform on that one at first glance, so didn't change it yet.

LebedevRI commented 4 years ago

Incidentally, https://reviews.llvm.org/D68408 solves the hang.

LebedevRI commented 4 years ago

Problematic transform: https://github.com/llvm/llvm-project/blob/994543abc9bf7bbb94a2deea31323031fb9ff58d/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp#L1763-L1765

// C-(C2-X) --> X+(C-C2)
if (match(Op1, m_Sub(m_Constant(C2), m_Value(X))))
  return BinaryOperator::CreateAdd(X, ConstantExpr::getSub(C, C2));

We fail to constant-fold since C2 here is a constantexpr, then canonicalizeAbsNabs() runs and undoes this transform, and here we go again.

LebedevRI commented 4 years ago

Trimmed a bit more:

%0 = type { [8 x %1], [8 x i32] } %1 = type { %2, i1 } %2 = type { i8*, i64 }

define i64 @​dynarec.emitter.Call(i64 %arg) { bb: %tmp = sub i64 ptrtoint (void (%0) @​func_with_addr to i64), %arg %tmp1 = icmp slt i64 %tmp, 0 %tmp2 = sub nsw i64 0, %tmp %tmp3 = select i1 %tmp1, i64 %tmp2, i64 %tmp ret i64 %tmp3 }

declare hidden void @​func_with_addr(%0*)

https://reviews.llvm.org/D68408#1978925 may have jinxed it, we've clearly got a new abs infinite loop ^^

IC: Visiting: %0 = sub i64 0, %tmp IC: Old = %0 = sub i64 0, %tmp New = = add i64 %arg, sub (i64 0, i64 ptrtoint (void (%"type 0x1d8f360") @​func_with_addr to i64)) IC: ADD: %0 = add i64 %arg, sub (i64 0, i64 ptrtoint (void (%0) @​func_with_addr to i64)) IC: ERASE %1 = sub i64 0, %tmp IC: ADD DEFERRED: %tmp = sub i64 ptrtoint (void (%0) @​func_with_addr to i64), %arg IC: ADD: %tmp = sub i64 ptrtoint (void (%0) @​func_with_addr to i64), %arg IC: Visiting: %tmp = sub i64 ptrtoint (void (%0) @​func_with_addr to i64), %arg IC: Visiting: %0 = add i64 %arg, sub (i64 0, i64 ptrtoint (void (%0) @​func_with_addr to i64)) IC: Old = %0 = add i64 %arg, sub (i64 0, i64 ptrtoint (void (%0) @​func_with_addr to i64)) New = = sub i64 %arg, ptrtoint (void (%"type 0x1d8f360") @​func_with_addr to i64) IC: ADD: %0 = sub i64 %arg, ptrtoint (void (%0) @​func_with_addr to i64) IC: ERASE %1 = add i64 %arg, sub (i64 0, i64 ptrtoint (void (%0) @​func_with_addr to i64)) IC: Visiting: %0 = sub i64 %arg, ptrtoint (void (%0) @​func_with_addr to i64) IC: Visiting: %tmp3 = select i1 %tmp1, i64 %0, i64 %tmp IC: ADD DEFERRED: %1 = sub i64 0, %tmp IC: ADD DEFERRED: %0 = sub i64 %arg, ptrtoint (void (%0) @​func_with_addr to i64) IC: Mod = %tmp3 = select i1 %tmp1, i64 %0, i64 %tmp New = %tmp3 = select i1 %tmp1, i64 %1, i64 %tmp IC: ADD: %tmp3 = select i1 %tmp1, i64 %1, i64 %tmp IC: ERASE %0 = sub i64 %arg, ptrtoint (void (%0) @​func_with_addr to i64) IC: ADD: %0 = sub i64 0, %tmp IC: Visiting: %0 = sub i64 0, %tmp

LebedevRI commented 4 years ago

Reduced a bit more, -instcombine is sufficient

; ModuleID = '/tmp/manual.ll' source_filename = "DynaRec" target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu"

%dynarec.emitter = type { i64, %"[]u8" } %"[]u8" = type { i8*, i64 } %dynarec.ebus = type { [8 x %"?[]align(4096) u8"], [8 x i32] } %"?[]align(4096) u8" = type { %"[]u8", i1 }

; Function Attrs: nobuiltin nounwind define hidden fastcc void @​dynarec.emitter.Call(%dynarec.emitter nocapture nonnull readonly align 8 %0) unnamed_addr #​0 { Entry: %1 = getelementptr inbounds %dynarec.emitter, %dynarec.emitter %0, i64 0, i32 0 %2 = load i64, i64 %1, align 8 %3 = sub i64 sub (i64 ptrtoint (void (%dynarec.ebus)* @​dynarec.ebus.reset to i64), i64 5), %2 %4 = icmp slt i64 %3, 0 %5 = sub nsw i64 0, %3 %spec.select = select i1 %4, i64 %5, i64 %3 %6 = icmp sgt i64 %spec.select, 4294967295 br i1 %6, label %SwitchElse, label %ErrRetContinue25

SwitchElse: ; preds = %Entry ret void

ErrRetContinue25: ; preds = %Entry call void @​llvm.trap() unreachable }

; Function Attrs: nobuiltin nounwind declare hidden void @​dynarec.ebus.reset(%dynarec.ebus* nonnull) unnamed_addr #​0

; Function Attrs: cold noreturn nounwind declare void @​llvm.trap() #​1

attributes #​0 = { nobuiltin nounwind } attributes #​1 = { cold noreturn nounwind }

!llvm.module.flags = !{#0, !​1}

!​0 = !{i32 2, !"Debug Info Version", i32 3} !​1 = !{i32 2, !"Dwarf Version", i32 4}

llvmbot commented 4 years ago

assigned to @majnemer