This is an archive of the discontinued LLVM Phabricator instance.

Differential D36512

[ValueTracking] Honour recursion limit
ClosedPublic

Authored by davide on Aug 9 2017, 5:05 AM.

Details

Reviewers
mcrosier
Commits
rG1d6f2b307aba: Merging r310481, r310492 and r310510: -----------------------------------------…
rG30e5194287a7: [ValueTracking] Honour recursion limit.
rL310634: Merging r310481, r310492 and r310510:
rL310481: [ValueTracking] Honour recursion limit.
Summary

The recently improved support for icmp in ValueTracking,

commit c6b02fa9154c7b897afe5fb746cec527fb3f8bb0
Author: Chad Rosier <mcrosier@codeaurora.org>
Date:   Thu Jul 6 20:00:25 2017 +0000

    [ValueTracking] Support icmps fed by 'and' and 'or'.

    This patch adds support for handling some forms of ands and ors in
    ValueTracking's isImpliedCondition API.

    PR33611
    https://reviews.llvm.org/D34901

exposes the fact that isImplied condition doesn't really bail out if we hit the recursion limit (and this function calls computeKnownBits which increases the depth and asserts).

This is the top of the stack, for archeologists (the frame is #13 because this is running inside rr).

#13 0x000000000215d12f in llvm::computeKnownBits (V=0x7a05fc0, Known=..., DL=...,
    Depth=7, AC=0x0, CxtI=0x0, DT=0x0, ORE=0x0) at ../lib/Analysis/ValueTracking.cpp:142
#14 0x0000000002171143 in isTruePredicate(llvm::CmpInst::Predicate, llvm::Value const*, llvm::Value const*, llvm::DataLayout const&, unsigned int)::$_9::operator()(llvm::Value const
*, llvm::Value const*, llvm::Value const*&, llvm::APInt const*&, llvm::APInt const*&) const (this=0x7ffd945de098, A=0x7a078d0, B=0x7a05c00, X=@0x7ffd945de090: 0x7a05fc0,
    CA=@0x7ffd945de088: 0x7a07888, CB=@0x7ffd945de080: 0x7a05af8)
    at ../lib/Analysis/ValueTracking.cpp:4376
#15 0x0000000002170ec0 in isTruePredicate (Pred=llvm::CmpInst::ICMP_ULE, LHS=0x7a078d0,
    RHS=0x7a05c00, DL=..., Depth=6) at ../lib/Analysis/ValueTracking.cpp:4387
#16 0x0000000002170c71 in isImpliedCondOperands (Pred=llvm::CmpInst::ICMP_ULT,
    ALHS=0x7a05c00, ARHS=0x7a05b10, BLHS=0x7a078d0, BRHS=0x7a05b10, DL=..., Depth=6)
    at ../lib/Analysis/ValueTracking.cpp:4414
#17 0x00000000021675c1 in isImpliedCondICmps (LHS=0x7a27d60, RHS=0x7a07960, DL=...,
    LHSIsTrue=true, Depth=6) at ../lib/Analysis/ValueTracking.cpp:4518
#18 0x000000000216720a in llvm::isImpliedCondition (LHS=0x7a27d60, RHS=0x7a07960,
    DL=..., LHSIsTrue=true, Depth=6) at ../lib/Analysis/ValueTracking.cpp:4581
#19 0x000000000216785a in isImpliedCondAndOr (LHS=0x7a27dd0, RHS=0x7a07960, DL=...,
    LHSIsTrue=true, Depth=5) at ../lib/Analysis/ValueTracking.cpp:4549
#20 0x0000000002167278 in llvm::isImpliedCondition (LHS=0x7a27dd0, RHS=0x7a07960,
    DL=..., LHSIsTrue=true, Depth=5) at ../lib/Analysis/ValueTracking.cpp:4589
#21 0x0000000002167798 in isImpliedCondAndOr (LHS=0x7a066b0, RHS=0x7a07960, DL=...,
    LHSIsTrue=true, Depth=4) at ../lib/Analysis/ValueTracking.cpp:4546
#22 0x0000000002167278 in llvm::isImpliedCondition (LHS=0x7a066b0, RHS=0x7a07960,

Diff Detail

Event Timeline

davide created this revision.Aug 9 2017, 5:05 AM
mcrosier accepted this revision.Aug 9 2017, 7:57 AM

One small comment, but otherwise LGTM. Thanks, Davide.

lib/Analysis/ValueTracking.cpp
4534

Is this check still necessary? I don't think it is, but of course, I'm the one who broke things in the first place.. :P

This revision is now accepted and ready to land.Aug 9 2017, 7:57 AM
davide added a comment.Aug 9 2017, 8:00 AM
In D36512#836711, @mcrosier wrote:

One small comment, but otherwise LGTM. Thanks, Davide.

Thanks for your review.

lib/Analysis/ValueTracking.cpp
4534

I don't think so. I'd replace this with an assertion on trunk, but I'll keep it for safety when doing the backport to 5.

mcrosier added inline comments.Aug 9 2017, 8:12 AM
lib/Analysis/ValueTracking.cpp
4534

SGTM!

Closed by commit rL310481: [ValueTracking] Honour recursion limit. (authored by davide). · Explain WhyAug 9 2017, 8:14 AM
This revision was automatically updated to reflect the committed changes.
alekseyshl added a subscriber: alekseyshl.Aug 9 2017, 11:22 AM

Test failed on http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap/builds/2011, please fix.

davide added a comment.Aug 9 2017, 11:45 AM
In D36512#837057, @alekseyshl wrote:

Test failed on http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap/builds/2011, please fix.

After r310492 ? Cheers.

Revision Contents

PathSize
lib/
Analysis/
4 lines
test/
Transforms/
SimplifyCFG/
116 lines

Diff 110363

lib/Analysis/ValueTracking.cpp

Show First 20 Lines • Show All 467 Lines • ▼ Show 20 Lines
const ICmpInst *RHS, const ICmpInst *RHS,
const DataLayout &DL, bool LHSIsTrue, const DataLayout &DL, bool LHSIsTrue,
unsigned Depth) { unsigned Depth) {
// The LHS must be an 'or' or an 'and' instruction. // The LHS must be an 'or' or an 'and' instruction.
assert((LHS->getOpcode() == Instruction::And || assert((LHS->getOpcode() == Instruction::And ||
LHS->getOpcode() == Instruction::Or) && LHS->getOpcode() == Instruction::Or) &&
"Expected LHS to be 'and' or 'or'."); "Expected LHS to be 'and' or 'or'.");
// The remaining tests are all recursive, so bail out if we hit the limit. // The remaining tests are all recursive, so bail out if we hit the limit.
mcrosierUnsubmitted
Not Done
ReplyInline Actions

Is this check still necessary? I don't think it is, but of course, I'm the one who broke things in the first place.. :P

mcrosier: Is this check still necessary? I don't think it is, but of course, I'm the one who broke…
davideAuthorUnsubmitted
Not Done
ReplyInline Actions

I don't think so. I'd replace this with an assertion on trunk, but I'll keep it for safety when doing the backport to 5.

davide: I don't think so. I'd replace this with an assertion on trunk, but I'll keep it for safety when…
mcrosierUnsubmitted
Not Done
ReplyInline Actions

SGTM!

mcrosier: SGTM!
if (Depth == MaxDepth) if (Depth == MaxDepth)
return None; return None;
// If the result of an 'or' is false, then we know both legs of the 'or' are // If the result of an 'or' is false, then we know both legs of the 'or' are
// false. Similarly, if the result of an 'and' is true, then we know both // false. Similarly, if the result of an 'and' is true, then we know both
// legs of the 'and' are true. // legs of the 'and' are true.
Value *ALHS, *ARHS; Value *ALHS, *ARHS;
if ((!LHSIsTrue && match(LHS, m_Or(m_Value(ALHS), m_Value(ARHS)))) || if ((!LHSIsTrue && match(LHS, m_Or(m_Value(ALHS), m_Value(ARHS)))) ||
(LHSIsTrue && match(LHS, m_And(m_Value(ALHS), m_Value(ARHS))))) { (LHSIsTrue && match(LHS, m_And(m_Value(ALHS), m_Value(ARHS))))) {
// FIXME: Make this non-recursion. // FIXME: Make this non-recursion.
if (Optional<bool> Implication = if (Optional<bool> Implication =
isImpliedCondition(ALHS, RHS, DL, LHSIsTrue, Depth + 1)) isImpliedCondition(ALHS, RHS, DL, LHSIsTrue, Depth + 1))
return Implication; return Implication;
if (Optional<bool> Implication = if (Optional<bool> Implication =
isImpliedCondition(ARHS, RHS, DL, LHSIsTrue, Depth + 1)) isImpliedCondition(ARHS, RHS, DL, LHSIsTrue, Depth + 1))
return Implication; return Implication;
return None; return None;
} }
return None; return None;
} }
Optional<bool> llvm::isImpliedCondition(const Value *LHS, const Value *RHS, Optional<bool> llvm::isImpliedCondition(const Value *LHS, const Value *RHS,
const DataLayout &DL, bool LHSIsTrue, const DataLayout &DL, bool LHSIsTrue,
unsigned Depth) { unsigned Depth) {
// Bail out when we hit the limit.
if (Depth == MaxDepth)
return None;
// A mismatch occurs when we compare a scalar cmp to a vector cmp, for // A mismatch occurs when we compare a scalar cmp to a vector cmp, for
// example. // example.
if (LHS->getType() != RHS->getType()) if (LHS->getType() != RHS->getType())
return None; return None;
Type *OpTy = LHS->getType(); Type *OpTy = LHS->getType();
assert(OpTy->isIntOrIntVectorTy(1) && "Expected integer type only!"); assert(OpTy->isIntOrIntVectorTy(1) && "Expected integer type only!");
Show All 26 Lines

test/Transforms/SimplifyCFG/pr34131.ll

  • This file was added.
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -simplifycfg %s -S | FileCheck %s
define void @patatino() {
; CHECK-LABEL: @patatino(
; CHECK-NEXT: br label [[BB1:%.*]]
; CHECK: bb1:
; CHECK-NEXT: br i1 undef, label [[BB4:%.*]], label [[BB9_CRITEDGE:%.*]]
; CHECK: bb4:
; CHECK-NEXT: [[DOTPR:%.*]] = phi i1 [ undef, [[BB4]] ], [ true, [[BB1]] ]
; CHECK-NEXT: br i1 [[DOTPR]], label [[BB4]], label [[BB6:%.*]]
; CHECK: bb6:
; CHECK-NEXT: [[TMP:%.*]] = or i64 undef, 1
; CHECK-NEXT: [[TMP8:%.*]] = icmp ult i64 [[TMP]], 0
; CHECK-NEXT: [[OR_COND:%.*]] = and i1 undef, [[TMP8]]
; CHECK-NEXT: [[TMP13:%.*]] = icmp ult i64 0, 0
; CHECK-NEXT: [[OR_COND2:%.*]] = and i1 [[OR_COND]], [[TMP13]]
; CHECK-NEXT: [[TMP15:%.*]] = icmp ult i64 undef, 0
; CHECK-NEXT: [[OR_COND3:%.*]] = and i1 [[OR_COND2]], [[TMP15]]
; CHECK-NEXT: [[TMP19:%.*]] = or i64 undef, 5
; CHECK-NEXT: [[TMP20:%.*]] = icmp ult i64 [[TMP19]], 0
; CHECK-NEXT: [[OR_COND4:%.*]] = and i1 [[OR_COND3]], [[TMP20]]
; CHECK-NEXT: [[TMP22:%.*]] = or i64 undef, 6
; CHECK-NEXT: [[TMP23:%.*]] = icmp ult i64 [[TMP22]], 0
; CHECK-NEXT: [[OR_COND5:%.*]] = and i1 [[OR_COND4]], [[TMP23]]
; CHECK-NEXT: [[TMP25:%.*]] = or i64 undef, 7
; CHECK-NEXT: [[TMP26:%.*]] = icmp ult i64 [[TMP25]], 0
; CHECK-NEXT: [[OR_COND6:%.*]] = and i1 [[OR_COND5]], [[TMP26]]
; CHECK-NEXT: [[TMP28:%.*]] = or i64 undef, 8
; CHECK-NEXT: [[TMP29:%.*]] = icmp ult i64 [[TMP28]], 0
; CHECK-NEXT: [[OR_COND7:%.*]] = and i1 [[OR_COND6]], [[TMP29]]
; CHECK-NEXT: [[OR_COND7_NOT:%.*]] = xor i1 [[OR_COND7]], true
; CHECK-NEXT: [[DOTNOT:%.*]] = xor i1 undef, true
; CHECK-NEXT: [[BRMERGE:%.*]] = or i1 [[OR_COND7_NOT]], [[DOTNOT]]
; CHECK-NEXT: [[DOTNOT8:%.*]] = xor i1 undef, true
; CHECK-NEXT: [[BRMERGE9:%.*]] = or i1 [[BRMERGE]], [[DOTNOT8]]
; CHECK-NEXT: [[DOTNOT10:%.*]] = xor i1 undef, true
; CHECK-NEXT: [[BRMERGE11:%.*]] = or i1 [[BRMERGE9]], [[DOTNOT10]]
; CHECK-NEXT: [[DOTNOT12:%.*]] = xor i1 undef, true
; CHECK-NEXT: [[BRMERGE13:%.*]] = or i1 [[BRMERGE11]], [[DOTNOT12]]
; CHECK-NEXT: [[DOTNOT14:%.*]] = xor i1 undef, true
; CHECK-NEXT: [[BRMERGE15:%.*]] = or i1 [[BRMERGE13]], [[DOTNOT14]]
; CHECK-NEXT: [[DOTNOT16:%.*]] = xor i1 undef, true
; CHECK-NEXT: [[BRMERGE17:%.*]] = or i1 [[BRMERGE15]], [[DOTNOT16]]
; CHECK-NEXT: [[DOTNOT18:%.*]] = xor i1 undef, true
; CHECK-NEXT: [[BRMERGE19:%.*]] = or i1 [[BRMERGE17]], [[DOTNOT18]]
; CHECK-NEXT: br i1 [[BRMERGE19]], label [[BB11:%.*]], label [[BB1]]
; CHECK: bb9.critedge:
; CHECK-NEXT: br label [[BB11]]
; CHECK: bb11:
; CHECK-NEXT: ret void
;
br label %bb1
bb1: ; preds = %bb36, %0
br label %bb2
bb2: ; preds = %bb3, %bb1
br i1 undef, label %bb4, label %bb3
bb3: ; preds = %bb4, %bb2
br i1 undef, label %bb2, label %bb5
bb4: ; preds = %bb2
switch i32 undef, label %bb3 [
]
bb5: ; preds = %bb3
br label %bb6
bb6: ; preds = %bb5
br i1 undef, label %bb7, label %bb9
bb7: ; preds = %bb6
%tmp = or i64 undef, 1
%tmp8 = icmp ult i64 %tmp, 0
br i1 %tmp8, label %bb12, label %bb9
bb9: ; preds = %bb35, %bb34, %bb33, %bb32, %bb31, %bb30, %bb27, %bb24, %bb21, %bb18, %bb16, %bb14, %bb12, %bb7, %bb6
br label %bb11
bb10: ; preds = %bb36
br label %bb11
bb11: ; preds = %bb10, %bb9
ret void
bb12: ; preds = %bb7
%tmp13 = icmp ult i64 0, 0
br i1 %tmp13, label %bb14, label %bb9
bb14: ; preds = %bb12
%tmp15 = icmp ult i64 undef, 0
br i1 %tmp15, label %bb16, label %bb9
bb16: ; preds = %bb14
%tmp17 = icmp ult i64 undef, 0
br i1 %tmp17, label %bb18, label %bb9
bb18: ; preds = %bb16
%tmp19 = or i64 undef, 5
%tmp20 = icmp ult i64 %tmp19, 0
br i1 %tmp20, label %bb21, label %bb9
bb21: ; preds = %bb18
%tmp22 = or i64 undef, 6
%tmp23 = icmp ult i64 %tmp22, 0
br i1 %tmp23, label %bb24, label %bb9
bb24: ; preds = %bb21
%tmp25 = or i64 undef, 7
%tmp26 = icmp ult i64 %tmp25, 0
br i1 %tmp26, label %bb27, label %bb9
bb27: ; preds = %bb24
%tmp28 = or i64 undef, 8
%tmp29 = icmp ult i64 %tmp28, 0
br i1 %tmp29, label %bb30, label %bb9
bb30: ; preds = %bb27
br i1 undef, label %bb31, label %bb9
bb31: ; preds = %bb30
br i1 undef, label %bb32, label %bb9
bb32: ; preds = %bb31
br i1 undef, label %bb33, label %bb9
bb33: ; preds = %bb32
br i1 undef, label %bb34, label %bb9
bb34: ; preds = %bb33
br i1 undef, label %bb35, label %bb9
bb35: ; preds = %bb34
br i1 undef, label %bb36, label %bb9
bb36: ; preds = %bb35
br i1 undef, label %bb1, label %bb10
}