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 } 172