[ExplicitGuards][NFC] API for explicit guards recognition

[mkazantsev]

Summary

This patch adds some functions that can distinguish guards represented as
explicit branches and usual explicit branches.

[mkazantsev]

Need to add tests on passes that use isGuard to see how they feel about it. Needs rework.

[mkazantsev]

Now this is an NFC. We will visit every place where explicit guards need enabling independently.

[fedor.sergeev]

include/llvm/Analysis/GuardUtils.h

33

*if* we can prove

36

Hmm... perhaps its coffee time, but I cant draw a line between the function name and its functionality.
"Re"-executable?

[mkazantsev]

include/llvm/Analysis/GuardUtils.h

36

Re-executable is the same as "memory was not modified before it"... I need to think how to re-state it clearly.

[fedor.sergeev]

include/llvm/Analysis/GuardUtils.h

36

Do you really need it to be a public interface?

include/llvm/Analysis/GuardUtils.h

 // conditions.
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_GUARDUTILS_H
 #define LLVM_ANALYSIS_GUARDUTILS_H
 
 namespace llvm {
 
+class BasicBlock;
 class User;
+class Value;
+
+/// Returns true of we can prove that execution will reach a call of an
+/// llvm.experimental.deopt intrinsic and memory will not be modified before
+/// that under assumption that we enter the basic block \p BB.
+bool alwaysGoesToReExecutableDeoptBlock(const BasicBlock *BB);
+
+/// If \p V can be represented as (%cond1 & %cond2 & ... & %wc & ...),
+/// where %wc is the result of call of llvm.experimental.widenable.condition,
+/// return %wc. Otherwise, return nullptr.
+const Value *extractWidenableCondition(const Value *V);
 
 /// Returns true iff \p U has semantics of a guard.
 bool isGuard(const User *U);
 
+/// Returns true iff \p is a guard represented as intrinsic.
+bool isGuardInIntrinsicForm(const User *U);
+
+/// Returns true iff \p is a guard represented as explicit branch.
+bool isGuardInExplicitForm(const User *U);
+
 } // llvm
 
 #endif // LLVM_ANALYSIS_GUARDUTILS_H
 

lib/Analysis/GuardUtils.cpp

 //===-- GuardUtils.cpp - Utils for work with guards -------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 // Utils that are used to perform analyzes related to guards and their
 // conditions.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/GuardUtils.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/PatternMatch.h"
 
 using namespace llvm;
 
+bool llvm::alwaysGoesToReExecutableDeoptBlock(const BasicBlock *BB) {
+  SmallPtrSet<const BasicBlock *, 4> SeenBlocks;
+  SeenBlocks.insert(BB);
+  do {
+    for (auto &I : *BB) {
+      // We are done if we have found the deopt call.
+      using namespace llvm::PatternMatch;
+      if (match(&I, m_Intrinsic<Intrinsic::experimental_deoptimize>()))
+          return true;
+      // If an instruction may write memory, this makes the part between the
+      // guard and the deoptimization not re-executable. If there is an
+      // instruction that may not transfer execution to successor, then we may
+      // not reach the deopt. In either case, conservatively return false.
+      if (I.mayWriteToMemory() ||
+          !isGuaranteedToTransferExecutionToSuccessor(&I))
+        return false;
+    }
+    // If there is a single successor, go analyze it. Do not deal with complex
+    // control flow.
+    if (auto *Succ = BB->getSingleSuccessor())
+      BB = Succ;
+    // Bail if we found a loop.
+  } while (SeenBlocks.insert(BB).second);
+  // Otherwise we are dealing with something that does not always deopt, or
+  // it is too hard to prove that it does.
+  return false;
+}
+
+const Value *llvm::extractWidenableCondition(const Value *V) {
+  SmallPtrSet<const Value *, 4> Visited;
+  SmallVector<const Value *, 4> WorkList;
+  Visited.insert(V);
+  WorkList.push_back(V);
+
+  // Try to find a widenable condition among arguments of AND (recursively).
+  while (!WorkList.empty()) {
+    auto *Curr = WorkList.pop_back_val();
+    using namespace llvm::PatternMatch;
+    if (match(Curr, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
+      return Curr;
+    const Value *Op1 = nullptr, *Op2 = nullptr;
+    if (match(Curr, m_And(m_Value(Op1), m_Value(Op2)))) {
+      if (Visited.insert(Op1).second)
+        WorkList.push_back(Op1);
+      if (Visited.insert(Op2).second)
+        WorkList.push_back(Op2);
+    }
+  }
+  // Nothing found.
+  return nullptr;
+}
+
 bool llvm::isGuard(const User *U) {
+  return isGuardInIntrinsicForm(U) || isGuardInExplicitForm(U);
+}
+
+bool llvm::isGuardInIntrinsicForm(const User *U) {
   using namespace llvm::PatternMatch;
   return match(U, m_Intrinsic<Intrinsic::experimental_guard>());
 }
+
+bool llvm::isGuardInExplicitForm(const User *U){
+    // Otherwise check whether it is a guard expressed in implicit control flow.
+  // First of all, it should be a conditional branch.
+  auto *BI = dyn_cast<BranchInst>(U);
+  if (!BI || !BI->isConditional())
+    return false;
+  // Make sure that the condition of this branch contains a widneable condition,
+  // maybe AND'ed with other operands.
+  if (!extractWidenableCondition(BI->getCondition()))
+    return false;
+  // Make sure that the false branch ends with a deopt which is always executed,
+  // and that no instruction between the guard and the deopt may change the
+  // memory state.
+  if (!alwaysGoesToReExecutableDeoptBlock(BI->getSuccessor(1)))
+    return false;
+  return true;
+}

lib/Transforms/Scalar/ExplicifyGuards.cpp

ExplicifyGuardsLegacyPass() : FunctionPass(ID) {
     initializeExplicifyGuardsLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override;
 };
 }
 
 static void turnToExplicitForm(CallInst *Guard, Function *DeoptIntrinsic) {
+  assert(isGuardInIntrinsicForm(Guard) && "Must be!");
   // Replace the guard with an explicit branch (just like in GuardWidening).
   BasicBlock *BB = Guard->getParent();
   makeGuardControlFlowExplicit(DeoptIntrinsic, Guard);
   BranchInst *ExplicitGuard = cast<BranchInst>(BB->getTerminator());
   assert(ExplicitGuard->isConditional() && "Must be!");
 
   // We want the guard to be expressed as explicit control flow, but still be
   // widenable. For that, we add Widenable Condition intrinsic call to the
   // guard's condition.
   IRBuilder<> B(ExplicitGuard);
   auto *WidenableCondition =
       B.CreateIntrinsic(Intrinsic::experimental_widenable_condition,
                         ExplicitGuard, "widenable_cond");
   WidenableCondition->setCallingConv(Guard->getCallingConv());
   auto *NewCond =
       B.CreateAnd(ExplicitGuard->getCondition(), WidenableCondition);
   NewCond->setName("exiplicit_guard_cond");
   ExplicitGuard->setCondition(NewCond);
+  assert(isGuardInExplicitForm(ExplicitGuard) && "Must be!");
   Guard->eraseFromParent();
 }
 
 static bool explicifyGuards(Function &F) {
   // Check if we can cheaply rule out the possibility of not having any work to
   // do.
   auto *GuardDecl = F.getParent()->getFunction(
       Intrinsic::getName(Intrinsic::experimental_guard));
   if (!GuardDecl || GuardDecl->use_empty())
     return false;
 
   SmallVector<CallInst *, 8> GuardIntrinsics;
   for (auto &I : instructions(F))
-    if (isGuard(&I))
+    if (isGuardInIntrinsicForm(&I))
       GuardIntrinsics.push_back(cast<CallInst>(&I));
 
   if (GuardIntrinsics.empty())
     return false;
 
   auto *DeoptIntrinsic = Intrinsic::getDeclaration(
       F.getParent(), Intrinsic::experimental_deoptimize, {F.getReturnType()});
   DeoptIntrinsic->setCallingConv(GuardDecl->getCallingConv());