From 14e540febcdace3b650dba2b8bb0e770b90409ad Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Fri, 1 Jan 2021 16:32:19 +0100 Subject: [PATCH] [LVI] Handle unions of conditions LVI previously handled "if (L && R)" conditions, but not "if (L || R)" conditions. The latter case can still produce useful information if L and R both constrain the same variable. This adds support for handling the "if (L || R)" case as well. The only difference is that we take the union instead of the intersection of the lattice values. --- llvm/lib/Analysis/LazyValueInfo.cpp | 24 ++++++++++++++++------ .../Transforms/CorrelatedValuePropagation/basic.ll | 12 ++++------- 2 files changed, 22 insertions(+), 14 deletions(-) diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp index d95c906..ba2b6fe 100644 --- a/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/llvm/lib/Analysis/LazyValueInfo.cpp @@ -1201,13 +1201,13 @@ getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1) return getValueFromOverflowCondition(Val, WO, isTrueDest); - // Handle conditions in the form of (cond1 && cond2), we know that on the - // true dest path both of the conditions hold. Similarly for conditions of - // the form (cond1 || cond2), we know that on the false dest path neither - // condition holds. Value *L, *R; - if (isTrueDest ? !match(Cond, m_LogicalAnd(m_Value(L), m_Value(R))) - : !match(Cond, m_LogicalOr(m_Value(L), m_Value(R)))) + bool IsAnd; + if (match(Cond, m_LogicalAnd(m_Value(L), m_Value(R)))) + IsAnd = true; + else if (match(Cond, m_LogicalOr(m_Value(L), m_Value(R)))) + IsAnd = false; + else return ValueLatticeElement::getOverdefined(); // Prevent infinite recursion if Cond references itself as in this example: @@ -1217,6 +1217,18 @@ getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, 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 + // if (!(L && R)) -> union L and R + if (isTrueDest ^ IsAnd) { + ValueLatticeElement V = getValueFromCondition(Val, L, isTrueDest, Visited); + if (V.isOverdefined()) + return V; + V.mergeIn(getValueFromCondition(Val, R, isTrueDest, Visited)); + return V; + } + return intersect(getValueFromCondition(Val, L, isTrueDest, Visited), getValueFromCondition(Val, R, isTrueDest, Visited)); } diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll b/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll index f04a20b..d8ecbbf 100644 --- a/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll +++ b/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll @@ -1262,16 +1262,14 @@ define void @or_union(i32 %a, i1* %p) { ; CHECK-NEXT: [[OR:%.*]] = or i1 [[CMP1]], [[CMP2]] ; CHECK-NEXT: br i1 [[OR]], label [[GUARD:%.*]], label [[EXIT:%.*]] ; CHECK: guard: -; CHECK-NEXT: [[C1:%.*]] = icmp eq i32 [[A]], 9 -; CHECK-NEXT: store i1 [[C1]], i1* [[P:%.*]], align 1 +; CHECK-NEXT: store i1 false, i1* [[P:%.*]], align 1 ; CHECK-NEXT: [[C2:%.*]] = icmp eq i32 [[A]], 10 ; CHECK-NEXT: store i1 [[C2]], i1* [[P]], align 1 ; CHECK-NEXT: [[C3:%.*]] = icmp eq i32 [[A]], 11 ; CHECK-NEXT: store i1 [[C3]], i1* [[P]], align 1 ; CHECK-NEXT: [[C4:%.*]] = icmp eq i32 [[A]], 12 ; CHECK-NEXT: store i1 [[C4]], i1* [[P]], align 1 -; CHECK-NEXT: [[C5:%.*]] = icmp eq i32 [[A]], 13 -; CHECK-NEXT: store i1 [[C5]], i1* [[P]], align 1 +; CHECK-NEXT: store i1 false, i1* [[P]], align 1 ; CHECK-NEXT: br label [[EXIT]] ; CHECK: exit: ; CHECK-NEXT: ret void @@ -1328,16 +1326,14 @@ define void @and_union(i32 %a, i1* %p) { ; CHECK-NEXT: [[AND:%.*]] = and i1 [[CMP1]], [[CMP2]] ; CHECK-NEXT: br i1 [[AND]], label [[EXIT:%.*]], label [[GUARD:%.*]] ; CHECK: guard: -; CHECK-NEXT: [[C1:%.*]] = icmp eq i32 [[A]], 9 -; CHECK-NEXT: store i1 [[C1]], i1* [[P:%.*]], align 1 +; CHECK-NEXT: store i1 false, i1* [[P:%.*]], align 1 ; CHECK-NEXT: [[C2:%.*]] = icmp eq i32 [[A]], 10 ; CHECK-NEXT: store i1 [[C2]], i1* [[P]], align 1 ; CHECK-NEXT: [[C3:%.*]] = icmp eq i32 [[A]], 11 ; CHECK-NEXT: store i1 [[C3]], i1* [[P]], align 1 ; CHECK-NEXT: [[C4:%.*]] = icmp eq i32 [[A]], 12 ; CHECK-NEXT: store i1 [[C4]], i1* [[P]], align 1 -; CHECK-NEXT: [[C5:%.*]] = icmp eq i32 [[A]], 13 -; CHECK-NEXT: store i1 [[C5]], i1* [[P]], align 1 +; CHECK-NEXT: store i1 false, i1* [[P]], align 1 ; CHECK-NEXT: br label [[EXIT]] ; CHECK: exit: ; CHECK-NEXT: ret void -- 2.7.4