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

[broune]

Summary

This change fixes two 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.

First fix: 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.

Second fix: 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.

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

[broune]

Phabricator tells me to make a new revision instead, this time adding llvm-commits as a subscriber, so I'll do that.

[broune]

The real, fixed revision is at D10376. Ignore this one.

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;
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) {
     // 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.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