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