Fix three bugs in loop unswitching related to trivial unswitching and the threshold parameter

[broune]

Summary

This change fixes three bugs in loop unswitching. This change causes an 81% speed-up on a benchmark that is based on EigenConvolutionKernel2D from Eigen3, where the lack of loop unswitching blocks hoisting of loads out of a nested loop (see bug 23816 for how loop unswitching and load hoisting are related).

Change 1: Unswitching on trivial conditions should always happen regardless of the computed unswitching cost, as really the cost is zero. While there is code to make that happen, the logic that checks the unswitching cost against a threshold was moved to an earlier point (revision 147935) than the point where trivial unswitching is detected, so trivial unswitching is currently blocked by the cost threshold. This change fixes that.

Change 2: Before revision 147935 (from 2012-01-11), the threshold parameter was a per-loop threshold. So an unswitching happened only if the cost of the unswitching was less than the threshold. In an indirect way (and I believe unintentionally), the logic for this since then has been that the threshold is an over-all budget across all loops for all loop unswitching done by a given LoopUnswitch loop pass object. So if an unswitching with cost 100 happens in one function, that in effect reduces the threshold from 100 to 0 for the loops even in another function. This persists for the lifetime of that loop pass object. This makes no difference for most small examples but it is important for large examples. This revision fixes that.

Change 3: The cost is currently calculated as std::min(NumInstructions, 5 * NumBlocks). So a loop with 2 blocks and a million instructions will have an unswitching cost of 10. I changed this to just NumInstructions, as it were before revision 147935, though I'm open to e.g. instead replacing std::min with std::max.

I've tried to make the change minimally invasive while staying with what I think was the original intent of the code.

[broune]

Change unswitching cost calculation from std::min(NumInstructions, 5 * NumBlocks) to NumInstructions.

[meheff]

Thanks for fixing this. This certainly seems saner than what is there now. Some clarifying comments about MaxSize might be good. Superficially it looks like some global budget because it is a pass level value and gets decremented per loop, but in reality all the budget gets returned when the pass is done with a loop and all of it's clones.

[broune]

Add comment on MaxSize.

[broune]

Friendly ping.

[meheff]

LGTM. Thanks!

[broune]

Friendly ping.

[hfinkel]

LGTM too.

[broune]

Committed as revision 240438.

lib/Transforms/Scalar/LoopUnswitch.cpp

class LUAnalysisCache {
 
     typedef DenseMap<const SwitchInst*, SmallPtrSet<const Value *, 8> >
       UnswitchedValsMap;
 
     typedef UnswitchedValsMap::iterator UnswitchedValsIt;
 
     struct LoopProperties {
       unsigned CanBeUnswitchedCount;
+      unsigned WasUnswitchedCount;
       unsigned SizeEstimation;
       UnswitchedValsMap UnswitchedVals;
     };
 
     // Here we use std::map instead of DenseMap, since we need to keep valid
     // LoopProperties pointer for current loop for better performance.
     typedef std::map<const Loop*, LoopProperties> LoopPropsMap;
     typedef LoopPropsMap::iterator LoopPropsMapIt;
 
     LoopPropsMap LoopsProperties;
     UnswitchedValsMap *CurLoopInstructions;
     LoopProperties *CurrentLoopProperties;
 
-    // Max size of code we can produce on remained iterations.
+    // A loop unswitching with an estimated cost above this threshold
+    // is not performed. MaxSize is turned into unswitching quota for
+    // the current loop, and reduced correspondingly, though note that
+    // the quota is returned by releaseMemory() when the loop has been
+    // processed, so that MaxSize will return to its previous
+    // value. So in most cases MaxSize will equal the Threshold flag
+    // when a new loop is processed. An exception to that is that
+    // MaxSize will have a smaller value while processing nested loops
+    // that were introduced due to loop unswitching of an outer loop.
+    //
+    // FIXME: The way that MaxSize works is subtle and depends on the
+    // pass manager processing loops and calling releaseMemory() in a
+    // specific order. It would be good to find a more straightforward
+    // way of doing what MaxSize does.
     unsigned MaxSize;
 
     public:
 
       LUAnalysisCache() :
         CurLoopInstructions(nullptr), CurrentLoopProperties(nullptr),
         MaxSize(Threshold)
       {}
public:
       // Mark case value as unswitched.
       // Since SI instruction can be partly unswitched, in order to avoid
       // extra unswitching in cloned loops keep track all unswitched values.
       void setUnswitched(const SwitchInst *SI, const Value *V);
 
       // Check was this case value unswitched before or not.
       bool isUnswitched(const SwitchInst *SI, const Value *V);
 
+      // Returns true if another unswitching could be done within the cost
+      // threshold.
+      bool CostAllowsUnswitching();
+
       // Clone all loop-unswitch related loop properties.
       // Redistribute unswitching quotas.
       // Note, that new loop data is stored inside the VMap.
       void cloneData(const Loop *NewLoop, const Loop *OldLoop,
                      const ValueToValueMapTy &VMap);
   };
 
   class LoopUnswitch : public LoopPass {
if (Inserted) {
     // FIXME: This is overly conservative because it does not take into
     // consideration code simplification opportunities and code that can
     // be shared by the resultant unswitched loops.
     CodeMetrics Metrics;
     for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
          I != E; ++I)
       Metrics.analyzeBasicBlock(*I, TTI, EphValues);
 
-    Props.SizeEstimation = std::min(Metrics.NumInsts, Metrics.NumBlocks * 5);
+    Props.SizeEstimation = Metrics.NumInsts;
     Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation);
+    Props.WasUnswitchedCount = 0;
     MaxSize -= Props.SizeEstimation * Props.CanBeUnswitchedCount;
 
     if (Metrics.notDuplicatable) {
       DEBUG(dbgs() << "NOT unswitching loop %"
                    << L->getHeader()->getName() << ", contents cannot be "
                    << "duplicated!\n");
       return false;
     }
   }
 
-  if (!Props.CanBeUnswitchedCount) {
-    DEBUG(dbgs() << "NOT unswitching loop %"
-                 << L->getHeader()->getName() << ", cost too high: "
-                 << L->getBlocks().size() << "\n");
-    return false;
-  }
-
   // Be careful. This links are good only before new loop addition.
   CurrentLoopProperties = &Props;
   CurLoopInstructions = &Props.UnswitchedVals;
 
   return true;
 }
 
 // Clean all data related to given loop.
 void LUAnalysisCache::forgetLoop(const Loop *L) {
 
   LoopPropsMapIt LIt = LoopsProperties.find(L);
 
   if (LIt != LoopsProperties.end()) {
     LoopProperties &Props = LIt->second;
-    MaxSize += Props.CanBeUnswitchedCount * Props.SizeEstimation;
+    MaxSize += (Props.CanBeUnswitchedCount + Props.WasUnswitchedCount)
+      * Props.SizeEstimation;
     LoopsProperties.erase(LIt);
   }
 
   CurrentLoopProperties = nullptr;
   CurLoopInstructions = nullptr;
 }
 
 // Mark case value as unswitched.
 // Since SI instruction can be partly unswitched, in order to avoid
 // extra unswitching in cloned loops keep track all unswitched values.
 void LUAnalysisCache::setUnswitched(const SwitchInst *SI, const Value *V) {
   (*CurLoopInstructions)[SI].insert(V);
 }
 
 // Check was this case value unswitched before or not.
 bool LUAnalysisCache::isUnswitched(const SwitchInst *SI, const Value *V) {
   return (*CurLoopInstructions)[SI].count(V);
 }
 
+bool LUAnalysisCache::CostAllowsUnswitching() {
+  return CurrentLoopProperties->CanBeUnswitchedCount > 0;
+}
+
 // Clone all loop-unswitch related loop properties.
 // Redistribute unswitching quotas.
 // Note, that new loop data is stored inside the VMap.
 void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop,
                                 const ValueToValueMapTy &VMap) {
 
   LoopProperties &NewLoopProps = LoopsProperties[NewLoop];
   LoopProperties &OldLoopProps = *CurrentLoopProperties;
   UnswitchedValsMap &Insts = OldLoopProps.UnswitchedVals;
 
   // Reallocate "can-be-unswitched quota"
 
   --OldLoopProps.CanBeUnswitchedCount;
+  ++OldLoopProps.WasUnswitchedCount;
+  NewLoopProps.WasUnswitchedCount = 0;
   unsigned Quota = OldLoopProps.CanBeUnswitchedCount;
   NewLoopProps.CanBeUnswitchedCount = Quota / 2;
   OldLoopProps.CanBeUnswitchedCount = Quota - Quota / 2;
 
   NewLoopProps.SizeEstimation = OldLoopProps.SizeEstimation;
 
   // Clone unswitched values info:
   // for new loop switches we clone info about values that was
bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val) {
   if (IsTrivialUnswitchCondition(LoopCond, &CondVal, &ExitBlock)) {
     // If the condition is trivial, always unswitch. There is no code growth
     // for this case.
     UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, ExitBlock);
     return true;
   }
 
   // Check to see if it would be profitable to unswitch current loop.
+  if (!BranchesInfo.CostAllowsUnswitching()) {
+    DEBUG(dbgs() << "NOT unswitching loop %"
+                 << currentLoop->getHeader()->getName()
+                 << " at non-trivial condition '"
+                 << *Val << "' == " << *LoopCond << "\n"
+                 << ". Cost too high.\n");
+    return false;
+  }
 
   // Do not do non-trivial unswitch while optimizing for size.
   if (OptimizeForSize || F->hasFnAttribute(Attribute::OptimizeForSize))
     return false;
 
   UnswitchNontrivialCondition(LoopCond, Val, currentLoop);
   return true;
 }

test/Transforms/LoopUnswitch/2015-06-10-Threshold.ll

+; RUN: opt < %s -loop-unswitch --loop-unswitch-threshold 4 \
+; RUN:   -verify-loop-info -S < %s 2>&1 -stats | FileCheck %s
+
+; Test for a bug. This tests that loop unswitching decisions in
+; different functions are independent. This was previously not the
+; case; the threshold of 4 would in effect be set to 0 after the first
+; unswitching and carried over as 0 into the next function.
+
+; CHECK-LABEL: @test1(
+define i32 @test1(i32* %var) {
+entry:
+; The loop should be unswitched on %c == true or %c == false, producing
+; two versions of the loop. The unswitch cost is 4.
+  %c = icmp eq i32 1, 2
+  br label %loop
+
+loop:
+  %i = phi i32 [0, %entry], [%nexti, %loop]
+  %incby = select i1 %c, i32 10, i32 20
+; CHECK-DAG: add i32 %i.us, 10
+; CHECK-DAG: add i32 %i, 20
+  %nexti = add i32 %i, %incby
+  %iterate = icmp eq i32 %nexti, 40
+  br i1 %iterate, label %loop, label %loop_exit
+
+; CHECK: loop_exit:
+loop_exit:
+  ret i32 0
+}
+
+; test2 is identical to test1, so the same thing should happen here as there.
+; CHECK-LABEL: @test2(
+define i32 @test2(i32* %var) {
+entry:
+  %c = icmp eq i32 1, 2
+  br label %loop
+
+loop:
+  %i = phi i32 [0, %entry], [%nexti, %loop]
+  %incby = select i1 %c, i32 10, i32 20
+; CHECK-DAG: add i32 %i.us, 10
+; CHECK-DAG: add i32 %i, 20
+  %nexti = add i32 %i, %incby
+  %iterate = icmp eq i32 %nexti, 40
+  br i1 %iterate, label %loop, label %loop_exit
+
+; CHECK: loop_exit:
+loop_exit:
+  ret i32 0
+}
+
+
+; CHECK: Statistics Collected
+; CHECK: 2 loop-unswitch - Number of selects unswitched

test/Transforms/LoopUnswitch/2015-06-10-Trivial.ll

+; RUN: opt < %s -loop-unswitch --loop-unswitch-threshold 4 \
+; RUN:   -verify-loop-info -S < %s 2>&1 -stats | FileCheck %s
+
+; Test for a bug. This tests that trivial unswitching happens even if
+; the computed unswitching cost is above the threshold and that
+; unswitching other loops in the same function does not prevent
+; unswitching on trivial conditions.
+
+define i32 @test(i32* %var) {
+; CHECK-LABEL: @test(
+; The first loop should be unswitched trivially on %c1 == false, leaving
+; one version of the loop with %c1 == true and no version for %c1 == false.
+; The unswitch cost is 5, above the threshold, but that should not matter
+; for trivial unswitching.
+  %c1 = icmp eq i32 1, 1
+; CHECK: br i1 %c1
+  br label %loop1
+
+loop1:
+; CHECK-NOT: br i1 false
+; CHECK: br i1 true
+; CHECK-NOT: br i1 false
+  %dummy1 = add i32 1, 1  ; to make the unswitch cost 5
+  %dummy2 = add i32 1, 1
+  %dummy3 = add i32 1, 1
+  %dummy4 = add i32 1, 1
+  br i1 %c1, label %loop1, label %loop1_exit
+
+; CHECK: loop1_exit:
+loop1_exit:
+; The second loop should be unswitched non-trivially on %c2 == true or
+; %c2 == false, producing two versions of the loop. The unswitch cost is 4.
+  %c2 = icmp eq i32 1, 2
+  br label %loop2
+
+loop2:
+  %i = phi i32 [0, %loop1_exit], [%nexti, %loop2]
+  %incby = select i1 %c2, i32 10, i32 20
+; CHECK-DAG: add i32 %i.us, 10
+; CHECK-DAG: add i32 %i, 20
+  %nexti = add i32 %i, %incby
+  %iterate = icmp eq i32 %nexti, 40
+  br i1 %iterate, label %loop2, label %loop2_exit
+
+; CHECK: loop2_exit:
+loop2_exit:
+  %c3 = icmp eq i32 1, 1
+  br label %loop3
+
+; The third loop is trivially unswitchable like the first one, the only
+; difference is that the unswitchable condition is %c3 == true, not false.
+loop3:
+; CHECK-NOT: br i1 true
+; CHECK: br i1 false
+; CHECK-NOT: br i1 true
+  %dummy5 = add i32 1, 1  ; to make the unswitch cost 5
+  %dummy6 = add i32 1, 1
+  %dummy7 = add i32 1, 1
+  %dummy8 = add i32 1, 1
+  br i1 %c3, label %loop3_exit, label %loop3
+
+; CHECK: loop3_exit:
+loop3_exit:
+  ret i32 0
+}
+
+; CHECK: Statistics Collected
+; CHECK: 2 loop-unswitch - Number of unswitches that are trivial
 No newline at end of file