Page MenuHomePhabricator

Add threshold for lowering lattice value 'overdefined' in LVI
Needs ReviewPublic

Authored by Jiangning on Sep 11 2014, 8:45 PM.

Details

Reviewers
hfinkel
Summary

This patch is to fix the compile time and memory consumption regression reported by Joerg. The regression is caused by my previous commit r215343.

In that commit, lowering lattice value 'overdefined' was introduced in LazyValueInfoCache::solveBlockValue, which is to expose more optimization opportunities to jump threading, but Joerg's new test case can expose regressions for this commit.

The solution in this patch is by introducing a threshold to control the count of lowering overdefined value. I tried Joerg's case, and got the following data with different threshold value,

Threshold UserTime MaxRSS
10 13.70 974664
100 13.44 974744
1000 13.73 974768
1500 13.74 974772
2000 14.05 974760
2500 14.93 1056600
5000 18.19 1220628
10000 22.43 1875788

Based on this data, I choose 1500 as threshold. I also checked SPEC2000/INT, and got the following data,

Threshold UserTime MaxRSS
10 129.60 71508
1500 130.45 71484

Review the patch, please!

Thanks,
-Jiangning

Diff Detail

Event Timeline

Jiangning updated this revision to Diff 13611.Sep 11 2014, 8:45 PM
Jiangning retitled this revision from to Add threshold for lowering lattice value 'overdefined' in LVI.
Jiangning updated this object.
Jiangning edited the test plan for this revision. (Show Details)
Jiangning added a reviewer: hfinkel.
Jiangning set the repository for this revision to rL LLVM.
Jiangning added a subscriber: Unknown Object (MLST).
hfinkel edited edge metadata.Sep 11 2014, 10:39 PM

I'd really prefer that we keep this count per block, instead of a global count. Is that possible?

Also, please upload full-context diffs in the future (see: http://llvm.org/docs/Phabricator.html).

lib/Analysis/LazyValueInfo.cpp
368

Could you make this a DenseMap<BasicBlock *, unsigned>, and keep a count per block?

joerg added a subscriber: joerg.Sep 12 2014, 1:12 AM
joerg added inline comments.
lib/Analysis/LazyValueInfo.cpp
41

Typo. Maybe with the changes suggsted by Hal use just:

// Experimentally derived threshold for additional lowering lattice values per block

564

Maybe just:

// Limit the number of additional lowering lattice value to avoid unjustified memory grows.

mcrosier added inline comments.
lib/Analysis/LazyValueInfo.cpp
584

Hi Hal, Jeorg and Chad,

Thanks for your feedback!

-Jiangning

lib/Analysis/LazyValueInfo.cpp
41

OK.

368

OK. But for this test case, the algorithm just encounters too many basic blocks rather than too many times for a single basic block. Anyway, to avoid confusion, following your comments, I added another threshold to check the number of basic blocks, so now we have two thresholds.

564

OK.

584

OK.

Jiangning updated this revision to Diff 13690.Sep 14 2014, 8:25 PM
Jiangning edited edge metadata.

Patch is updated following the feedback.

In D5322#5, @hfinkel wrote:

I'd really prefer that we keep this count per block, instead of a global count. Is that possible?

Also, please upload full-context diffs in the future (see: http://llvm.org/docs/Phabricator.html).

Hi Hal,

Thanks for guiding me to this tool, and it is very helpful. I will try to do it if future.

Is there any GUI helping to do this rather than using the tool arcanist on command line only? I don't really want to submit rubbish to community.

Thanks,
-Jiangning

  • Original Message -----

From: "Jiangning Liu" <liujiangning1@gmail.com>
To: liujiangning1@gmail.com, hfinkel@anl.gov
Cc: mcrosier@codeaurora.org, joerg@NetBSD.org, llvm-commits@cs.uiuc.edu
Sent: Sunday, September 14, 2014 10:18:49 PM
Subject: Re: [PATCH] Add threshold for lowering lattice value 'overdefined' in LVI

Hi Hal, Jeorg and Chad,

Thanks for your feedback!

-Jiangning

================
Comment at: lib/Analysis/LazyValueInfo.cpp:41
@@ -39,1 +40,3 @@

+ This threshold is purticularly tuned with some special cases
exposing
+
regression of compile time and memory consumption.


joerg wrote:
> Typo. Maybe with the changes suggsted by Hal use just:
>
> // Experimentally derived threshold for additional lowering lattice
> values per block
OK.

================
Comment at: lib/Analysis/LazyValueInfo.cpp:360
@@ -351,1 +359,3 @@
+ /// lowered.
+ unsigned LoweringOverdefinedTimes;


hfinkel wrote:
> Could you make this a DenseMap<BasicBlock *, unsigned>, and keep a
> count per block?
OK. But for this test case, the algorithm just encounters too many
basic blocks rather than too many times for a single basic block.
Anyway, to avoid confusion, following your comments, I added another
threshold to check the number of basic blocks, so now we have two
thresholds.

Alright. Here's what I'm trying to avoid: Given a large function, optimizing code near the beginning of the function better than code at the end of the function. Maybe we should put the count inside of LVILatticeVal itself? That seems like it should be more local.

Thanks again,
Hal

================
Comment at: lib/Analysis/LazyValueInfo.cpp:556
@@ -542,1 +555,3 @@
+ complexity. Therefore, we introduce OverdefinedThreshold to
control
+
the maximum times of further lowering lattice value
'overdefined'.


joerg wrote:
> Maybe just:
>
> // Limit the number of additional lowering lattice value to avoid
> unjustified memory grows.
OK.

================
Comment at: lib/Analysis/LazyValueInfo.cpp:574
@@ -556,2 +573,3 @@

BBLV.markOverdefined();

+ LoweringOverdefinedTimes++;


mcrosier wrote:
> Please use a preincrement.
>
> http://llvm.org/releases/2.7/docs/CodingStandards.html#micro_preincrement
OK.

http://reviews.llvm.org/D5322