llvm/lib/Analysis/GuardUtils.cpp

   1 //===-- GuardUtils.cpp - Utils for work with guards -------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 // Utils that are used to perform analyzes related to guards and their
   9 // conditions.
  10 //===----------------------------------------------------------------------===//
  11
  12 #include "llvm/Analysis/GuardUtils.h"
  13 #include "llvm/IR/PatternMatch.h"
  14
  15 using namespace llvm;
  16 using namespace llvm::PatternMatch;
  17
  18 bool llvm::isGuard(const User *U) {
  19   return match(U, m_Intrinsic<Intrinsic::experimental_guard>());
  20 }
  21
  22 bool llvm::isWidenableCondition(const Value *V) {
  23   return match(V, m_Intrinsic<Intrinsic::experimental_widenable_condition>());
  24 }
  25
  26 bool llvm::isWidenableBranch(const User *U) {
  27   Value *Condition, *WidenableCondition;
  28   BasicBlock *GuardedBB, *DeoptBB;
  29   return parseWidenableBranch(U, Condition, WidenableCondition, GuardedBB,
  30                               DeoptBB);
  31 }
  32
  33 bool llvm::isGuardAsWidenableBranch(const User *U) {
  34   if (!isWidenableBranch(U))
  35     return false;
  36   BasicBlock *DeoptBB = cast<BranchInst>(U)->getSuccessor(1);
  37   SmallPtrSet<const BasicBlock *, 2> Visited;
  38   Visited.insert(DeoptBB);
  39   do {
  40     for (auto &Insn : *DeoptBB) {
  41       if (match(&Insn, m_Intrinsic<Intrinsic::experimental_deoptimize>()))
  42         return true;
  43       if (Insn.mayHaveSideEffects())
  44         return false;
  45     }
  46     DeoptBB = DeoptBB->getUniqueSuccessor();
  47     if (!DeoptBB)
  48       return false;
  49   } while (Visited.insert(DeoptBB).second);
  50   return false;
  51 }
  52
  53 bool llvm::parseWidenableBranch(const User *U, Value *&Condition,
  54                                 Value *&WidenableCondition,
  55                                 BasicBlock *&IfTrueBB, BasicBlock *&IfFalseBB) {
  56
  57   Use *C, *WC;
  58   if (parseWidenableBranch(const_cast<User*>(U), C, WC, IfTrueBB, IfFalseBB)) {
  59     if (C)
  60       Condition = C->get();
  61     else
  62       Condition = ConstantInt::getTrue(IfTrueBB->getContext());
  63     WidenableCondition = WC->get();
  64     return true;
  65   }
  66   return false;
  67 }
  68
  69 bool llvm::parseWidenableBranch(User *U, Use *&C,Use *&WC,
  70                                 BasicBlock *&IfTrueBB, BasicBlock *&IfFalseBB) {
  71
  72   auto *BI = dyn_cast<BranchInst>(U);
  73   if (!BI || !BI->isConditional())
  74     return false;
  75   auto *Cond = BI->getCondition();
  76   if (!Cond->hasOneUse())
  77     return false;
  78
  79   IfTrueBB = BI->getSuccessor(0);
  80   IfFalseBB = BI->getSuccessor(1);
  81
  82   if (match(Cond, m_Intrinsic<Intrinsic::experimental_widenable_condition>())) {
  83     WC = &BI->getOperandUse(0);
  84     C = nullptr;
  85     return true;
  86   }
  87
  88   // Check for two cases:
  89   // 1) br (i1 (and A, WC())), label %IfTrue, label %IfFalse
  90   // 2) br (i1 (and WC(), B)), label %IfTrue, label %IfFalse
  91   // We do not check for more generalized and trees as we should canonicalize
  92   // to the form above in instcombine. (TODO)
  93   Value *A, *B;
  94   if (!match(Cond, m_And(m_Value(A), m_Value(B))))
  95     return false;
  96   auto *And = dyn_cast<Instruction>(Cond);
  97   if (!And)
  98     // Could be a constexpr
  99     return false;
 100
 101   if (match(A, m_Intrinsic<Intrinsic::experimental_widenable_condition>()) &&
 102       A->hasOneUse()) {
 103     WC = &And->getOperandUse(0);
 104     C = &And->getOperandUse(1);
 105     return true;
 106   }
 107
 108   if (match(B, m_Intrinsic<Intrinsic::experimental_widenable_condition>()) &&
 109       B->hasOneUse()) {
 110     WC = &And->getOperandUse(1);
 111     C = &And->getOperandUse(0);
 112     return true;
 113   }
 114   return false;
 115 }
 116
 117 template <typename CallbackType>
 118 static void parseCondition(Value *Condition,
 119                            CallbackType RecordCheckOrWidenableCond) {
 120   SmallVector<Value *, 4> Worklist(1, Condition);
 121   SmallPtrSet<Value *, 4> Visited;
 122   Visited.insert(Condition);
 123   do {
 124     Value *Check = Worklist.pop_back_val();
 125     Value *LHS, *RHS;
 126     if (match(Check, m_And(m_Value(LHS), m_Value(RHS)))) {
 127       if (Visited.insert(LHS).second)
 128         Worklist.push_back(LHS);
 129       if (Visited.insert(RHS).second)
 130         Worklist.push_back(RHS);
 131       continue;
 132     }
 133     if (!RecordCheckOrWidenableCond(Check))
 134       break;
 135   } while (!Worklist.empty());
 136 }
 137
 138 void llvm::parseWidenableGuard(const User *U,
 139                                llvm::SmallVectorImpl<Value *> &Checks) {
 140   assert((isGuard(U) || isWidenableBranch(U)) && "Should be");
 141   Value *Condition = isGuard(U) ? cast<IntrinsicInst>(U)->getArgOperand(0)
 142                                 : cast<BranchInst>(U)->getCondition();
 143
 144   parseCondition(Condition, [&](Value *Check) {
 145     if (!isWidenableCondition(Check))
 146       Checks.push_back(Check);
 147     return true;
 148   });
 149 }
 150
 151 Value *llvm::extractWidenableCondition(const User *U) {
 152   auto *BI = dyn_cast<BranchInst>(U);
 153   if (!BI || !BI->isConditional())
 154     return nullptr;
 155
 156   auto Condition = BI->getCondition();
 157   if (!Condition->hasOneUse())
 158     return nullptr;
 159
 160   Value *WidenableCondition = nullptr;
 161   parseCondition(Condition, [&](Value *Check) {
 162     // We require widenable_condition has only one use, otherwise we don't
 163     // consider appropriate branch as widenable.
 164     if (isWidenableCondition(Check) && Check->hasOneUse()) {
 165       WidenableCondition = Check;
 166       return false;
 167     }
 168     return true;
 169   });
 170   return WidenableCondition;
 171 }