This is an archive of the discontinued LLVM Phabricator instance.

Differential D46046

[SCEV] Do not use induction in isKnownPredicate for simplification umax
ClosedPublic

Authored by skatkov on Apr 25 2018, 1:23 AM.

Details

Reviewers
sanjoy
mkazantsev
Commits
rG7d02f059e71c: SCEV] Do not use induction in isKnownPredicate for simplification umax.
rL331949: SCEV] Do not use induction in isKnownPredicate for simplification umax.
Summary

During simplification umax we trigger isKnownPredicate twice. As a first attempt it
tries the induction. To do that it tries to get post increment of SCEV.
Re-writing the SCEV may result in simplification of umax. If the SCEV contains a lot
of umax operations this recursion becomes very slow.

The added test demonstrates the slow behavior.

To resolve this we use only simple ways to check whether the predicate is known.

Diff Detail

Event Timeline

skatkov created this revision.Apr 25 2018, 1:23 AM
Herald added a subscriber: javed.absar. · View Herald TranscriptApr 25 2018, 1:23 AM
lebedev.ri added a subscriber: lebedev.ri.Apr 25 2018, 1:26 AM
lebedev.ri added inline comments.
include/llvm/Analysis/ScalarEvolution.h
884 ↗(On Diff #143869)

s/Do not/Does not/ ?

1864 ↗(On Diff #143869)

Same

skatkov updated this revision to Diff 143870.Apr 25 2018, 2:00 AM
javed.absar added a comment.Apr 25 2018, 2:05 AM

Would removing 'isKnownViaInduction' have any impact of the number of cases 'analyzeable by scev?

lib/Analysis/ScalarEvolution.cpp
8812

Hi Serguei.

I tried to trace the split and code duplication, and I think it would probably be simpler to combine 'isKnownPredicateWithoutInduction' and 'isKnownPredicateWithoutInductionHelper' into just one function (if that's possible).

skatkov added a comment.Apr 25 2018, 2:10 AM
In D46046#1077768, @javed.absar wrote:

Would removing 'isKnownViaInduction' have any impact of the number of cases 'analyzeable by scev?

As I understand it should not.
We will not be able to simplify umax in case it could be simplified before due to usage of induction but late analysis should not in general suffer from that.

But let's wait for Sanjoy's opinion on that.

lib/Analysis/ScalarEvolution.cpp
8812

Are you ok that we will have a code duplication in isKnownPredicateWithoutInduction and isKnownPredicate?

javed.absar added inline comments.Apr 25 2018, 2:18 AM
lib/Analysis/ScalarEvolution.cpp
8812

Yes I think that would be better for readability.

skatkov updated this revision to Diff 144279.Apr 26 2018, 9:56 PM

@sanjoy , please take a look.

sanjoy added a comment.Apr 29 2018, 11:30 AM

I'm a bit worried about adding yet another IsKnownViaXXX codepath (there are already too many!). Can we be a bit smarter in isKnownPredicate so that it avoids the recursive compile time blowup? If that's not possible, can we instead push the logic in isKnownPredicateWithoutInduction into isKnownViaNonRecursiveReasoning?

mkazantsev added inline comments.May 2 2018, 7:20 PM
lib/Analysis/ScalarEvolution.cpp
8813

This can invoke isKnownPredicate and isKnownViaInduction from inside. And we will have the same problem again. I suggest invoking non-recursive reasoning check from umax/smax.

skatkov updated this revision to Diff 144980.May 2 2018, 9:42 PM

Agreed with Max. Restriction of recursion between isKnownPredicate and simplification of umax is too complex.

skatkov added a comment.May 6 2018, 6:33 PM

@sanjoy, are you ok with the last change?

sanjoy accepted this revision.May 8 2018, 9:47 PM

lgtm

test/Analysis/IVUsers/deep_recursion_in_scev.ll
9

Minor nit: this test can probably be cleaned up a bit. For instance, instead of the volatile load you can pass in %tmp as a parameter, and you can remove the addressspace qualifiers.

This revision is now accepted and ready to land.May 8 2018, 9:47 PM
Closed by commit rL331949: SCEV] Do not use induction in isKnownPredicate for simplification umax. (authored by skatkov). · Explain WhyMay 9 2018, 6:44 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
lib/
Analysis/
11 lines
test/
Analysis/
IVUsers/
182 lines

Diff 144980

lib/Analysis/ScalarEvolution.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 3,511 Lines • ▼ Show 20 Lines#endif
} }
// Okay, check to see if the same value occurs in the operand list twice. If // Okay, check to see if the same value occurs in the operand list twice. If
// so, delete one. Since we sorted the list, these values are required to // so, delete one. Since we sorted the list, these values are required to
// be adjacent. // be adjacent.
for (unsigned i = 0, e = Ops.size()-1; i != e; ++i) for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
// X umax Y umax Y --> X umax Y // X umax Y umax Y --> X umax Y
// X umax Y --> X, if X is always greater than Y // X umax Y --> X, if X is always greater than Y
if (Ops[i] == Ops[i+1] || if (Ops[i] == Ops[i + 1] || isKnownViaNonRecursiveReasoning(
isKnownPredicate(ICmpInst::ICMP_UGE, Ops[i], Ops[i+1])) { ICmpInst::ICMP_UGE, Ops[i], Ops[i + 1])) {
Ops.erase(Ops.begin()+i+1, Ops.begin()+i+2); Ops.erase(Ops.begin() + i + 1, Ops.begin() + i + 2);
--i; --e; --i; --e;
} else if (isKnownPredicate(ICmpInst::ICMP_ULE, Ops[i], Ops[i+1])) { } else if (isKnownViaNonRecursiveReasoning(ICmpInst::ICMP_ULE, Ops[i],
Ops[i + 1])) {
Ops.erase(Ops.begin()+i, Ops.begin()+i+1); Ops.erase(Ops.begin() + i, Ops.begin() + i + 1);
--i; --e; --i; --e;
} }
if (Ops.size() == 1) return Ops[0]; if (Ops.size() == 1) return Ops[0];
assert(!Ops.empty() && "Reduced umax down to nothing!"); assert(!Ops.empty() && "Reduced umax down to nothing!");
// Okay, it looks like we really DO need a umax expr. Check to see if we // Okay, it looks like we really DO need a umax expr. Check to see if we
▲ Show 20 Lines • Show All 5,269 Lines • ▼ Show 20 Linesbool ScalarEvolution::isKnownPredicate(ICmpInst::Predicate Pred,
return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS); return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
} }
bool ScalarEvolution::isKnownOnEveryIteration(ICmpInst::Predicate Pred, bool ScalarEvolution::isKnownOnEveryIteration(ICmpInst::Predicate Pred,
const SCEVAddRecExpr *LHS, const SCEVAddRecExpr *LHS,
const SCEV *RHS) { const SCEV *RHS) {
const Loop *L = LHS->getLoop(); const Loop *L = LHS->getLoop();
return isLoopEntryGuardedByCond(L, Pred, LHS->getStart(), RHS) && return isLoopEntryGuardedByCond(L, Pred, LHS->getStart(), RHS) &&
isLoopBackedgeGuardedByCond(L, Pred, LHS->getPostIncExpr(*this), RHS); isLoopBackedgeGuardedByCond(L, Pred, LHS->getPostIncExpr(*this), RHS);
javed.absarUnsubmitted
Not Done
ReplyInline Actions

Hi Serguei.

I tried to trace the split and code duplication, and I think it would probably be simpler to combine 'isKnownPredicateWithoutInduction' and 'isKnownPredicateWithoutInductionHelper' into just one function (if that's possible).

javed.absar: Hi Serguei. I tried to trace the split and code duplication, and I think it would probably be…
skatkovAuthorUnsubmitted
Not Done
ReplyInline Actions

Are you ok that we will have a code duplication in isKnownPredicateWithoutInduction and isKnownPredicate?

skatkov: Are you ok that we will have a code duplication in isKnownPredicateWithoutInduction and…
javed.absarUnsubmitted
Not Done
ReplyInline Actions

Yes I think that would be better for readability.

javed.absar: Yes I think that would be better for readability.
} }
mkazantsevUnsubmitted
Not Done
ReplyInline Actions

This can invoke isKnownPredicate and isKnownViaInduction from inside. And we will have the same problem again. I suggest invoking non-recursive reasoning check from umax/smax.

mkazantsev: This can invoke `isKnownPredicate` and `isKnownViaInduction` from inside. And we will have the…
bool ScalarEvolution::isMonotonicPredicate(const SCEVAddRecExpr *LHS, bool ScalarEvolution::isMonotonicPredicate(const SCEVAddRecExpr *LHS,
ICmpInst::Predicate Pred, ICmpInst::Predicate Pred,
bool &Increasing) { bool &Increasing) {
bool Result = isMonotonicPredicateImpl(LHS, Pred, Increasing); bool Result = isMonotonicPredicateImpl(LHS, Pred, Increasing);
#ifndef NDEBUG #ifndef NDEBUG
// Verify an invariant: inverting the predicate should turn a monotonically // Verify an invariant: inverting the predicate should turn a monotonically
▲ Show 20 Lines • Show All 3,323 Lines • Show Last 20 Lines

test/Analysis/IVUsers/deep_recursion_in_scev.ll

  • This file was added.
; RUN: opt < %s -analyze -iv-users
; This is a regression test against very slow execution...
; In bad case it should fail by timeout.
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
target triple = "x86_64-unknown-linux-gnu"
define void @quux(i8 addrspace(1)* %arg, i8 addrspace(1)* %arg1) {
bb:
%tmp = load volatile i32, i32 addrspace(256)* inttoptr (i64 104 to i32 addrspace(256)*), align 8
sanjoyUnsubmitted
Not Done
ReplyInline Actions

Minor nit: this test can probably be cleaned up a bit. For instance, instead of the volatile load you can pass in %tmp as a parameter, and you can remove the addressspace qualifiers.

sanjoy: Minor nit: this test can probably be cleaned up a bit. For instance, instead of the volatile…
%tmp2 = getelementptr inbounds i8, i8 addrspace(1)* %arg, i64 80
%tmp3 = bitcast i8 addrspace(1)* %tmp2 to i8 addrspace(1)* addrspace(1)*
%tmp4 = load i8 addrspace(1)*, i8 addrspace(1)* addrspace(1)* %tmp3, align 8
%tmp5 = getelementptr inbounds i8, i8 addrspace(1)* %tmp4, i64 8
%tmp6 = bitcast i8 addrspace(1)* %tmp5 to i8 addrspace(1)* addrspace(1)*
%tmp7 = load i8 addrspace(1)*, i8 addrspace(1)* addrspace(1)* %tmp6, align 8
%tmp8 = getelementptr inbounds i8, i8 addrspace(1)* %tmp7, i64 8
%tmp9 = bitcast i8 addrspace(1)* %tmp8 to i32 addrspace(1)*
%tmp10 = load i32, i32 addrspace(1)* %tmp9, align 8
%tmp11 = udiv i32 65, %tmp10
%tmp12 = getelementptr inbounds i8, i8 addrspace(1)* %arg, i64 80
%tmp13 = bitcast i8 addrspace(1)* %tmp12 to i8 addrspace(1)* addrspace(1)*
%tmp14 = load i8 addrspace(1)*, i8 addrspace(1)* addrspace(1)* %tmp13, align 8
%tmp15 = getelementptr inbounds i8, i8 addrspace(1)* %tmp14, i64 8
%tmp16 = bitcast i8 addrspace(1)* %tmp15 to i8 addrspace(1)* addrspace(1)*
%tmp17 = load i8 addrspace(1)*, i8 addrspace(1)* addrspace(1)* %tmp16, align 8
%tmp18 = getelementptr inbounds i8, i8 addrspace(1)* %arg1, i64 8
%tmp19 = bitcast i8 addrspace(1)* %tmp18 to i32 addrspace(1)*
%tmp20 = load i32, i32 addrspace(1)* %tmp19, align 8, !range !0
%tmp21 = getelementptr inbounds i8, i8 addrspace(1)* %tmp17, i64 8
%tmp22 = bitcast i8 addrspace(1)* %tmp21 to i32 addrspace(1)*
%tmp23 = load i32, i32 addrspace(1)* %tmp22, align 8, !range !0
%tmp24 = zext i32 %tmp23 to i64
%tmp25 = and i32 %tmp11, 7
%tmp26 = icmp ugt i32 %tmp10, 9
br i1 %tmp26, label %bb27, label %bb46
bb27: ; preds = %bb117, %bb
%tmp28 = phi i32 [ 8, %bb ], [ %tmp112, %bb117 ]
br label %bb29
bb29: ; preds = %bb40, %bb27
%tmp30 = phi i32 [ %tmp43, %bb40 ], [ %tmp28, %bb27 ]
%tmp31 = phi i32 [ %tmp41, %bb40 ], [ %tmp25, %bb27 ]
br label %bb32
bb32: ; preds = %bb37, %bb29
%tmp33 = phi i64 [ 0, %bb29 ], [ %tmp38, %bb37 ]
%tmp34 = trunc i64 %tmp33 to i32
%tmp35 = add i32 %tmp30, %tmp34
%tmp36 = icmp ult i32 %tmp35, %tmp20
br i1 %tmp36, label %bb37, label %bb56
bb37: ; preds = %bb32
%tmp38 = add nuw nsw i64 %tmp33, 1
%tmp39 = icmp ult i64 %tmp38, %tmp24
br i1 %tmp39, label %bb32, label %bb40
bb40: ; preds = %bb37
%tmp41 = add i32 %tmp31, -1
%tmp42 = trunc i64 %tmp38 to i32
%tmp43 = add i32 %tmp30, %tmp42
%tmp44 = icmp eq i32 %tmp41, 0
br i1 %tmp44, label %bb45, label %bb29
bb45: ; preds = %bb40
ret void
bb46: ; preds = %bb
%tmp47 = sub nsw i32 %tmp11, %tmp25
br label %bb48
bb48: ; preds = %bb117, %bb46
%tmp49 = phi i32 [ 8, %bb46 ], [ %tmp112, %bb117 ]
%tmp50 = phi i32 [ %tmp47, %bb46 ], [ %tmp118, %bb117 ]
br label %bb51
bb51: ; preds = %bb58, %bb48
%tmp52 = phi i64 [ 0, %bb48 ], [ %tmp59, %bb58 ]
%tmp53 = phi i32 [ %tmp49, %bb48 ], [ %tmp54, %bb58 ]
%tmp54 = add i32 %tmp53, 1
%tmp55 = icmp ult i32 %tmp53, %tmp20
br i1 %tmp55, label %bb58, label %bb56
bb56: ; preds = %bb109, %bb101, %bb93, %bb85, %bb77, %bb69, %bb61, %bb51, %bb32
unreachable
bb58: ; preds = %bb51
%tmp59 = add nuw nsw i64 %tmp52, 1
%tmp60 = icmp ult i64 %tmp59, %tmp24
br i1 %tmp60, label %bb51, label %bb61
bb61: ; preds = %bb66, %bb58
%tmp62 = phi i64 [ %tmp67, %bb66 ], [ 0, %bb58 ]
%tmp63 = phi i32 [ %tmp64, %bb66 ], [ %tmp54, %bb58 ]
%tmp64 = add i32 %tmp63, 1
%tmp65 = icmp ult i32 %tmp63, %tmp20
br i1 %tmp65, label %bb66, label %bb56
bb66: ; preds = %bb61
%tmp67 = add nuw nsw i64 %tmp62, 1
%tmp68 = icmp ult i64 %tmp67, %tmp24
br i1 %tmp68, label %bb61, label %bb69
bb69: ; preds = %bb74, %bb66
%tmp70 = phi i64 [ %tmp75, %bb74 ], [ 0, %bb66 ]
%tmp71 = phi i32 [ %tmp72, %bb74 ], [ %tmp64, %bb66 ]
%tmp72 = add i32 %tmp71, 1
%tmp73 = icmp ult i32 %tmp71, %tmp20
br i1 %tmp73, label %bb74, label %bb56
bb74: ; preds = %bb69
%tmp75 = add nuw nsw i64 %tmp70, 1
%tmp76 = icmp ult i64 %tmp75, %tmp24
br i1 %tmp76, label %bb69, label %bb77
bb77: ; preds = %bb82, %bb74
%tmp78 = phi i64 [ %tmp83, %bb82 ], [ 0, %bb74 ]
%tmp79 = phi i32 [ %tmp80, %bb82 ], [ %tmp72, %bb74 ]
%tmp80 = add i32 %tmp79, 1
%tmp81 = icmp ult i32 %tmp79, %tmp20
br i1 %tmp81, label %bb82, label %bb56
bb82: ; preds = %bb77
%tmp83 = add nuw nsw i64 %tmp78, 1
%tmp84 = icmp ult i64 %tmp83, %tmp24
br i1 %tmp84, label %bb77, label %bb85
bb85: ; preds = %bb90, %bb82
%tmp86 = phi i64 [ %tmp91, %bb90 ], [ 0, %bb82 ]
%tmp87 = phi i32 [ %tmp88, %bb90 ], [ %tmp80, %bb82 ]
%tmp88 = add i32 %tmp87, 1
%tmp89 = icmp ult i32 %tmp87, %tmp20
br i1 %tmp89, label %bb90, label %bb56
bb90: ; preds = %bb85
%tmp91 = add nuw nsw i64 %tmp86, 1
%tmp92 = icmp ult i64 %tmp91, %tmp24
br i1 %tmp92, label %bb85, label %bb93
bb93: ; preds = %bb98, %bb90
%tmp94 = phi i64 [ %tmp99, %bb98 ], [ 0, %bb90 ]
%tmp95 = phi i32 [ %tmp96, %bb98 ], [ %tmp88, %bb90 ]
%tmp96 = add i32 %tmp95, 1
%tmp97 = icmp ult i32 %tmp95, %tmp20
br i1 %tmp97, label %bb98, label %bb56
bb98: ; preds = %bb93
%tmp99 = add nuw nsw i64 %tmp94, 1
%tmp100 = icmp ult i64 %tmp99, %tmp24
br i1 %tmp100, label %bb93, label %bb101
bb101: ; preds = %bb106, %bb98
%tmp102 = phi i64 [ %tmp107, %bb106 ], [ 0, %bb98 ]
%tmp103 = phi i32 [ %tmp104, %bb106 ], [ %tmp96, %bb98 ]
%tmp104 = add i32 %tmp103, 1
%tmp105 = icmp ult i32 %tmp103, %tmp20
br i1 %tmp105, label %bb106, label %bb56
bb106: ; preds = %bb101
%tmp107 = add nuw nsw i64 %tmp102, 1
%tmp108 = icmp ult i64 %tmp107, %tmp24
br i1 %tmp108, label %bb101, label %bb109
bb109: ; preds = %bb114, %bb106
%tmp110 = phi i64 [ %tmp115, %bb114 ], [ 0, %bb106 ]
%tmp111 = phi i32 [ %tmp112, %bb114 ], [ %tmp104, %bb106 ]
%tmp112 = add i32 %tmp111, 1
%tmp113 = icmp ult i32 %tmp111, %tmp20
br i1 %tmp113, label %bb114, label %bb56
bb114: ; preds = %bb109
%tmp115 = add nuw nsw i64 %tmp110, 1
%tmp116 = icmp ult i64 %tmp115, %tmp24
br i1 %tmp116, label %bb109, label %bb117
bb117: ; preds = %bb114
%tmp118 = add i32 %tmp50, -8
%tmp119 = icmp eq i32 %tmp118, 0
br i1 %tmp119, label %bb27, label %bb48
}
!0 = !{i32 0, i32 2147483647}