[CodeGenPrepare] Fix isIVIncrement (PR49466)

[TaWeiTu]

Summary

In the NFC commit 8d835f42a57f15c0b9053bd7c41ea95821a40e5f, the check for !L is
moved to a separate function getIVIncrement which, instead of using BO->getParent(),
uses PN->getParent(). However, these two basic blocks are not necessarily the same.

https://bugs.llvm.org/show_bug.cgi?id=49466 demonstrates a case where PN is contained in
a loop while BO is not, causing the null-pointer dereference in L->getLoopLatch().

This patch checks whether both BO and PN belong to the same loop before entering getIVIncrement.

[lebedev.ri]

Tests missing

[TaWeiTu]

• Add testcase

[TaWeiTu]

• Fix typo

[mkazantsev]

Thanks for catching this. Indeed, this fact was checked before my patch and was lost during the refactoring. LGTM with nits.

llvm/lib/CodeGen/CodeGenPrepare.cpp

1350

nit: \n not needed.

llvm/test/CodeGen/X86/pr49466.ll

2

If the test is expected to pass, it doesn't really need REQUIRES: asserts

3

| Filecheck %s + ; CHECK-LABEL: @m( if all you want to check is a no-crash.

[TaWeiTu]

• Fix nits

[TaWeiTu]

Thanks for the review!

[TaWeiTu]

• Fix test

[rupprecht]

Reverted in 8d20f2c2c66eb486ff23cc3d55a53bd840b36971. Although this fixes a crash, it also introduces a compile timeout (haven't checked if it's a true infinite loop or just _really_ slow) on other code. The reproducer is in the commit message.

[TaWeiTu]

In D98144#2623484, @rupprecht wrote:

Reverted in 8d20f2c2c66eb486ff23cc3d55a53bd840b36971. Although this fixes a crash, it also introduces a compile timeout (haven't checked if it's a true infinite loop or just _really_ slow) on other code. The reproducer is in the commit message.

Thanks for the report!
There seems to be an infinite loop here but I don't know the reason yet.
Will investigate the cause later.

[rupprecht]

Here's an IR reproducer, derived from the C++ one I provided in the reverting commit (as before, it reproduces with "clang -O2", although it doesn't with "opt -O2"):

; ModuleID = '/tmp/repro.cc'
source_filename = "/tmp/repro.cc"
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"

%class.D = type { i64 }
%class.a = type { %class.g }
%class.g = type { i32*, i32* }

$_ZNK1aIliEixEl = comdat any

$_ZNK1aIliE1jEv = comdat any

@o = dso_local local_unnamed_addr global i32 0, align 4
@p = dso_local local_unnamed_addr global i32 0, align 4
@.str = private unnamed_addr constant [1 x i8] zeroinitializer, align 1

; Function Attrs: uwtable mustprogress
define dso_local void @_ZN1D1qERK1aIliE(%class.D* nocapture nonnull dereferenceable(8) %0, %class.a* nonnull align 8 dereferenceable(16) %1) local_unnamed_addr #0 align 2 {
  %3 = call i64 @_ZNK1aIliEixEl(%class.a* nonnull dereferenceable(16) %1, i64 0) #3
  %4 = icmp eq i64 %3, 0
  br i1 %4, label %26, label %5

5:                                                ; preds = %2
  %6 = call i64 @_ZNK1aIliE1jEv(%class.a* nonnull dereferenceable(16) %1)
  %7 = icmp eq i64 %6, 0
  br i1 %7, label %26, label %8

8:                                                ; preds = %5
  %9 = getelementptr inbounds %class.D, %class.D* %0, i64 0, i32 0
  br label %10

10:                                               ; preds = %8, %18
  %11 = phi i64 [ 0, %8 ], [ %23, %18 ]
  %12 = call i64 @_ZNK1aIliEixEl(%class.a* nonnull dereferenceable(16) %1, i64 %11) #3
  %13 = icmp eq i64 %12, 0
  br i1 %13, label %18, label %14

14:                                               ; preds = %10, %14
  %15 = load i32, i32* @o, align 4, !tbaa !2
  %16 = call i32 @_Z3fn1IiiEiT_T0_PKc(i32 %15, i32 0, i8* getelementptr inbounds ([1 x i8], [1 x i8]* @.str, i64 0, i64 0))
  %17 = icmp eq i32 %16, 0
  br i1 %17, label %18, label %14, !llvm.loop !6

18:                                               ; preds = %14, %10
  %19 = call i64 @_ZNK1aIliEixEl(%class.a* nonnull dereferenceable(16) %1, i64 %11) #3
  %20 = load i32, i32* @p, align 4, !tbaa !2
  %21 = sext i32 %20 to i64
  %22 = sdiv i64 %19, %21
  store i64 %22, i64* %9, align 8, !tbaa !9
  %23 = add i64 %11, 1
  %24 = call i64 @_ZNK1aIliE1jEv(%class.a* nonnull dereferenceable(16) %1)
  %25 = icmp eq i64 %24, 0
  br i1 %25, label %26, label %10, !llvm.loop !12

26:                                               ; preds = %18, %5, %2
  ret void
}

; Function Attrs: nounwind uwtable willreturn mustprogress
define linkonce_odr dso_local i64 @_ZNK1aIliEixEl(%class.a* nonnull dereferenceable(16) %0, i64 %1) local_unnamed_addr #1 comdat align 2 {
  %3 = getelementptr inbounds %class.a, %class.a* %0, i64 0, i32 0, i32 0
  %4 = load i32*, i32** %3, align 8, !tbaa !13
  %5 = getelementptr inbounds i32, i32* %4, i64 %1
  %6 = load i32, i32* %5, align 4, !tbaa !2
  %7 = sext i32 %6 to i64
  ret i64 %7
}

; Function Attrs: nounwind uwtable willreturn mustprogress
define linkonce_odr dso_local i64 @_ZNK1aIliE1jEv(%class.a* nonnull dereferenceable(16) %0) local_unnamed_addr #1 comdat align 2 {
  %2 = getelementptr inbounds %class.a, %class.a* %0, i64 0, i32 0, i32 1
  %3 = load i32*, i32** %2, align 8, !tbaa !16
  %4 = getelementptr inbounds %class.a, %class.a* %0, i64 0, i32 0, i32 0
  %5 = load i32*, i32** %4, align 8, !tbaa !13
  %6 = ptrtoint i32* %3 to i64
  %7 = ptrtoint i32* %5 to i64
  %8 = sub i64 %6, %7
  %9 = ashr exact i64 %8, 2
  ret i64 %9
}

declare dso_local i32 @_Z3fn1IiiEiT_T0_PKc(i32, i32, i8*) local_unnamed_addr #2

attributes #0 = { uwtable mustprogress "frame-pointer"="none" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #1 = { nounwind uwtable willreturn mustprogress "frame-pointer"="none" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #2 = { "frame-pointer"="none" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
attributes #3 = { nounwind }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{!"clang version 13.0.0 (https://github.com/llvm/llvm-project.git dfd27ebbd0eb137c9a439b7c537bb87ba903efd3)"}
!2 = !{!3, !3, i64 0}
!3 = !{!"int", !4, i64 0}
!4 = !{!"omnipotent char", !5, i64 0}
!5 = !{!"Simple C++ TBAA"}
!6 = distinct !{!6, !7, !8}
!7 = !{!"llvm.loop.mustprogress"}
!8 = !{!"llvm.loop.unroll.disable"}
!9 = !{!10, !11, i64 0}
!10 = !{!"_ZTS1D", !11, i64 0}
!11 = !{!"long", !4, i64 0}
!12 = distinct !{!12, !7, !8}
!13 = !{!14, !15, i64 0}
!14 = !{!"_ZTS1g", !15, i64 0, !15, i64 8}
!15 = !{!"any pointer", !4, i64 0}
!16 = !{!14, !15, i64 8}

llvm/lib/CodeGen/CodeGenPrepare.cpp

getIVIncrement(const PHINode *PN, const LoopInfo *LI) {
   if (match(IVInc, m_ExtractValue<0>(m_Intrinsic<Intrinsic::uadd_with_overflow>(
                        m_Specific(PN), m_Constant(Step)))))
     return std::make_pair(IVInc, Step);
   return None;
 }
 
 static bool isIVIncrement(const BinaryOperator *BO, const LoopInfo *LI) {
   auto *PN = dyn_cast<PHINode>(BO->getOperand(0));
-  if (!PN)
+  if (!PN || LI->getLoopFor(BO->getParent()) != LI->getLoopFor(PN->getParent()))
     return false;
   if (auto IVInc = getIVIncrement(PN, LI))
     return IVInc->first == BO;
   return false;
 }
 
 bool CodeGenPrepare::replaceMathCmpWithIntrinsic(BinaryOperator *BO,
                                                  Value *Arg0, Value *Arg1,
                                                  CmpInst *Cmp,
                                                  Intrinsic::ID IID) {
   auto IsReplacableIVIncrement = [this, &Cmp](BinaryOperator *BO) {
     if (!isIVIncrement(BO, LI))
       return false;
     const Loop *L = LI->getLoopFor(BO->getParent());
+    assert(L && "L should not be null after isIVIncrement()");
     // IV increment may have other users than the IV. We do not want to make
     // dominance queries to analyze the legality of moving it towards the cmp,
     // so just check that there is no other users.
     if (!BO->hasOneUse())
       return false;
     // Do not risk on moving increment into a child loop.
     if (LI->getLoopFor(Cmp->getParent()) != L)
       return false;

llvm/test/CodeGen/X86/pr49466.ll

+; RUN: opt < %s -O2 -codegenprepare -S | FileCheck %s
+
+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"
+
+@b = dso_local local_unnamed_addr global i64 0, align 8
+@c = dso_local local_unnamed_addr global i64 0, align 8
+@d = dso_local local_unnamed_addr global i64 0, align 8
+@e = dso_local local_unnamed_addr global i64 0, align 8
+@f = dso_local local_unnamed_addr global i64 0, align 8
+@g = dso_local local_unnamed_addr global i64 0, align 8
+
+; CHECK-LABEL: @m(
+
+define dso_local i32 @m() local_unnamed_addr {
+entry:
+  %0 = load i64, i64* @f, align 8
+  %1 = inttoptr i64 %0 to i32*
+  %2 = load i64, i64* @c, align 8
+  %conv18 = trunc i64 %2 to i32
+  %cmp = icmp slt i32 %conv18, 3
+  %3 = load i64, i64* @d, align 8
+  %conv43 = trunc i64 %3 to i8
+  %tobool40.not = icmp eq i8 %conv43, 0
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond39.preheader, %entry
+  %j.0 = phi i32 [ undef, %entry ], [ %j.1.lcssa, %for.cond39.preheader ]
+  %p.0 = phi i64 [ undef, %entry ], [ %p.1.lcssa, %for.cond39.preheader ]
+  %i.0 = phi i32 [ undef, %entry ], [ %i.1.lcssa, %for.cond39.preheader ]
+  %cmp73 = icmp slt i32 %i.0, 3
+  br i1 %cmp73, label %for.body.preheader, label %for.cond39.preheader
+
+for.body.preheader:                               ; preds = %for.cond
+  br label %for.body
+
+for.cond1.loopexit:                               ; preds = %for.inc34.preheader, %for.end12
+  br i1 %cmp, label %for.body, label %for.cond39.preheader.loopexit
+
+for.cond39.preheader.loopexit:                    ; preds = %for.cond1.loopexit
+  br label %for.cond39.preheader
+
+for.cond39.preheader:                             ; preds = %for.cond39.preheader.loopexit, %for.cond
+  %j.1.lcssa = phi i32 [ %j.0, %for.cond ], [ %conv18, %for.cond39.preheader.loopexit ]
+  %p.1.lcssa = phi i64 [ %p.0, %for.cond ], [ 0, %for.cond39.preheader.loopexit ]
+  %i.1.lcssa = phi i32 [ %i.0, %for.cond ], [ %conv18, %for.cond39.preheader.loopexit ]
+  br i1 %tobool40.not, label %for.cond, label %for.inc42.preheader
+
+for.inc42.preheader:                              ; preds = %for.cond39.preheader
+  br label %for.inc42
+
+for.body:                                         ; preds = %for.body.preheader, %for.cond1.loopexit
+  %l.176 = phi i8 [ %sub, %for.cond1.loopexit ], [ 0, %for.body.preheader ]
+  %p.175 = phi i64 [ 0, %for.cond1.loopexit ], [ %p.0, %for.body.preheader ]
+  %j.174 = phi i32 [ %conv18, %for.cond1.loopexit ], [ %j.0, %for.body.preheader ]
+  %tobool.not = icmp eq i32 %j.174, 0
+  br i1 %tobool.not, label %cleanup45, label %for.cond2.preheader
+
+for.cond2.preheader:                              ; preds = %for.body
+  %tobool3.not69 = icmp eq i64 %p.175, 0
+  %.pr.pre = load i64, i64* @e, align 8
+  br i1 %tobool3.not69, label %for.end12, label %for.body4.preheader
+
+for.body4.preheader:                              ; preds = %for.cond2.preheader
+  %4 = sub i64 0, %p.175
+  %xtraiter = and i64 %4, 7
+  %lcmp.mod.not = icmp eq i64 %xtraiter, 0
+  br i1 %lcmp.mod.not, label %for.body4.prol.loopexit, label %for.body4.prol.preheader
+
+for.body4.prol.preheader:                         ; preds = %for.body4.preheader
+  %5 = mul nsw i64 %xtraiter, -1
+  br label %for.body4.prol
+
+for.body4.prol:                                   ; preds = %for.body4.prol.preheader, %for.body4.prol
+  %lsr.iv = phi i64 [ 0, %for.body4.prol.preheader ], [ %lsr.iv.next, %for.body4.prol ]
+  %lsr.iv.next = add nsw i64 %lsr.iv, -1
+  %prol.iter.cmp.not = icmp eq i64 %5, %lsr.iv.next
+  br i1 %prol.iter.cmp.not, label %for.body4.prol.loopexit.loopexit, label %for.body4.prol
+
+for.body4.prol.loopexit.loopexit:                 ; preds = %for.body4.prol
+  %6 = sub i64 %p.175, %lsr.iv.next
+  br label %for.body4.prol.loopexit
+
+for.body4.prol.loopexit:                          ; preds = %for.body4.prol.loopexit.loopexit, %for.body4.preheader
+  %p.270.unr = phi i64 [ %p.175, %for.body4.preheader ], [ %6, %for.body4.prol.loopexit.loopexit ]
+  %7 = icmp ugt i64 %p.175, -8
+  br i1 %7, label %for.end12, label %for.body4.preheader89
+
+for.body4.preheader89:                            ; preds = %for.body4.prol.loopexit
+  br label %for.body4
+
+for.body4:                                        ; preds = %for.body4.preheader89, %for.body4
+  %p.270 = phi i64 [ %inc11.7, %for.body4 ], [ %p.270.unr, %for.body4.preheader89 ]
+  %inc11.7 = add i64 %p.270, 8
+  %tobool3.not.7 = icmp eq i64 %inc11.7, 0
+  br i1 %tobool3.not.7, label %for.end12.loopexit, label %for.body4
+
+for.end12.loopexit:                               ; preds = %for.body4
+  br label %for.end12
+
+for.end12:                                        ; preds = %for.end12.loopexit, %for.body4.prol.loopexit, %for.cond2.preheader
+  %8 = load i32, i32* %1, align 4
+  %conv23 = zext i32 %8 to i64
+  %9 = load i64, i64* @b, align 8
+  %div24 = udiv i64 %9, %conv23
+  store i64 %div24, i64* @b, align 8
+  %sub = add i8 %l.176, -1
+  %tobool32.not72 = icmp eq i64 %.pr.pre, 0
+  br i1 %tobool32.not72, label %for.cond1.loopexit, label %for.inc34.preheader
+
+for.inc34.preheader:                              ; preds = %for.end12
+  store i64 0, i64* @e, align 8
+  br label %for.cond1.loopexit
+
+for.inc42:                                        ; preds = %for.inc42.preheader, %for.inc42
+  br label %for.inc42
+
+cleanup45:                                        ; preds = %for.body
+  %cmp13 = icmp ne i8 %l.176, 0
+  %conv16 = zext i1 %cmp13 to i32
+  ret i32 %conv16
+}