New user self-registration is disabled due to spam. For an account please email bugs-admin@lists.llvm.org with your e-mail address and full name.

Bug 45539 - Instcombine enters an infinite loop when optimizing IR
Summary: Instcombine enters an infinite loop when optimizing IR
Status: RESOLVED FIXED
Alias: None
Product: libraries
Classification: Unclassified
Component: Scalar Optimizations (show other bugs)
Version: trunk
Hardware: PC Linux
: P normal
Assignee: David Majnemer
URL:
Keywords:
Depends on:
Blocks: release-10.0.1
  Show dependency tree
 
Reported: 2020-04-14 13:17 PDT by Noam Preil
Modified: 2020-06-23 22:36 PDT (History)
5 users (show)

See Also:
Fixed By Commit(s): 01bcc3e93714 be4501f6e48


Attachments
IR reduction (7.27 KB, text/plain)
2020-04-14 13:17 PDT, Noam Preil
Details
release 10.x patch (1.59 KB, patch)
2020-04-16 12:40 PDT, Sanjay Patel
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Noam Preil 2020-04-14 13:17:45 PDT
Created attachment 23356 [details]
IR reduction

The core LLVM transformation libraries enter an infinite loop in the instcombine pass while optimizing this IR in -O2 or above.
Comment 1 Roman Lebedev 2020-04-14 13:30:21 PDT
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}
Comment 2 Roman Lebedev 2020-04-14 13:52:45 PDT
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 =   <badref> = 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 =   <badref> = 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
Comment 3 Roman Lebedev 2020-04-14 14:01:07 PDT
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.
Comment 4 Roman Lebedev 2020-04-14 14:05:12 PDT
Incidentally, https://reviews.llvm.org/D68408 solves the hang.
Comment 5 Sanjay Patel 2020-04-15 06:38:41 PDT
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.
Comment 6 Sanjay Patel 2020-04-15 06:48:42 PDT
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.
Comment 7 Tom Stellard 2020-04-16 10:49:56 PDT
(In reply to Sanjay Patel from comment #5)
> 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?
Comment 8 Tom Stellard 2020-04-16 11:01:39 PDT
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.
Comment 9 Sanjay Patel 2020-04-16 12:40:42 PDT
Created attachment 23378 [details]
release 10.x patch

The regression test part of the patch needed an edit to apply cleanly to the branch version of the file.
Comment 10 Sanjay Patel 2020-04-16 12:41:52 PDT
(In reply to Tom Stellard from comment #8)
> 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.
Comment 11 Tom Stellard 2020-06-23 22:36:16 PDT
Merged: be4501f6e48