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
isGuard(const User * U)18 bool llvm::isGuard(const User *U) {
19 return match(U, m_Intrinsic<Intrinsic::experimental_guard>());
20 }
21
isWidenableCondition(const Value * V)22 bool llvm::isWidenableCondition(const Value *V) {
23 return match(V, m_Intrinsic<Intrinsic::experimental_widenable_condition>());
24 }
25
isWidenableBranch(const User * U)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
isGuardAsWidenableBranch(const User * U)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
parseWidenableBranch(const User * U,Value * & Condition,Value * & WidenableCondition,BasicBlock * & IfTrueBB,BasicBlock * & IfFalseBB)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
parseWidenableBranch(User * U,Use * & C,Use * & WC,BasicBlock * & IfTrueBB,BasicBlock * & IfFalseBB)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>
parseCondition(Value * Condition,CallbackType RecordCheckOrWidenableCond)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
parseWidenableGuard(const User * U,llvm::SmallVectorImpl<Value * > & Checks)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
extractWidenableCondition(const User * U)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