llvm-project

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