From 911a541620bcc78e637589b8623d94b8f3cdafba Mon Sep 17 00:00:00 2001 From: Peilin Guo Date: Fri, 7 May 2021 16:05:50 +0800 Subject: [PATCH] [LazyValueInfo] Insert an Overdefined placeholder to prevent infinite recursion getValueFromCondition() uses a Visited set to record the intermediate value. However, it uses a postorder way to compute the value first and update the Visited set later. Thus it will be trapped into an infinite recursion if there exists IRs that use no dominated by its def as in this example: %tmp3 = or i1 undef, %tmp4 %tmp4 = or i1 undef, %tmp3 To prevent this, we can insert an Overdefined placeholder into the set before computing the actual value. Reviewed by: nikic Differential Revision: https://reviews.llvm.org/D101273 --- llvm/lib/Analysis/LazyValueInfo.cpp | 18 +++-- ...rt-placeholder-to-prevent-infinite-recursion.ll | 80 ++++++++++++++++++++++ 2 files changed, 88 insertions(+), 10 deletions(-) create mode 100644 llvm/test/Transforms/JumpThreading/insert-placeholder-to-prevent-infinite-recursion.ll diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp index 104f0e4..ea33214 100644 --- a/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/llvm/lib/Analysis/LazyValueInfo.cpp @@ -1175,13 +1175,6 @@ getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, else return ValueLatticeElement::getOverdefined(); - // Prevent infinite recursion if Cond references itself as in this example: - // Cond: "%tmp4 = and i1 %tmp4, undef" - // BL: "%tmp4 = and i1 %tmp4, undef" - // BR: "i1 undef" - if (L == Cond || R == Cond) - return ValueLatticeElement::getOverdefined(); - // if (L && R) -> intersect L and R // if (!(L || R)) -> intersect L and R // if (L || R) -> union L and R @@ -1201,9 +1194,14 @@ getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest, SmallDenseMap &Visited) { - auto I = Visited.find(Cond); - if (I != Visited.end()) - return I->second; + // Insert an Overdefined placeholder into the set to prevent + // infinite recursion if there exists IRs that use not + // dominated by its def as in this example: + // "%tmp3 = or i1 undef, %tmp4" + // "%tmp4 = or i1 undef, %tmp3" + auto Iter = Visited.try_emplace(Cond, ValueLatticeElement::getOverdefined()); + if (!Iter.second) + return Iter.first->getSecond(); auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited); Visited[Cond] = Result; diff --git a/llvm/test/Transforms/JumpThreading/insert-placeholder-to-prevent-infinite-recursion.ll b/llvm/test/Transforms/JumpThreading/insert-placeholder-to-prevent-infinite-recursion.ll new file mode 100644 index 0000000..23a689f --- /dev/null +++ b/llvm/test/Transforms/JumpThreading/insert-placeholder-to-prevent-infinite-recursion.ll @@ -0,0 +1,80 @@ +; RUN: opt -jump-threading -S < %s | FileCheck %s +@a = common dso_local local_unnamed_addr global i16 0, align 2 + +; Function Attrs: nofree norecurse nounwind +define internal fastcc void @s() unnamed_addr { +; CHECK-LABEL: @s( +; CHECK-NEXT: for.cond1.preheader.lr.ph: +; CHECK-NEXT: br label [[FOR_COND1_PREHEADER:%.*]] +; CHECK: for.cond1.preheader: +; CHECK-NEXT: [[DOTPR_I_19:%.*]] = phi i32 [ undef, [[FOR_COND1_PREHEADER_LR_PH:%.*]] ], [ 0, [[FOR_INC_SPLIT_1:%.*]] ] +; CHECK-NEXT: [[TMP0:%.*]] = phi i16 [ undef, [[FOR_COND1_PREHEADER_LR_PH]] ], [ [[INC9:%.*]], [[FOR_INC_SPLIT_1]] ] +; CHECK-NEXT: [[TOBOOL4_I:%.*]] = icmp eq i32 [[DOTPR_I_19]], 0 +; CHECK-NEXT: br i1 [[TOBOOL4_I]], label [[FOR_INC_SPLIT_1]], label [[FOR_BODY_LR_PH_I:%.*]] +; CHECK: for.body.lr.ph.i: +; CHECK-NEXT: ret void +; CHECK: for.cond.for.end10_crit_edge: +; CHECK-NEXT: ret void +; CHECK: for.inc.split.1: +; CHECK-NEXT: [[INC9]] = add i16 [[TMP0]], 1 +; CHECK-NEXT: [[TOBOOL:%.*]] = icmp eq i16 [[INC9]], 0 +; CHECK-NEXT: br i1 [[TOBOOL]], label [[FOR_COND_FOR_END10_CRIT_EDGE:%.*]], label [[FOR_COND1_PREHEADER]] +; +for.cond1.preheader.lr.ph: + br label %for.cond1.preheader + +for.cond1.preheader: ; preds = %for.inc.split.1, %for.cond1.preheader.lr.ph + %.pr.i.19 = phi i32 [ undef, %for.cond1.preheader.lr.ph ], [ 0, %for.inc.split.1 ] + %0 = phi i16 [ undef, %for.cond1.preheader.lr.ph ], [ %inc9, %for.inc.split.1 ] + %tobool4.i = icmp eq i32 %.pr.i.19, 0 + br i1 %tobool4.i, label %t.exit, label %for.body.lr.ph.i + +for.body.lr.ph.i: ; preds = %for.cond1.preheader + ret void + +t.exit: ; preds = %for.cond1.preheader + br label %for.inc.split + +for.inc.split: ; preds = %t.exit + %tobool4.i.1 = icmp eq i32 %.pr.i.19, 0 + br i1 %tobool4.i.1, label %for.inc.split.1, label %for.body.lr.ph.i.1 + +for.cond.for.end10_crit_edge: ; preds = %for.inc.split.1 + ret void + +for.body.lr.ph.i.1: ; preds = %for.inc.split + br label %for.body.lr.ph.split.i.1 + +for.body.lr.ph.split.i.1: ; preds = %for.body.lr.ph.i.1 + br label %for.body.preheader.i.1 + +for.body.preheader.i.1: ; preds = %for.body.lr.ph.split.i.1 + br label %for.body.i.us.1.preheader + +for.body.i.us.1.preheader: ; preds = %for.body.preheader.i.1 + br label %for.body.i.us.1 + +for.body.i.us.1: ; preds = %lor.end.i.us.1, %for.body.i.us.1.preheader + %.b.i.us.1 = phi i1 [ %spec.select44.i.us.1, %lor.end.i.us.1 ], [ undef, %for.body.i.us.1.preheader ] + br i1 %.b.i.us.1, label %lor.end.i.us.1, label %lor.rhs.i.us.1 + +lor.rhs.i.us.1: ; preds = %for.body.i.us.1 + %conv5.i.us.1 = trunc i32 undef to i8 + br label %lor.end.i.us.1 + +lor.end.i.us.1: ; preds = %lor.rhs.i.us.1, %for.body.i.us.1 + %.b31.i.us.1 = or i1 undef, %.b.i.us.1 + %spec.select44.i.us.1 = or i1 undef, %.b31.i.us.1 + br i1 undef, label %for.end18.loopexit42.i.1.loopexit, label %for.body.i.us.1 + +for.end18.loopexit42.i.1.loopexit: ; preds = %lor.end.i.us.1 + br label %for.end18.loopexit42.i.1 + +for.end18.loopexit42.i.1: ; preds = %for.end18.loopexit42.i.1.loopexit + br label %for.inc.split.1 + +for.inc.split.1: ; preds = %for.end18.loopexit42.i.1, %for.inc.split + %inc9 = add i16 %0, 1 + %tobool = icmp eq i16 %inc9, 0 + br i1 %tobool, label %for.cond.for.end10_crit_edge, label %for.cond1.preheader +} -- 2.7.4