[DebugInfo][LoopStrengthReduction] Prevent attempts to translate long SCEV expressions

[chrisjackson]

Summary

As reported in pr51656 scev-based salvaging can use excessive resources to the point of crashing when large SCEV expressions are encountered. This patch places a limit on the length of expression for which an attempt to translate will be made.

[chrisjackson]

Applied clang-format.

[StephenTozer]

In D110558#3027018, @chrisjackson wrote:

Applied clang-format.

Looks like this didn't actually apply, the revision is showing this update as having applied no changes and the formatting issues are still present.

I also suppose it would be good if we could have the expression limit put as a variable with an explanatory comment, rather than a magic number. Other than that, this change LGTM.

[chrisjackson]

Applied format.

[chrisjackson]

Added a comment explaining the choice of maximum expression size.

[StephenTozer]

Could the 64 be moved to a variable? Something similar to MaxIVUsers in the same file would be ideal - a static const variable at the top of the file with a comment explaining what it is used for.

[chrisjackson]

Moved the expresion limit to a const.

[Orlando]

Just a few nits inline. I otherwise defer to @StephenTozer's reviewing.

llvm/test/Transforms/LoopStrengthReduce/pr51656.ll

3

Is there a reason for this test to be X86 specific?

79

nit: I think the convention is to use a single ; for FileCheck directive comments.

[chrisjackson]

Updated based on @Orlando 's comments

[StephenTozer]

Two nits, other than that LGTM.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

142

llvm/test/Transforms/LoopStrengthReduce/pr51656.ll

78

Just for the sake of resiliency, it would be better to replace the metadata references here with variable matches. So essentially replace !20 with ![[VAR_E:[0-9]+]], and then insert another check directive ![[VAR_E]] = !DILocalVariable(name: "e" below.

[chrisjackson]

Updated based on final review comments.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

 /// bail out. This threshold is far beyond the number of users that LSR can
 /// conceivably solve, so it should not affect generated code, but catches the
 /// worst cases before LSR burns too much compile time and stack space.
 static const unsigned MaxIVUsers = 200;
 
 // Temporary flag to cleanup congruent phis after LSR phi expansion.
 // It's currently disabled until we can determine whether it's truly useful or
 // not. The flag should be removed after the v3.0 release.
 // This is now needed for ivchains.
 static cl::opt<bool> EnablePhiElim(
   "enable-lsr-phielim", cl::Hidden, cl::init(true),
   cl::desc("Enable LSR phi elimination"));
 
 // The flag adds instruction count to solutions cost comparision.
 static cl::opt<bool> InsnsCost(
   "lsr-insns-cost", cl::Hidden, cl::init(true),
   cl::desc("Add instruction count to a LSR cost model"));
static void RewriteDVIUsingIterCount(DVIRecoveryRec CachedDVI,
 
   LLVM_DEBUG(dbgs() << "scev-salvage: Value to salvage SCEV: "
                     << *CachedDVI.SCEV << '\n');
 
   const auto *Rec = cast<SCEVAddRecExpr>(CachedDVI.SCEV);
   if (!Rec->isAffine())
     return;
 
+  // Some SCEVs are very large and require excessive resources to translate.
+  if (CachedDVI.SCEV->getExpressionSize() > 64)
+    return;
+
   // Initialise a new builder with the iteration count expression. In
   // combination with the value's SCEV this enables recovery.
   SCEVDbgValueBuilder RecoverValue(IterationCount);
   if (!RecoverValue.SCEVToValueExpr(*Rec, SE))
     return;
 
   LLVM_DEBUG(dbgs() << "scev-salvage: Updating: " << *CachedDVI.DVI << '\n');
   RecoverValue.applyExprToDbgValue(*CachedDVI.DVI, CachedDVI.Expr);
DbgRewriteSalvageableDVIs(llvm::Loop *L, ScalarEvolution &SE,
   assert(SCEVInductionVar &&
          "Anticipated a SCEV for the post-LSR induction variable");
 
   if (const SCEVAddRecExpr *IVAddRec =
           dyn_cast<SCEVAddRecExpr>(SCEVInductionVar)) {
     if (!IVAddRec->isAffine())
       return;
 
-    // The iteratioun count is required to recover location values.
+    // Some SCEVs are very large and require excessive resources to translate.
+    if (IVAddRec->getExpressionSize() > 64)
+      return;
+
+    // The iteration count is required to recover location values.
     SCEVDbgValueBuilder IterCountExpr;
     IterCountExpr.pushValue(LSRInductionVar);
     if (!IterCountExpr.SCEVToIterCountExpr(*IVAddRec, SE))
       return;
 
     LLVM_DEBUG(dbgs() << "scev-salvage: IV SCEV: " << *SCEVInductionVar
                       << '\n');
 

llvm/test/Transforms/LoopStrengthReduce/pr51656.ll

+; RUN: opt -loop-reduce -S %s | FileCheck %s
+; REQUIRES: x86-registered-target
+
+;; This test ensures that no attempt is made to translate long SCEVs into
+;; DIExpressions. Attempting the translation can use excessive resources and
+;; result in crashes.
+
+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"
+
+@c = dso_local local_unnamed_addr global i32 0, align 4, !dbg !0
+@b = dso_local local_unnamed_addr global i32 0, align 4, !dbg !9
+@a = dso_local local_unnamed_addr global i32 0, align 4, !dbg !5
+
+define dso_local i32 @d() local_unnamed_addr #0 !dbg !16 {
+entry:
+  %b.promoted = load i32, i32* @b, align 4, !tbaa !29
+  %mul = mul nsw i32 %b.promoted, %b.promoted, !dbg !33
+  %mul.1 = mul nsw i32 %mul, %mul, !dbg !33
+  %mul.2 = mul nsw i32 %mul.1, %mul.1, !dbg !33
+  %mul.3 = mul nsw i32 %mul.2, %mul.2, !dbg !33
+  %mul.4 = mul nsw i32 %mul.3, %mul.3, !dbg !33
+  %mul.5 = mul nsw i32 %mul.4, %mul.4, !dbg !33
+  %mul.6 = mul nsw i32 %mul.5, %mul.5, !dbg !33
+  %mul.7 = mul nsw i32 %mul.6, %mul.6, !dbg !33
+  %mul.8 = mul nsw i32 %mul.7, %mul.7, !dbg !33
+  %mul.9 = mul nsw i32 %mul.8, %mul.8, !dbg !33
+  %mul.10 = mul nsw i32 %mul.9, %mul.9, !dbg !33
+  %mul.11 = mul nsw i32 %mul.10, %mul.10, !dbg !33
+  %mul.12 = mul nsw i32 %mul.11, %mul.11, !dbg !33
+  %mul.13 = mul nsw i32 %mul.12, %mul.12, !dbg !33
+  %mul.14 = mul nsw i32 %mul.13, %mul.13, !dbg !33
+  %mul.15 = mul nsw i32 %mul.14, %mul.14, !dbg !33
+  %mul.16 = mul nsw i32 %mul.15, %mul.15, !dbg !33
+  %mul.17 = mul nsw i32 %mul.16, %mul.16, !dbg !33
+  %mul.18 = mul nsw i32 %mul.17, %mul.17, !dbg !33
+  %mul.19 = mul nsw i32 %mul.18, %mul.18, !dbg !33
+  %mul.20 = mul nsw i32 %mul.19, %mul.19, !dbg !33
+  %mul.21 = mul nsw i32 %mul.20, %mul.20, !dbg !33
+  %mul.22 = mul nsw i32 %mul.21, %mul.21, !dbg !33
+  %mul.23 = mul nsw i32 %mul.22, %mul.22, !dbg !33
+  %mul.24 = mul nsw i32 %mul.23, %mul.23, !dbg !33
+  %mul.25 = mul nsw i32 %mul.24, %mul.24, !dbg !33
+  %mul.26 = mul nsw i32 %mul.25, %mul.25, !dbg !33
+  %mul.27 = mul nsw i32 %mul.26, %mul.26, !dbg !33
+  %mul.28 = mul nsw i32 %mul.27, %mul.27, !dbg !33
+  %mul.29 = mul nsw i32 %mul.28, %mul.28, !dbg !33
+  %mul.30 = mul nsw i32 %mul.29, %mul.29, !dbg !33
+  %mul.31 = mul nsw i32 %mul.30, %mul.30, !dbg !33
+  %mul.32 = mul nsw i32 %mul.31, %mul.31, !dbg !33
+  %mul.33 = mul nsw i32 %mul.32, %mul.32, !dbg !33
+  %mul.34 = mul nsw i32 %mul.33, %mul.33, !dbg !33
+  %mul.35 = mul nsw i32 %mul.34, %mul.34, !dbg !33
+  %mul.36 = mul nsw i32 %mul.35, %mul.35, !dbg !33
+  %mul.37 = mul nsw i32 %mul.36, %mul.36, !dbg !33
+  %mul.38 = mul nsw i32 %mul.37, %mul.37, !dbg !33
+  %mul.39 = mul nsw i32 %mul.38, %mul.38, !dbg !33
+  %mul.40 = mul nsw i32 %mul.39, %mul.39, !dbg !33
+  %mul.41 = mul nsw i32 %mul.40, %mul.40, !dbg !33
+  %mul.42 = mul nsw i32 %mul.41, %mul.41, !dbg !33
+  %mul.43 = mul nsw i32 %mul.42, %mul.42, !dbg !33
+  %mul.44 = mul nsw i32 %mul.43, %mul.43, !dbg !33
+  %mul.45 = mul nsw i32 %mul.44, %mul.44, !dbg !33
+  %mul.46 = mul nsw i32 %mul.45, %mul.45, !dbg !33
+  %mul.47 = mul nsw i32 %mul.46, %mul.46, !dbg !33
+  store i32 49, i32* @c, align 4, !dbg !36, !tbaa !29
+  store i32 %mul.47, i32* @b, align 4, !dbg !37, !tbaa !29
+  %.pr = load i32, i32* @a, align 4, !dbg !38, !tbaa !29
+  %tobool.not8 = icmp eq i32 %.pr, 0, !dbg !39
+  br i1 %tobool.not8, label %for.end3, label %for.body2.preheader, !dbg !39
+
+for.body2.preheader:                              ; preds = %entry
+  br label %for.body2, !dbg !39
+
+for.body2:                                        ; preds = %for.body2.preheader, %for.body2
+  %0 = phi i32 [ %sub, %for.body2 ], [ %.pr, %for.body2.preheader ]
+  %sub = sub nsw i32 %0, %mul.47, !dbg !40
+  ;; CHECK: call void @llvm.dbg.value(metadata !DIArgList(i32 undef, i32 %mul.47), metadata !20, metadata !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_minus, DW_OP_LLVM_convert, 32, DW_ATE_signed, DW_OP_LLVM_convert, 64, DW_ATE_signed, DW_OP_stack_value))
+  call void @llvm.dbg.value(metadata i32 %sub, metadata !20, metadata !DIExpression(DW_OP_LLVM_convert, 32, DW_ATE_signed, DW_OP_LLVM_convert, 64, DW_ATE_signed, DW_OP_stack_value)), !dbg !41
+  %tobool.not = icmp eq i32 %sub, 0, !dbg !39
+  br i1 %tobool.not, label %for.cond1.for.end3_crit_edge, label %for.body2, !dbg !39, !llvm.loop !42
+
+for.cond1.for.end3_crit_edge:                     ; preds = %for.body2
+  store i32 0, i32* @a, align 4, !dbg !40, !tbaa !29
+  br label %for.end3, !dbg !39
+
+for.end3:                                         ; preds = %for.cond1.for.end3_crit_edge, %entry
+  ret i32 undef, !dbg !45
+}
+
+declare void @llvm.dbg.value(metadata, metadata, metadata) #1
+
+!llvm.dbg.cu = !{!2}
+!llvm.module.flags = !{!11, !12, !13, !14}
+!llvm.ident = !{!15}
+
+!0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression())
+!1 = distinct !DIGlobalVariable(name: "c", scope: !2, file: !7, line: 2, type: !8, isLocal: false, isDefinition: true)
+!2 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3, producer: "clang version 14.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, globals: !4, splitDebugInlining: false, nameTableKind: None)
+!3 = !DIFile(filename: "test.c", directory: "/test")
+!4 = !{!5, !9, !0}
+!5 = !DIGlobalVariableExpression(var: !6, expr: !DIExpression())
+!6 = distinct !DIGlobalVariable(name: "a", scope: !2, file: !7, line: 2, type: !8, isLocal: false, isDefinition: true)
+!7 = !DIFile(filename: "./test.c", directory: "/test")
+!8 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!9 = !DIGlobalVariableExpression(var: !10, expr: !DIExpression())
+!10 = distinct !DIGlobalVariable(name: "b", scope: !2, file: !7, line: 2, type: !8, isLocal: false, isDefinition: true)
+!11 = !{i32 7, !"Dwarf Version", i32 4}
+!12 = !{i32 2, !"Debug Info Version", i32 3}
+!13 = !{i32 1, !"wchar_size", i32 4}
+!14 = !{i32 7, !"uwtable", i32 1}
+!15 = !{!"clang version 14.0.0"}
+!16 = distinct !DISubprogram(name: "d", scope: !7, file: !7, line: 3, type: !17, scopeLine: 3, flags: DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !2, retainedNodes: !19)
+!17 = !DISubroutineType(types: !18)
+!18 = !{!8}
+!19 = !{!20}
+!20 = !DILocalVariable(name: "e", scope: !21, file: !7, line: 8, type: !24)
+!21 = distinct !DILexicalBlock(scope: !22, file: !7, line: 7, column: 14)
+!22 = distinct !DILexicalBlock(scope: !23, file: !7, line: 7, column: 3)
+!23 = distinct !DILexicalBlock(scope: !16, file: !7, line: 7, column: 3)
+!24 = !DIDerivedType(tag: DW_TAG_typedef, name: "uint64_t", file: !25, line: 27, baseType: !26)
+!25 = !DIFile(filename: "/usr/include/x86_64-linux-gnu/bits/stdint-uintn.h", directory: "")
+!26 = !DIDerivedType(tag: DW_TAG_typedef, name: "__uint64_t", file: !27, line: 44, baseType: !28)
+!27 = !DIFile(filename: "/usr/include/x86_64-linux-gnu/bits/types.h", directory: "")
+!28 = !DIBasicType(name: "long unsigned int", size: 64, encoding: DW_ATE_unsigned)
+!29 = !{!30, !30, i64 0}
+!30 = !{!"int", !31, i64 0}
+!31 = !{!"omnipotent char", !32, i64 0}
+!32 = !{!"Simple C/C++ TBAA"}
+!33 = !DILocation(line: 6, column: 7, scope: !34)
+!34 = distinct !DILexicalBlock(scope: !35, file: !7, line: 5, column: 3)
+!35 = distinct !DILexicalBlock(scope: !16, file: !7, line: 5, column: 3)
+!36 = !DILocation(line: 0, scope: !16)
+!37 = !DILocation(line: 0, scope: !34)
+!38 = !DILocation(line: 7, column: 10, scope: !22)
+!39 = !DILocation(line: 7, column: 3, scope: !23)
+!40 = !DILocation(line: 8, column: 20, scope: !21)
+!41 = !DILocation(line: 0, scope: !21)
+!42 = distinct !{!42, !39, !43, !44}
+!43 = !DILocation(line: 9, column: 3, scope: !23)
+!44 = !{!"llvm.loop.mustprogress"}
+!45 = !DILocation(line: 10, column: 1, scope: !16)