LLVM 19.0.0git
DomConditionCache.cpp
Go to the documentation of this file.
1//===- DomConditionCache.cpp ----------------------------------------------===//
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
11
12using namespace llvm;
13using namespace llvm::PatternMatch;
14
15// TODO: This code is very similar to findAffectedValues() in
16// AssumptionCache, but currently specialized to just the patterns that
17// computeKnownBits() supports, and without the notion of result elem indices
18// that are AC specific. Deduplicate this code once we have a clearer picture
19// of how much they can be shared.
21 SmallVectorImpl<Value *> &Affected) {
22 auto AddAffected = [&Affected](Value *V) {
23 if (isa<Argument>(V) || isa<GlobalValue>(V)) {
24 Affected.push_back(V);
25 } else if (auto *I = dyn_cast<Instruction>(V)) {
26 Affected.push_back(I);
27
28 // Peek through unary operators to find the source of the condition.
29 Value *Op;
30 if (match(I, m_PtrToInt(m_Value(Op)))) {
31 if (isa<Instruction>(Op) || isa<Argument>(Op))
32 Affected.push_back(Op);
33 }
34 }
35 };
36
39 Worklist.push_back(Cond);
40 while (!Worklist.empty()) {
41 Value *V = Worklist.pop_back_val();
42 if (!Visited.insert(V).second)
43 continue;
44
46 Value *A, *B;
47 if (match(V, m_LogicalOp(m_Value(A), m_Value(B)))) {
48 Worklist.push_back(A);
49 Worklist.push_back(B);
50 } else if (match(V, m_ICmp(Pred, m_Value(A), m_Constant()))) {
51 AddAffected(A);
52
53 if (ICmpInst::isEquality(Pred)) {
54 Value *X;
55 // (X & C) or (X | C) or (X ^ C).
56 // (X << C) or (X >>_s C) or (X >>_u C).
59 AddAffected(X);
60 } else {
61 Value *X;
62 // Handle (A + C1) u< C2, which is the canonical form of
63 // A > C3 && A < C4.
65 AddAffected(X);
66 // Handle icmp slt/sgt (bitcast X to int), 0/-1, which is supported by
67 // computeKnownFPClass().
68 if ((Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT) &&
70 Affected.push_back(X);
71 }
72 } else if (match(Cond, m_CombineOr(m_FCmp(Pred, m_Value(A), m_Constant()),
73 m_Intrinsic<Intrinsic::is_fpclass>(
74 m_Value(A), m_Constant())))) {
75 // Handle patterns that computeKnownFPClass() support.
76 AddAffected(A);
77 }
78 }
79}
80
82 assert(BI->isConditional() && "Must be conditional branch");
84 findAffectedValues(BI->getCondition(), Affected);
85 for (Value *V : Affected) {
86 auto &AV = AffectedValues[V];
87 if (!is_contained(AV, BI))
88 AV.push_back(BI);
89 }
90}
static void findAffectedValues(CallBase *CI, TargetTransformInfo *TTI, SmallVectorImpl< AssumptionCache::ResultElem > &Affected)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static void findAffectedValues(Value *Cond, SmallVectorImpl< Value * > &Affected)
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
#define I(x, y, z)
Definition: MD5.cpp:58
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Conditional or Unconditional Branch instruction.
bool isConditional() const
Value * getCondition() const
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:965
This class represents an Operation in the Expression.
void registerBranch(BranchInst *BI)
Add a branch condition to the cache.
bool isEquality() const
Return true if this predicate is either EQ or NE.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
LLVM Value Representation.
Definition: Value.h:74
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:982
auto m_LogicalOp()
Matches either L && R or L || R where L and R are arbitrary values.
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:144
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:147
CmpClass_match< LHS, RHS, FCmpInst, FCmpInst::Predicate > m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R)
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
BinOpPred_match< LHS, RHS, is_shift_op > m_Shift(const LHS &L, const RHS &R)
Matches shift operations.
BinOpPred_match< LHS, RHS, is_bitwiselogic_op > m_BitwiseLogic(const LHS &L, const RHS &R)
Matches bitwise logic operations.
ElementWiseBitCast_match< OpTy > m_ElementWiseBitCast(const OpTy &Op)
CastOperator_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:218
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
DWARFExpression::Operation Op
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1888