Add threshold for lowering lattice value 'overdefined' in LVI

[Jiangning]

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.

mem_size.cc29 KBDownload

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

[hfinkel]

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]

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]

lib/Analysis/LazyValueInfo.cpp

584

Please use a preincrement.

http://llvm.org/releases/2.7/docs/CodingStandards.html#micro_preincrement

[Jiangning]

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]

Patch is updated following the feedback.

[Jiangning]

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

[hfinkel]

• Original Message -----

From: "Jiangning Liu" <[e-mail]>
To: [e-mail], [e-mail]
Cc: [e-mail], [e-mail], [e-mail]
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

lib/Analysis/LazyValueInfo.cpp

 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/ValueHandle.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetLibraryInfo.h"

 
 #define DEBUG_TYPE "lazy-value-info"
 
+// Experimentally derived threshold for the number of basic blocks lowered for
+// lattice value overdefined.
+static cl::opt<unsigned>
+OverdefinedBBThreshold("lvi-overdefined-BB-threshold",
+    cl::init(1500), cl::Hidden,
+    cl::desc("Threshold of the number of basic blocks lowered for lattice value"
+             "'overdefined'."));
+
+// Experimentally derived threshold for additional lowering lattice values
+// overdefined per block.
+static cl::opt<unsigned>
+OverdefinedThreshold("lvi-overdefined-threshold", cl::init(10), cl::Hidden,
+    cl::desc("Threshold of lowering lattice value 'overdefined'."));
+
 char LazyValueInfo::ID = 0;
 INITIALIZE_PASS_BEGIN(LazyValueInfo, "lazy-value-info",
                 "Lazy Value Information Analysis", false, true)

     const DataLayout *DL;
     /// An optional DT pointer.
     DominatorTree *DT;
+    /// A counter to record how many times Overdefined has been tried to be
+    /// lowered.
+    DenseMap<BasicBlock *, unsigned> LoweringOverdefinedTimes;
     
     friend struct LVIValueHandle;
     

 }
 
 void LazyValueInfoCache::solve() {
+  LoweringOverdefinedTimes.clear();
   while (!BlockValueStack.empty()) {
     std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
     if (solveBlockValue(e.second, e.first)) {

   // BB2. So we should have to follow data flow propagation algorithm to get the
   // value on edge BB1->BB2 propagated to BB2, and finally %v on BB2 has a
   // constant range describing a negative value.
-
-  if (!BBLV.isUndefined() && !BBLV.isOverdefined()) {
+  //
+  // In the mean time, limit the number of additional lowering lattice value to
+  // avoid unjustified memory grows.
+
+  if (LoweringOverdefinedTimes.count(BB) == 0)
+    LoweringOverdefinedTimes.insert(std::make_pair(BB, 0));
+  if ((!BBLV.isUndefined() && !BBLV.isOverdefined()) ||
+      (BBLV.isOverdefined() &&
+       (LoweringOverdefinedTimes[BB] > OverdefinedThreshold ||
+        LoweringOverdefinedTimes.size() > OverdefinedBBThreshold))) {
     DEBUG(dbgs() << "  reuse BB '" << BB->getName() << "' val=" << BBLV <<'\n');
     
     // Since we're reusing a cached value here, we don't need to update the 

   // lattice value to overdefined, so that cycles will terminate and be
   // conservatively correct.
   BBLV.markOverdefined();
+  ++LoweringOverdefinedTimes[BB];
   
   Instruction *BBI = dyn_cast<Instruction>(Val);
   if (!BBI || BBI->getParent() != BB) {