Instcombine enters an infinite loop when optimizing IR

[llvmbot]

Bugzilla Link	45539
Resolution	FIXED
Resolved on	Jun 23, 2020 22:36
Version	trunk
OS	Linux
Blocks	#44654
Attachments	IR reduction
Reporter	LLVM Bugzilla Contributor
CC	@LebedevRI,@nikic,@rotateright,@tstellar
Fixed by commit(s)	01bcc3e be4501f

Extended Description

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

[llvmbot]

assigned to @majnemer

[LebedevRI]

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}

[LebedevRI]

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]

Problematic transform:

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Lines 1763 to 1765 in 994543a

	// 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));

// 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]

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

[rotateright]

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.

[rotateright]

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.

[tstellar]

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?

[tstellar]

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.

[rotateright]

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

[rotateright]

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.

[tstellar]

Merged: be4501f