[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

22

*if* we can prove

25

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

25

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

25

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 iff \p U has semantics of a guard.
-bool isGuard(const User *U);
+/// 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 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/AliasSetTracker.cpp

 void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
   if (UnknownInsts.empty())
     addRef();
   UnknownInsts.emplace_back(I);
 
   // Guards are marked as modifying memory for control flow modelling purposes,
   // but don't actually modify any specific memory location.
   using namespace PatternMatch;
-  bool MayWriteMemory = I->mayWriteToMemory() && !isGuard(I) &&
+  bool MayWriteMemory = I->mayWriteToMemory() && !isGuardInIntrinsicForm(I) &&
     !(I->use_empty() && match(I, m_Intrinsic<Intrinsic::invariant_start>()));
   if (!MayWriteMemory) {
     Alias = SetMayAlias;
     Access |= RefAccess;
     return;
   }
 
   // FIXME: This should use mod/ref information to make this not suck so bad

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::isGuard(const User *U) {
+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::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/Analysis/ValueTracking.cpp

for (auto *CmpU : U->users()) {
         if (const BranchInst *BI = dyn_cast<BranchInst>(Curr)) {
           assert(BI->isConditional() && "uses a comparison!");
 
           BasicBlock *NonNullSuccessor =
               BI->getSuccessor(Pred == ICmpInst::ICMP_EQ ? 1 : 0);
           BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor);
           if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent()))
             return true;
-        } else if (Pred == ICmpInst::ICMP_NE && isGuard(Curr) &&
+        } else if (Pred == ICmpInst::ICMP_NE && isGuardInIntrinsicForm(Curr) &&
                    DT->dominates(cast<Instruction>(Curr), CtxI)) {
           return true;
         }
       }
     }
   }
 
   return false;

lib/Transforms/Scalar/EarlyCSE.cpp

if (match(Inst, m_Intrinsic<Intrinsic::invariant_start>())) {
       auto *CI = cast<CallInst>(Inst);
       MemoryLocation MemLoc = MemoryLocation::getForArgument(CI, 1, TLI);
       // Don't start a scope if we already have a better one pushed
       if (!AvailableInvariants.count(MemLoc))
         AvailableInvariants.insert(MemLoc, CurrentGeneration);
       continue;
     }
 
-    if (isGuard(Inst)) {
+    if (isGuardInIntrinsicForm(Inst)) {
       if (auto *CondI =
               dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0))) {
         if (SimpleValue::canHandle(CondI)) {
           // Do we already know the actual value of this condition?
           if (auto *KnownCond = AvailableValues.lookup(CondI)) {
             // Is the condition known to be true?
             if (isa<ConstantInt>(KnownCond) &&
                 cast<ConstantInt>(KnownCond)->isOne()) {

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());

lib/Transforms/Scalar/GuardWidening.cpp

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 (isGuard(&I))
+      if (isGuardInIntrinsicForm(&I))
+        // TODO: Support explicit guards as well.
         CurrentList.push_back(cast<Instruction>(&I));
 
     for (auto *II : CurrentList)
       Changed |= eliminateGuardViaWidening(II, 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 |= eliminateGuardViaWidening(BI, DFI, GuardsInBlock);
           else if (BPI->getEdgeProbability(BB, 1U) >= *LikelyTaken)
             Changed |= eliminateGuardViaWidening(BI, DFI, GuardsInBlock,
                                                  /*InvertCondition*/true);
         }
   }
 
   assert(EliminatedGuardsAndBranches.empty() || Changed);
   for (auto *I : EliminatedGuardsAndBranches)
     if (!WidenedGuards.count(I)) {
       assert(isa<ConstantInt>(getCondition(I)) && "Should be!");
-      if (isGuard(I))
+      if (isGuardInIntrinsicForm(I))
         eliminateGuard(I);
       else {
         assert(isa<BranchInst>(I) &&
                "Eliminated something other than guard or branch?");
         ++CondBranchEliminated;
       }
     }
 

lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreadingPass::ProcessGuards(BasicBlock *BB) {
   // Try to thread one of the guards of the block.
   // TODO: Look up deeper than to immediate predecessor?
   auto *Parent = Pred1->getSinglePredecessor();
   if (!Parent || Parent != Pred2->getSinglePredecessor())
     return false;
 
   if (auto *BI = dyn_cast<BranchInst>(Parent->getTerminator()))
     for (auto &I : *BB)
-      if (isGuard(&I) && ThreadGuard(BB, cast<IntrinsicInst>(&I), BI))
+      if (isGuardInIntrinsicForm(&I) &&
+          ThreadGuard(BB, cast<IntrinsicInst>(&I), BI))
         return true;
 
   return false;
 }
 
 /// Try to propagate the guard from BB which is the lower block of a diamond
 /// to one of its branches, in case if diamond's condition implies guard's
 /// condition.

lib/Transforms/Scalar/LICM.cpp

for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
         hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE);
         Changed = true;
         continue;
       }
 
       using namespace PatternMatch;
       if (((I.use_empty() &&
             match(&I, m_Intrinsic<Intrinsic::invariant_start>())) ||
-           isGuard(&I)) &&
+           isGuardInIntrinsicForm(&I)) &&
           IsMustExecute && IsMemoryNotModified &&
           CurLoop->hasLoopInvariantOperands(&I)) {
         hoist(I, DT, CurLoop, SafetyInfo, ORE);
         Changed = true;
         continue;
       }
 
       if (IsMustExecute)

lib/Transforms/Scalar/LowerGuardIntrinsic.cpp

static bool lowerGuardIntrinsic(Function &F) {
   // do.
   auto *GuardDecl = F.getParent()->getFunction(
       Intrinsic::getName(Intrinsic::experimental_guard));
   if (!GuardDecl || GuardDecl->use_empty())
     return false;
 
   SmallVector<CallInst *, 8> ToLower;
   for (auto &I : instructions(F))
-    if (isGuard(&I))
+    if (isGuardInIntrinsicForm(&I))
+      // TODO: Introduce lowering for guards in explicit form as well.
       ToLower.push_back(cast<CallInst>(&I));
 
   if (ToLower.empty())
     return false;
 
   auto *DeoptIntrinsic = Intrinsic::getDeclaration(
       F.getParent(), Intrinsic::experimental_deoptimize, {F.getReturnType()});
   DeoptIntrinsic->setCallingConv(GuardDecl->getCallingConv());