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 9 #include "llvm/Analysis/DomConditionCache.h" 10 #include "llvm/IR/PatternMatch.h" 11 12 using namespace llvm; 13 using 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. 20 static void findAffectedValues(Value *Cond, 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 37 bool TopLevelIsAnd = match(Cond, m_LogicalAnd()); 38 SmallVector<Value *, 8> Worklist; 39 SmallPtrSet<Value *, 8> Visited; 40 Worklist.push_back(Cond); 41 while (!Worklist.empty()) { 42 Value *V = Worklist.pop_back_val(); 43 if (!Visited.insert(V).second) 44 continue; 45 46 CmpInst::Predicate Pred; 47 Value *A, *B; 48 // Only recurse into and/or if it matches the top-level and/or type. 49 if (TopLevelIsAnd ? match(V, m_LogicalAnd(m_Value(A), m_Value(B))) 50 : match(V, m_LogicalOr(m_Value(A), m_Value(B)))) { 51 Worklist.push_back(A); 52 Worklist.push_back(B); 53 } else if (match(V, m_ICmp(Pred, m_Value(A), m_Constant()))) { 54 AddAffected(A); 55 56 if (ICmpInst::isEquality(Pred)) { 57 Value *X; 58 // (X & C) or (X | C) or (X ^ C). 59 // (X << C) or (X >>_s C) or (X >>_u C). 60 if (match(A, m_BitwiseLogic(m_Value(X), m_ConstantInt())) || 61 match(A, m_Shift(m_Value(X), m_ConstantInt()))) 62 AddAffected(X); 63 } else { 64 Value *X; 65 // Handle (A + C1) u< C2, which is the canonical form of 66 // A > C3 && A < C4. 67 if (match(A, m_Add(m_Value(X), m_ConstantInt()))) 68 AddAffected(X); 69 // Handle icmp slt/sgt (bitcast X to int), 0/-1, which is supported by 70 // computeKnownFPClass(). 71 if ((Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT) && 72 match(A, m_ElementWiseBitCast(m_Value(X)))) 73 Affected.push_back(X); 74 } 75 } else if (match(Cond, m_CombineOr(m_FCmp(Pred, m_Value(A), m_Constant()), 76 m_Intrinsic<Intrinsic::is_fpclass>( 77 m_Value(A), m_Constant())))) { 78 // Handle patterns that computeKnownFPClass() support. 79 AddAffected(A); 80 } 81 } 82 } 83 84 void DomConditionCache::registerBranch(BranchInst *BI) { 85 assert(BI->isConditional() && "Must be conditional branch"); 86 SmallVector<Value *, 16> Affected; 87 findAffectedValues(BI->getCondition(), Affected); 88 for (Value *V : Affected) { 89 auto &AV = AffectedValues[V]; 90 if (!is_contained(AV, BI)) 91 AV.push_back(BI); 92 } 93 } 94