Skip to content

Commit c11c1ed

Browse files
igor-laevskyigor-laevsky
committedFeb 14, 2017
[SCEV] Cache results during GetMinTrailingZeros query
Differential Revision: https://reviews.llvm.org/D29759 llvm-svn: 295060
1 parent 5b281d9 commit c11c1ed

File tree

3 files changed

+91
-8
lines changed

3 files changed

+91
-8
lines changed
 

‎llvm/include/llvm/Analysis/ScalarEvolution.h

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -543,6 +543,12 @@ class ScalarEvolution {
543543
/// predicate by splitting it into a set of independent predicates.
544544
bool ProvingSplitPredicate;
545545

546+
/// Memoized values for the GetMinTrailingZeros
547+
DenseMap<const SCEV *, uint32_t> MinTrailingZerosCache;
548+
549+
/// Private helper method for the GetMinTrailingZeros method
550+
uint32_t GetMinTrailingZerosImpl(const SCEV *S);
551+
546552
/// Information about the number of loop iterations for which a loop exit's
547553
/// branch condition evaluates to the not-taken path. This is a temporary
548554
/// pair of exact and max expressions that are eventually summarized in

‎llvm/lib/Analysis/ScalarEvolution.cpp

Lines changed: 22 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -4437,8 +4437,7 @@ const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) {
44374437
return getGEPExpr(GEP, IndexExprs);
44384438
}
44394439

4440-
uint32_t
4441-
ScalarEvolution::GetMinTrailingZeros(const SCEV *S) {
4440+
uint32_t ScalarEvolution::GetMinTrailingZerosImpl(const SCEV *S) {
44424441
if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
44434442
return C->getAPInt().countTrailingZeros();
44444443

@@ -4448,14 +4447,16 @@ ScalarEvolution::GetMinTrailingZeros(const SCEV *S) {
44484447

44494448
if (const SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) {
44504449
uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
4451-
return OpRes == getTypeSizeInBits(E->getOperand()->getType()) ?
4452-
getTypeSizeInBits(E->getType()) : OpRes;
4450+
return OpRes == getTypeSizeInBits(E->getOperand()->getType())
4451+
? getTypeSizeInBits(E->getType())
4452+
: OpRes;
44534453
}
44544454

44554455
if (const SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) {
44564456
uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
4457-
return OpRes == getTypeSizeInBits(E->getOperand()->getType()) ?
4458-
getTypeSizeInBits(E->getType()) : OpRes;
4457+
return OpRes == getTypeSizeInBits(E->getOperand()->getType())
4458+
? getTypeSizeInBits(E->getType())
4459+
: OpRes;
44594460
}
44604461

44614462
if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
@@ -4472,8 +4473,8 @@ ScalarEvolution::GetMinTrailingZeros(const SCEV *S) {
44724473
uint32_t BitWidth = getTypeSizeInBits(M->getType());
44734474
for (unsigned i = 1, e = M->getNumOperands();
44744475
SumOpRes != BitWidth && i != e; ++i)
4475-
SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)),
4476-
BitWidth);
4476+
SumOpRes =
4477+
std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)), BitWidth);
44774478
return SumOpRes;
44784479
}
44794480

@@ -4514,6 +4515,17 @@ ScalarEvolution::GetMinTrailingZeros(const SCEV *S) {
45144515
return 0;
45154516
}
45164517

4518+
uint32_t ScalarEvolution::GetMinTrailingZeros(const SCEV *S) {
4519+
auto I = MinTrailingZerosCache.find(S);
4520+
if (I != MinTrailingZerosCache.end())
4521+
return I->second;
4522+
4523+
uint32_t Result = GetMinTrailingZerosImpl(S);
4524+
auto InsertPair = MinTrailingZerosCache.insert({S, Result});
4525+
assert(InsertPair.second && "Should insert a new key");
4526+
return InsertPair.first->second;
4527+
}
4528+
45174529
/// Helper method to assign a range to V from metadata present in the IR.
45184530
static Optional<ConstantRange> GetRangeFromMetadata(Value *V) {
45194531
if (Instruction *I = dyn_cast<Instruction>(V))
@@ -9510,6 +9522,7 @@ ScalarEvolution::ScalarEvolution(ScalarEvolution &&Arg)
95109522
ValueExprMap(std::move(Arg.ValueExprMap)),
95119523
PendingLoopPredicates(std::move(Arg.PendingLoopPredicates)),
95129524
WalkingBEDominatingConds(false), ProvingSplitPredicate(false),
9525+
MinTrailingZerosCache(std::move(Arg.MinTrailingZerosCache)),
95139526
BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)),
95149527
PredicatedBackedgeTakenCounts(
95159528
std::move(Arg.PredicatedBackedgeTakenCounts)),
@@ -9915,6 +9928,7 @@ void ScalarEvolution::forgetMemoizedResults(const SCEV *S) {
99159928
SignedRanges.erase(S);
99169929
ExprValueMap.erase(S);
99179930
HasRecMap.erase(S);
9931+
MinTrailingZerosCache.erase(S);
99189932

99199933
auto RemoveSCEVFromBackedgeMap =
99209934
[S, this](DenseMap<const Loop *, BackedgeTakenInfo> &Map) {

‎llvm/test/Analysis/ScalarEvolution/pr18606-min-zeros.ll

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
; RUN: opt -S -indvars < %s | FileCheck %s
2+
3+
; CHECK: @test
4+
; CHECK: %5 = add i32 %local_6_, %local_0_
5+
; CEHCK: %37 = mul i32 %36, %36
6+
7+
define i32 @test(i32, i32) {
8+
bci_0:
9+
br label %bci_30
10+
11+
bci_68: ; preds = %bci_45
12+
%local_6_.lcssa = phi i32 [ %local_6_, %bci_45 ]
13+
%.lcssa1.lcssa = phi i32 [ %37, %bci_45 ]
14+
%.lcssa.lcssa = phi i32 [ 34, %bci_45 ]
15+
%2 = add i32 %local_6_.lcssa, 262
16+
%3 = add i32 %2, %.lcssa1.lcssa
17+
%4 = add i32 %3, %.lcssa.lcssa
18+
ret i32 %4
19+
20+
bci_30: ; preds = %bci_45, %bci_0
21+
%local_0_ = phi i32 [ %0, %bci_0 ], [ %38, %bci_45 ]
22+
%local_6_ = phi i32 [ 2, %bci_0 ], [ %39, %bci_45 ]
23+
%5 = add i32 %local_6_, %local_0_
24+
br label %bci_45
25+
26+
bci_45: ; preds = %bci_30
27+
%6 = mul i32 %5, %5
28+
%7 = mul i32 %6, %6
29+
%8 = mul i32 %7, %7
30+
%9 = mul i32 %8, %8
31+
%10 = mul i32 %9, %9
32+
%11 = mul i32 %10, %10
33+
%12 = mul i32 %11, %11
34+
%13 = mul i32 %12, %12
35+
%14 = mul i32 %13, %13
36+
%15 = mul i32 %14, %14
37+
%16 = mul i32 %15, %15
38+
%17 = mul i32 %16, %16
39+
%18 = mul i32 %17, %17
40+
%19 = mul i32 %18, %18
41+
%20 = mul i32 %19, %19
42+
%21 = mul i32 %20, %20
43+
%22 = mul i32 %21, %21
44+
%23 = mul i32 %22, %22
45+
%24 = mul i32 %23, %23
46+
%25 = mul i32 %24, %24
47+
%26 = mul i32 %25, %25
48+
%27 = mul i32 %26, %26
49+
%28 = mul i32 %27, %27
50+
%29 = mul i32 %28, %28
51+
%30 = mul i32 %29, %29
52+
%31 = mul i32 %30, %30
53+
%32 = mul i32 %31, %31
54+
%33 = mul i32 %32, %32
55+
%34 = mul i32 %33, %33
56+
%35 = mul i32 %34, %34
57+
%36 = mul i32 %35, %35
58+
%37 = mul i32 %36, %36
59+
%38 = add i32 %37, -11
60+
%39 = add i32 %local_6_, 1
61+
%40 = icmp sgt i32 %39, 76
62+
br i1 %40, label %bci_68, label %bci_30
63+
}

0 commit comments

Comments
 (0)