[POC] Iterative hoisting during trivial unswitch

[reames]

Summary

This is not really ready for review; posted as a proof of concept since the use of SCEV's disposition ties into the discussion on D60093.

The basic idea to this is to be able to unswitch a long chain of range checks on different arrays all in a single invocation of SimpleLoopUnswitch. Right now, we're not able to so since each dominating check we eliminate prevents hoisting of dominated lengths. (Correctly.) If we decide to integrate the InvariantComputation logic from D60093 into SCEV's disposition handling, then we'll be able to prove that an invariant load (which the length would be) would be invariant after hoisting.

We might also be able to do a form of hoisting here using MSSA, but I haven't actually looked into that yet.

[reames]

Abandoning this approach. As Chandler pointed out in offline discussion, the iteration of the loop pass manager itself - remember, this is in the *new* pass manager, not the old - should handle this case. I'm going to try to figure out why it didn't first, and then only return to this approach if I'm either a) stuck on that for some reason or b) trying to improve efficiency (i.e. reduce number of iterations required.)

lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/Utils/Local.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/GenericDomTree.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 #include <algorithm>
 #include <cassert>
 #include <iterator>
 #include <numeric>
 #include <utility>
 
static bool unswitchTrivialBranch(Loop &L, BranchInst &BI, DominatorTree &DT,
 
   // The loop invariant values that we want to unswitch.
   TinyPtrVector<Value *> Invariants;
 
   // When true, we're fully unswitching the branch rather than just unswitching
   // some input conditions to the branch.
   bool FullUnswitch = false;
 
-  if (L.isLoopInvariant(BI.getCondition())) {
+  if (L.isLoopInvariant(BI.getCondition()) ||
+      (SE->isLoopInvariant(SE->getSCEV(BI.getCondition()), &L) &&
+       isSafeToExpand(SE->getSCEV(BI.getCondition()), *SE))) {
     Invariants.push_back(BI.getCondition());
     FullUnswitch = true;
   } else {
     if (auto *CondInst = dyn_cast<Instruction>(BI.getCondition()))
       Invariants = collectHomogenousInstGraphLoopInvariants(L, *CondInst, LI);
     if (Invariants.empty())
       // Couldn't find invariant inputs!
       return false;
LLVM_DEBUG({
     for (Value *Invariant : Invariants) {
       dbgs() << "      " << *Invariant << " == true";
       if (Invariant != Invariants.back())
         dbgs() << " ||";
       dbgs() << "\n";
     }
   });
 
+  if (!L.isLoopInvariant(BI.getCondition()) &&
+      SE->isLoopInvariant(SE->getSCEV(BI.getCondition()), &L)) {
+    auto &DL = LoopExitBB->getParent()->getParent()->getDataLayout();
+    auto *PHTerm = L.getLoopPreheader()->getTerminator();
+    // TODO: Do we need a SCEVHoister?
+    SCEVExpander Expander(*SE, DL, "");
+    auto *OldCond = BI.getCondition();
+    auto *NewCond = Expander.expandCodeFor(SE->getSCEV(OldCond),
+                                           OldCond->getType(),
+                                           PHTerm);
+    BI.setCondition(NewCond);
+    assert(Invariants.size() == 1 &&
+           Invariants[0] == OldCond);
+    TinyPtrVector<Value *> NewInvariants;
+    NewInvariants.push_back(NewCond);
+    Invariants = NewInvariants;
+
+    // FIXME: This can walk out of our current loop.
+    RecursivelyDeleteTriviallyDeadInstructions(OldCond, nullptr, MSSAU);
+  }
+
+  
   // If we have scalar evolutions, we need to invalidate them including this
   // loop and the loop containing the exit block.
   if (SE) {
     if (Loop *ExitL = LI.getLoopFor(LoopExitBB))
       SE->forgetLoop(ExitL);
     else
       // Forget the entire nest as this exits the entire nest.
       SE->forgetTopmostLoop(&L);

test/Transforms/SimpleLoopUnswitch/trivial-unswitch.ll

 ; CHECK-NEXT:    call void @sink(i32 %[[PHI]])
 ; CHECK-NEXT:    br label %header
 
 loopexit:
   ret void
 ; CHECK:       loopexit:
 ; CHECK-NEXT:    ret
 }
+
+define i32 @test_iterative_scev_hoist(i32* %var, i32 %cond1.i32,
+                                      i32 %cond2.i32) {
+; CHECK-LABEL: @test_iterative_scev_hoist(
+entry:
+  br label %loop_begin
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    trunc
+; CHECK-NEXT:    br i1 %{{.*}}, label %entry.split, label %loop_exit.split
+;
+; CHECK:       entry.split:
+; CHECK-NEXT:    trunc
+; CHECK-NEXT:    br i1 %{{.*}}, label %entry.split.split, label %loop_exit
+;
+; CHECK:       entry.split.split:
+; CHECK-NEXT:    br label %loop_begin
+
+loop_begin:
+  %cond1 = trunc i32 %cond1.i32 to i1
+  br i1 %cond1, label %continue, label %loop_exit  ; first trivial condition
+; CHECK:       loop_begin:
+; CHECK-NEXT:    br label %continue
+
+continue:
+  %var_val = load i32, i32* %var
+  %cond2 = trunc i32 %cond2.i32 to i1
+  br i1 %cond2, label %do_something, label %loop_exit  ; second trivial condition
+; CHECK:       continue:
+; CHECK-NEXT:    load
+; CHECK-NEXT:    br label %do_something
+
+do_something:
+  call void @some_func() noreturn nounwind
+  br label %loop_begin
+; CHECK:       do_something:
+; CHECK-NEXT:    call
+; CHECK-NEXT:    br label %loop_begin
+
+loop_exit:
+  ret i32 0
+; CHECK:       loop_exit:
+; CHECK-NEXT:    br label %loop_exit.split
+;
+; CHECK:       loop_exit.split:
+; CHECK-NEXT:    ret
+}