From 6148a4925e2eef4a34f61c9f379bb81d61e8eac1 Mon Sep 17 00:00:00 2001 From: Hans Wennborg Date: Tue, 30 Jan 2018 09:48:42 +0000 Subject: [PATCH] Merging r323331: ------------------------------------------------------------------------ r323331 | spatel | 2018-01-24 16:20:37 +0100 (Wed, 24 Jan 2018) | 21 lines [ValueTracking] add recursion depth param to matchSelectPattern We're getting bug reports: https://bugs.llvm.org/show_bug.cgi?id=35807 https://bugs.llvm.org/show_bug.cgi?id=35840 https://bugs.llvm.org/show_bug.cgi?id=36045 ...where we blow up the stack in value tracking because other passes are sending in selects that have an operand that is itself the select. We don't currently have a reliable way to avoid analyzing dead code that may take non-standard forms, so bail out when things go too far. This mimics the recursion depth limitations in other parts of value tracking. Unfortunately, this pushes the underlying problems for other passes (jump-threading, simplifycfg, correlated-propagation) into hiding. If someone wants to uncover those again, the first draft of this patch on Phab would do that (it would assert rather than bail out). Differential Revision: https://reviews.llvm.org/D42442 ------------------------------------------------------------------------ git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_60@323737 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/ValueTracking.h | 3 +- lib/Analysis/ValueTracking.cpp | 29 +++++++----- test/Analysis/ValueTracking/select-pattern.ll | 46 +++++++++++++++++++ 3 files changed, 66 insertions(+), 12 deletions(-) create mode 100644 test/Analysis/ValueTracking/select-pattern.ll diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h index 1c51523b157..1fdb3cff537 100644 --- a/include/llvm/Analysis/ValueTracking.h +++ b/include/llvm/Analysis/ValueTracking.h @@ -508,7 +508,8 @@ class Value; /// -> LHS = %a, RHS = i32 4, *CastOp = Instruction::SExt /// SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, - Instruction::CastOps *CastOp = nullptr); + Instruction::CastOps *CastOp = nullptr, + unsigned Depth = 0); inline SelectPatternResult matchSelectPattern(const Value *V, const Value *&LHS, const Value *&RHS, Instruction::CastOps *CastOp = nullptr) { diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp index a0032f99ec2..b799f5144bc 100644 --- a/lib/Analysis/ValueTracking.cpp +++ b/lib/Analysis/ValueTracking.cpp @@ -4165,17 +4165,18 @@ static SelectPatternResult matchClamp(CmpInst::Predicate Pred, /// a < c ? min(a,b) : min(b,c) ==> min(min(a,b),min(b,c)) static SelectPatternResult matchMinMaxOfMinMax(CmpInst::Predicate Pred, Value *CmpLHS, Value *CmpRHS, - Value *TrueVal, Value *FalseVal) { + Value *TVal, Value *FVal, + unsigned Depth) { // TODO: Allow FP min/max with nnan/nsz. assert(CmpInst::isIntPredicate(Pred) && "Expected integer comparison"); Value *A, *B; - SelectPatternResult L = matchSelectPattern(TrueVal, A, B); + SelectPatternResult L = matchSelectPattern(TVal, A, B, nullptr, Depth + 1); if (!SelectPatternResult::isMinOrMax(L.Flavor)) return {SPF_UNKNOWN, SPNB_NA, false}; Value *C, *D; - SelectPatternResult R = matchSelectPattern(FalseVal, C, D); + SelectPatternResult R = matchSelectPattern(FVal, C, D, nullptr, Depth + 1); if (L.Flavor != R.Flavor) return {SPF_UNKNOWN, SPNB_NA, false}; @@ -4240,7 +4241,8 @@ static SelectPatternResult matchMinMaxOfMinMax(CmpInst::Predicate Pred, static SelectPatternResult matchMinMax(CmpInst::Predicate Pred, Value *CmpLHS, Value *CmpRHS, Value *TrueVal, Value *FalseVal, - Value *&LHS, Value *&RHS) { + Value *&LHS, Value *&RHS, + unsigned Depth) { // Assume success. If there's no match, callers should not use these anyway. LHS = TrueVal; RHS = FalseVal; @@ -4249,7 +4251,7 @@ static SelectPatternResult matchMinMax(CmpInst::Predicate Pred, if (SPR.Flavor != SelectPatternFlavor::SPF_UNKNOWN) return SPR; - SPR = matchMinMaxOfMinMax(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal); + SPR = matchMinMaxOfMinMax(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal, Depth); if (SPR.Flavor != SelectPatternFlavor::SPF_UNKNOWN) return SPR; @@ -4313,7 +4315,8 @@ static SelectPatternResult matchSelectPattern(CmpInst::Predicate Pred, FastMathFlags FMF, Value *CmpLHS, Value *CmpRHS, Value *TrueVal, Value *FalseVal, - Value *&LHS, Value *&RHS) { + Value *&LHS, Value *&RHS, + unsigned Depth) { LHS = CmpLHS; RHS = CmpRHS; @@ -4429,7 +4432,7 @@ static SelectPatternResult matchSelectPattern(CmpInst::Predicate Pred, } if (CmpInst::isIntPredicate(Pred)) - return matchMinMax(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal, LHS, RHS); + return matchMinMax(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal, LHS, RHS, Depth); // According to (IEEE 754-2008 5.3.1), minNum(0.0, -0.0) and similar // may return either -0.0 or 0.0, so fcmp/select pair has stricter @@ -4550,7 +4553,11 @@ static Value *lookThroughCast(CmpInst *CmpI, Value *V1, Value *V2, } SelectPatternResult llvm::matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, - Instruction::CastOps *CastOp) { + Instruction::CastOps *CastOp, + unsigned Depth) { + if (Depth >= MaxDepth) + return {SPF_UNKNOWN, SPNB_NA, false}; + SelectInst *SI = dyn_cast(V); if (!SI) return {SPF_UNKNOWN, SPNB_NA, false}; @@ -4579,7 +4586,7 @@ SelectPatternResult llvm::matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, FMF.setNoSignedZeros(); return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS, cast(TrueVal)->getOperand(0), C, - LHS, RHS); + LHS, RHS, Depth); } if (Value *C = lookThroughCast(CmpI, FalseVal, TrueVal, CastOp)) { // If this is a potential fmin/fmax with a cast to integer, then ignore @@ -4588,11 +4595,11 @@ SelectPatternResult llvm::matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, FMF.setNoSignedZeros(); return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS, C, cast(FalseVal)->getOperand(0), - LHS, RHS); + LHS, RHS, Depth); } } return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS, TrueVal, FalseVal, - LHS, RHS); + LHS, RHS, Depth); } /// Return true if "icmp Pred LHS RHS" is always true. diff --git a/test/Analysis/ValueTracking/select-pattern.ll b/test/Analysis/ValueTracking/select-pattern.ll new file mode 100644 index 00000000000..455df00ef12 --- /dev/null +++ b/test/Analysis/ValueTracking/select-pattern.ll @@ -0,0 +1,46 @@ +; RUN: opt -simplifycfg < %s -S | FileCheck %s + +; The dead code would cause a select that had itself +; as an operand to be analyzed. This would then cause +; infinite recursion and eventual crash. + +define void @PR36045(i1 %t, i32* %b) { +; CHECK-LABEL: @PR36045( +; CHECK-NEXT: entry: +; CHECK-NEXT: ret void +; +entry: + br i1 %t, label %if, label %end + +if: + br i1 %t, label %unreach, label %pre + +unreach: + unreachable + +pre: + %p = phi i32 [ 70, %if ], [ %sel, %for ] + br label %for + +for: + %cmp = icmp sgt i32 %p, 8 + %add = add i32 %p, 2 + %sel = select i1 %cmp, i32 %p, i32 %add + %cmp21 = icmp ult i32 %sel, 21 + br i1 %cmp21, label %pre, label %for.end + +for.end: + br i1 %t, label %unreach2, label %then12 + +then12: + store i32 0, i32* %b + br label %unreach2 + +unreach2: + %spec = phi i32 [ %sel, %for.end ], [ 42, %then12 ] + unreachable + +end: + ret void +} + -- 2.40.0