[LoopUnswitch] Add block frequency analysis to recognize hot/cold regions

[• chenli]

Summary

This patch adds block frequency analysis to LoopUnswitch pass to recognize hot/cold regions. For cold regions the pass only performs trivial unswitches since they do not increase code size, and for hot regions everything works as before. This helps to minimize code growth in cold regions and be more aggressive in hot regions. Currently the default cold regions are blocks with frequencies below 20% of function entry frequency, and it can be adjusted via -loop-unswitch-cold-block-frequency flag. The entire feature is controlled via -loop-unswitch-with-block-frequency flag and it is off by default.

[• chenli]

lib/Transforms/Scalar/LoopUnswitch.cpp

502

I chose to use loop preheader's frequency for coldness comparison. This will ignore the size of the loop because it does not count backedges or iteration numbers. My reasoning is that if the loop was only entered once in the pass 1000 executions, we should be confident that it will never be entered again. Therefore, no matter how many times the loop iterates, it shouldn't affect our decision. But I could see the other way around. I am open to change it if anyone prefers the other way.

[reames]

lib/Transforms/Scalar/LoopUnswitch.cpp

78

What are your plans for testing this and getting it enabled by default?

84

Have you explored this parameter at all?

My guess would be that disabling loop unswitching should only be done for *really* cold loops. I have no evidence, but a cool loop in a really hot function seems like something we should unswitch.

436

Minor comment clarification: "function entry baseline frequency". "Loops with headers below this frequency"

502

I feel pretty strongly that making decisions based on the number of times the loop executes rather than the number of times the header executes is likely to produce negative results.

Consider:
while(true) {

if (loop invariant) {
}
if (loop invariant2) {
}
if (loop invariant3) {
}
do work();

}

Your change would completely disable unswitching in this loop which seems non-ideal.

504

Given there's already handling for OptForSize within UnswitchIfProfitable, I'd like to see the handling combined. A cleanup change to move the OptForSize check here - I think that's NFC right? - and then using that in this patch would help.

test/Transforms/LoopUnswitch/cold-loop.ll

22

This is perhaps a bad example. In this particular case, we could split the loop into two subloops without code growth. Maybe tweak your example so it's more obvious why we want to avoid unswitching this?

[davidxl]

The main problem with the patch is that the cold loop detection can have many false positives. With profile feedback, cold loops can be reliably detected but not with the method described in this patch. Without profile feedback, the cold loop filtering should probably not be turned on by default unless it is optimized for size. When the filtering is not on, we should not pay the compile time penalty of computing BFI unconditionally either. Cong has recently made it possible to compute BFI without relying on running the wrapper pass.

lib/Transforms/Scalar/LoopUnswitch.cpp

502

The hotness of the loop should be measured by the frequency of the hottest BB in the loop relative to the function entry.

With PGO, you will need to check the execution count of the hottest BB in the loop (relative to some threshold set by the program summary).

test/Transforms/LoopUnswitch/cold-loop.ll

22

Unswitching duplicates the loop, so size overhead is the loop setup code (in this case probably just a branch associated with backedge).

[• chenli]

In D11605#216478, @davidxl wrote:

The main problem with the patch is that the cold loop detection can have many false positives. With profile feedback, cold loops can be reliably detected but not with the method described in this patch.

Do you mean by using other profiles together with BFI or using BFI differently?

Without profile feedback, the cold loop filtering should probably not be turned on by default unless it is optimized for size.

Yes, you are correct. Initially I was thinking this could take cold loop's unswitch budget to hot loop and thus make hot loop unswitch more aggressively. But it turned out separate loops will have the same initial unswitch budget and not effect each other. So it will only optimize code size.

When the filtering is not on, we should not pay the compile time penalty of computing BFI unconditionally either. Cong has recently made it possible to compute BFI without relying on running the wrapper pass.

Do you mean this patch http://reviews.llvm.org/D11196 ?

lib/Transforms/Scalar/LoopUnswitch.cpp

84

I was thinking about that too. Maybe adding function hotness to its loops is a good idea, ie. lower this threshold for hot functions and increase it for cold functions.

502

I think the hottest BB should be the header, assuming its inner loops will be processed by their own unswitch passes.

504

I will have a look at this.

test/Transforms/LoopUnswitch/cold-loop.ll

22

Yes, this is not a good case. I will add some side-effect code after the first condition (so the first one is still trivial and not affected by coldness check, but unswitching the second one will grow code size).

[• chenli]

In D11605#216478, @davidxl wrote:

The main problem with the patch is that the cold loop detection can have many false positives. With profile feedback, cold loops can be reliably detected but not with the method described in this patch.

By the correct cold loop detection, do you specifically mean to check the execution count of the hottest BB in the loop?

[• chenli]

Update patch to fix the following issues:

1. Use standalone BFI without relying on the wrapper pass.
2. Use the hottest block (loop header in this case) to determine the loop's hotness.
3. Update the non-trivial condition test case to have effect of code growth.

I also plan to have a follow-up patch to introduce function_entry_count to hot/cold region detection.

[• chenli]

ping ...

[reames]

Minor comments below. Once addressed, I plan to give a LGTM unless David has further comments in the meantime.

lib/Transforms/Scalar/LoopUnswitch.cpp

77

This comment is a bit deceptive. I'd just drop it.

84

Right now, we're only limiting code size increase. Please adjust the string.

88

I think the default here should be much lower, but we can tune this in separate changes. My guess here would be something like 1/100 rather than 20/100. I also think we should have an absolute cutoff, but again, we can tune separately.

176

Add a comment which says what these are used for and that they're only used with the PGO option enabled.

test/Transforms/LoopUnswitch/cold-loop.ll

39

Please add a couple of instructions here per previous comment on test case.

[davidxl]

lib/Transforms/Scalar/LoopUnswitch.cpp

88

This is not frequency. Maybe call it 'ColdnessThreshold' or something.

89

It is the 'Coldness threshold in percent. The loop header frequency (relative to the entry frequency) is compared with the threshold to determine if non-trivial unswitching should be enabled.'

441

Note that this also triggers the check when PGO is not enabled (e.g, with static prediction).

To check if PGO is on, do:

HasProfileData = F.getEntryCount().hasValue();
if (HasProfileData) {

..

[• chenli]

lib/Transforms/Scalar/LoopUnswitch.cpp

441

Do you mean that without PGO enabled, this should never be triggered?

[davidxl]

Right. I won't trust static profile data to tell you what is cold or hot.

In fact I think the right way to determine coldness is to use the
actual profile count of the loop header to determine loop is cold or
not -- the actual exec count of a loop header can be computed by
multiplying the relative frequency with the the F.getEntryCount(). A
common threshold can be 0 or 1, which means the loop rarely executes.

David

[• chenli]

Update patch w.r.t Philip's and David's comments.

[davidxl]

Looks fine, but please wait for Phillip or another review to give you LGTM.

[reames]

LGTM

lib/Transforms/Scalar/LoopUnswitch.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Support/BranchProbability.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/Support/CommandLine.h"

 STATISTIC(TotalInsts,  "Total number of instructions analyzed");
 
 // The specific value of 100 here was chosen based only on intuition and a
 // few specific examples.
 static cl::opt<unsigned>
 Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"),
           cl::init(100), cl::Hidden);
 
+// FIXME: This is false by default due to pervasive problems with
+// exactly what block frequency models.
+// Refer bug: https://llvm.org/bugs/show_bug.cgi?id=20316
+static cl::opt<bool>
+LoopUnswitchWithBlockFrequency("loop-unswitch-with-block-frequency",
+    cl::init(false), cl::Hidden,
+    cl::desc("Enable the use of the block frequency analysis to access PGO "
+             "heuristics to minimize code growth in cold regions and be more "
+             "aggressive in hot regions."));
+
+static cl::opt<unsigned>
+ColdFrequency("loop-unswitch-cold-block-frequency", cl::init(20), cl::Hidden,
+    cl::desc("Block frequency to be considered as cold. Non-trivial "
+             "unswitches are not applied to cold blocks."));
+
 namespace {
 
   class LUAnalysisCache {
 
     typedef DenseMap<const SwitchInst*, SmallPtrSet<const Value *, 8> >
       UnswitchedValsMap;
 
     typedef UnswitchedValsMap::iterator UnswitchedValsIt;
class LoopUnswitch : public LoopPass {
     AssumptionCache *AC;
 
     // Used to check if second loop needs processing after
     // RewriteLoopBodyWithConditionConstant rewrites first loop.
     std::vector<Loop*> LoopProcessWorklist;
 
     LUAnalysisCache BranchesInfo;
 
+    BlockFrequencyInfo BFI;
+    BlockFrequency ColdEntryFreq;
+
     bool OptimizeForSize;
     bool redoLoop;
 
     Loop *currentLoop;
     DominatorTree *DT;
     BasicBlock *loopHeader;
     BasicBlock *loopPreheader;
 
bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
   if (skipOptnoneFunction(L))
     return false;
 
   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
       *L->getHeader()->getParent());
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   LPM = &LPM_Ref;
   DominatorTreeWrapperPass *DTWP =
       getAnalysisIfAvailable<DominatorTreeWrapperPass>();
   DT = DTWP ? &DTWP->getDomTree() : nullptr;
   currentLoop = L;
   Function *F = currentLoop->getHeader()->getParent();
+
+  if (LoopUnswitchWithBlockFrequency) {
+    BranchProbabilityInfo BPI(*F, *LI);
+    BFI.calculate(*L->getHeader()->getParent(), BPI, *LI);
+
+    // Use BranchProbability to compute a minimum frequency based on
+    // function entry baseline frequency. Loops with headers below this
+    // frequency are considered as cold.
+    const BranchProbability ColdProb(ColdFrequency, 100);
+    ColdEntryFreq = BlockFrequency(BFI.getEntryFreq()) * ColdProb;
+  }
+
   bool Changed = false;
   do {
     assert(currentLoop->isLCSSAForm(*DT));
     redoLoop = false;
     Changed |= processCurrentLoop();
   } while(redoLoop);
 
   if (Changed) {
bool LoopUnswitch::processCurrentLoop() {
 
   // Try trivial unswitch first before loop over other basic blocks in the loop.
   if (TryTrivialLoopUnswitch(Changed)) {
     return true;
   }
 
   // Do not do non-trivial unswitch while optimizing for size.
   // FIXME: Use Function::optForSize().
   if (OptimizeForSize ||
       loopHeader->getParent()->hasFnAttribute(Attribute::OptimizeForSize))
     return false;
 
+  if (LoopUnswitchWithBlockFrequency) {
+    // Compute the weighted frequency of the hottest block in the
+    // loop (loopHeader in this case since inner loops should be
+    // processed before outer loop). If it is less than ColdFrequency,
+    // we should not unswitch.
+    BlockFrequency LoopEntryFreq = BFI.getBlockFreq(loopHeader);
+    if (LoopEntryFreq < ColdEntryFreq)
+      return false;
+  }
+
   // Loop over all of the basic blocks in the loop.  If we find an interior
   // block that is branching on a loop-invariant condition, we can unswitch this
   // loop.
   for (Loop::block_iterator I = currentLoop->block_begin(),
          E = currentLoop->block_end(); I != E; ++I) {
     TerminatorInst *TI = (*I)->getTerminator();
     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
       // If this isn't branching on an invariant condition, we can't unswitch

test/Transforms/LoopUnswitch/cold-loop.ll

+; RUN: opt < %s -loop-unswitch -loop-unswitch-with-block-frequency -S 2>&1 | FileCheck %s
+
+; trivial condition should be unswithed regardless of coldness.
+define i32 @test1(i1 %cond1, i1 %cond2) {
+  br i1 %cond1, label %loop_begin, label %loop_exit, !prof !0
+
+loop_begin:  
+
+; CHECK: br i1 true, label %continue, label %loop_exit.loopexit
+  br i1 %cond2, label %continue, label %loop_exit  ; trivial condition
+
+continue:
+  call void @some_func1() noreturn nounwind
+  br label %loop_begin
+  
+loop_exit:
+  ret i32 0
+}
+
+; cold non-trivial condition should not be unswitched.
+define i32 @test2(i32* %var, i1 %cond1, i1 %cond2) {
+  br i1 %cond1, label %loop_begin, label %loop_exit, !prof !0
+
+loop_begin:
+  store i32 1, i32* %var
+
+; CHECK: br i1 %cond2, label %continue1, label %continue2
+  br i1 %cond2, label %continue1, label %continue2  ; non-trivial condition  
+
+continue1:
+  call void @some_func1() noreturn nounwind
+  br label %joint
+
+continue2:
+  call void @some_func2() noreturn nounwind
+  br label %joint
+
+joint:
+  br label %loop_begin
+
+loop_exit:
+  ret i32 0
+}
+
+declare void @some_func1() noreturn
+declare void @some_func2() noreturn
+
+!0 = !{!"branch_weights", i32 1, i32 100000}