Aggressively hoist guards out of loops (to provide a target for widening)

[reames]

Summary

If we have a guard w/loop invariant operands, which is reached along a side effect free path on the first iteration, we can hoist that guard outside the loop, even over control flow we can not analyse. Doing so may widen the condition - make it fail on more executions than the original program - but that's explicitly allowed by the documented semantics of guards.

At the moment, I'm mostly looking for feedback on approach. Is this the right framing and placement? As noted in the comment, I'm considering an alternate "spliting" framing, would that be cleaner?

I need to add dedicated tests and will rebase when done so, but for now, the GuardWidening/basics.ll test show the difference fairly well. (I have not included the output in the diff yet.)

[reames]

Planning a change in direction after offline discussion w/Artur. Instead of framing this as hoisting/widening, I'm going to reframe as a separate loop transform which lifts a trivial guard (by splitting the condition) into the loop preheader where possible. We think this will be easier to test, and may have positive effects beyond guard widening,

[reames]

No longer actively working on this, we've moved to widenable conditions by default anyway.

lib/Transforms/Scalar/GuardWidening.cpp

static cl::opt<unsigned> FrequentBranchThreshold(
     cl::init(1000));
 
 static cl::opt<bool>
     WidenBranchGuards("guard-widening-widen-branch-guards", cl::Hidden,
                       cl::desc("Whether or not we should widen guards  "
                                "expressed as branches by widenable conditions"),
                       cl::init(true));
 
+static cl::opt<bool>
+    AggressivelyHoist("guard-widening-aggressively-hoist", cl::Hidden,
+                      cl::desc("Should guards be hoisted out of loops "
+                               "(whether they're known to execute or not)"),
+                      cl::init(true));
+
+
 namespace {
 
 // Get the condition of \p I. It can either be a guard or a conditional branch.
 static Value *getCondition(Instruction *I) {
   if (IntrinsicInst *GI = dyn_cast<IntrinsicInst>(I)) {
     assert(GI->getIntrinsicID() == Intrinsic::experimental_guard &&
            "Bad guard intrinsic?");
     return GI->getArgOperand(0);

 static bool isSupportedGuardInstruction(const Instruction *Insn) {
   if (isGuard(Insn))
     return true;
   if (WidenBranchGuards && isGuardAsWidenableBranch(Insn))
     return true;
   return false;
 }
 
+/// If it is legal to hoist a guard out of a loop into the preheader, do so.
+/// The assumption is that it is always profitable to do so and that backoff
+/// (i.e. unprofitable transforms triggering recompiles w/decreased
+/// optimization aggressiveness) are handled externally.  In particular, this
+/// may introduce deoptimizations which would have never happened in the
+/// original program.
+static bool hoistGuardToPreheader(ICFLoopSafetyInfo &SI,
+                                  Instruction &Guard, Loop *L) {
+  // TODO: implement a similiar transform for widenable_conditions
+  assert(isGuard(&Guard));
+
+  BasicBlock *Preheader = L->getLoopPreheader();
+  if (!Preheader)
+    return false;
+
+  // TODO: enhancement ideas:
+  // *) Hoist out of outer most loop we can establish legality for, not simply
+  //    the innermost one as we do now.
+  // *) Limit the transform to cases where BPI tells us the block is likely to
+  //    run, and thus we're not widening "too much".  (Possibly rephrase this
+  //    as unconditional splitting followed by conditional widening?)
+
+  bool SplitGuard = !L->isLoopInvariant(Guard.getOperand(0));
+  for (unsigned i = 1; i < Guard.getNumOperands(); i++)
+    if (!L->isLoopInvariant(Guard.getOperand(i)))
+      return false;
+  if (!SI.doesNotWriteMemoryBefore(Guard, L))
+    return false;
+  if (SplitGuard) {
+    auto *NewGuard = Guard.clone();
+    auto *True = ConstantInt::getTrue(Guard.getOperand(0)->getType());
+    NewGuard->setOperand(0, True);
+    SI.insertInstructionTo(NewGuard, Preheader);
+    NewGuard->insertBefore(Preheader->getTerminator());
+  } else {
+    SI.removeInstruction(&Guard);
+    SI.insertInstructionTo(&Guard, Preheader);
+    Guard.moveBefore(Preheader->getTerminator());
+  }
+  return true;
+}
+
 bool GuardWideningImpl::run() {
-  DenseMap<BasicBlock *, SmallVector<Instruction *, 8>> GuardsInBlock;
   bool Changed = false;
+
+  if (AggressivelyHoist) {
+    // As a first pass, hoist any guards out of loops that we can.  Doing this
+    // before the second pass ensures that we can merge them after hoisting.
+    ICFLoopSafetyInfo SI(&DT);
+    for (auto DFI = df_begin(Root), DFE = df_end(Root);
+         DFI != DFE; ++DFI) {
+      auto *BB = (*DFI)->getBlock();
+      if (!BlockFilter(BB))
+        continue;
+      
+      Loop *L = LI.getLoopFor(BB);
+      for (auto Itr = BB->begin(); Itr != BB->end();) {
+        Instruction &I = *(Itr);
+        ++Itr;
+        if (isGuard(&I) && L && hoistGuardToPreheader(SI, I, L))
+          Changed = true;
+      }
+    }
+  }
+  DenseMap<BasicBlock *, SmallVector<Instruction *, 8>> GuardsInBlock;
   Optional<BranchProbability> LikelyTaken = None;
   if (WidenFrequentBranches && BPI) {
     unsigned Threshold = FrequentBranchThreshold;
     assert(Threshold > 0 && "Zero threshold makes no sense!");
     LikelyTaken = BranchProbability(Threshold - 1, Threshold);
   }
-
   for (auto DFI = df_begin(Root), DFE = df_end(Root);
        DFI != DFE; ++DFI) {
     auto *BB = (*DFI)->getBlock();
     if (!BlockFilter(BB))
       continue;
 
     auto &CurrentList = GuardsInBlock[BB];
 
     for (auto &I : *BB)
       if (isSupportedGuardInstruction(&I))
         CurrentList.push_back(cast<Instruction>(&I));
     
-    for (auto *II : CurrentList)
-      Changed |= eliminateInstrViaWidening(II, DFI, GuardsInBlock);
+    for (auto *I : CurrentList)
+      Changed |= eliminateInstrViaWidening(I, DFI, GuardsInBlock);
+    
     if (WidenFrequentBranches && BPI)
       if (auto *BI = dyn_cast<BranchInst>(BB->getTerminator()))
         if (BI->isConditional()) {
           // If one of branches of a conditional is likely taken, try to
           // eliminate it.
           if (BPI->getEdgeProbability(BB, 0U) >= *LikelyTaken)
             Changed |= eliminateInstrViaWidening(BI, DFI, GuardsInBlock);
           else if (BPI->getEdgeProbability(BB, 1U) >= *LikelyTaken)