172 lines · 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-exception6//7//===----------------------------------------------------------------------===//8// Utils that are used to perform analyzes related to guards and their9// conditions.10//===----------------------------------------------------------------------===//11 12#include "llvm/Analysis/GuardUtils.h"13#include "llvm/IR/PatternMatch.h"14 15using namespace llvm;16using namespace llvm::PatternMatch;17 18bool llvm::isGuard(const User *U) {19 return match(U, m_Intrinsic<Intrinsic::experimental_guard>());20}21 22bool llvm::isWidenableCondition(const Value *V) {23 return match(V, m_Intrinsic<Intrinsic::experimental_widenable_condition>());24}25 26bool llvm::isWidenableBranch(const User *U) {27 Value *Condition, *WidenableCondition;28 BasicBlock *GuardedBB, *DeoptBB;29 return parseWidenableBranch(U, Condition, WidenableCondition, GuardedBB,30 DeoptBB);31}32 33bool 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 53bool 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 else62 Condition = ConstantInt::getTrue(IfTrueBB->getContext());63 WidenableCondition = WC->get();64 return true;65 }66 return false;67}68 69bool 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 %IfFalse90 // 2) br (i1 (and WC(), B)), label %IfTrue, label %IfFalse91 // We do not check for more generalized and trees as we should canonicalize92 // 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 constexpr99 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 117template <typename CallbackType>118static 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 138void 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 151Value *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't163 // 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