llvm/lib/Analysis/DomConditionCache.cpp

   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   ICmpInst::Predicate Pred;
  38   Value *A;
  39   if (match(Cond, m_ICmp(Pred, m_Value(A), m_Constant()))) {
  40     AddAffected(A);
  41
  42     if (ICmpInst::isEquality(Pred)) {
  43       Value *X;
  44       // (X & C) or (X | C) or (X ^ C).
  45       // (X << C) or (X >>_s C) or (X >>_u C).
  46       if (match(A, m_BitwiseLogic(m_Value(X), m_ConstantInt())) ||
  47           match(A, m_Shift(m_Value(X), m_ConstantInt())))
  48         AddAffected(X);
  49     } else {
  50       Value *X;
  51       // Handle (A + C1) u< C2, which is the canonical form of A > C3 && A < C4.
  52       if (match(A, m_Add(m_Value(X), m_ConstantInt())))
  53         AddAffected(X);
  54     }
  55   }
  56 }
  57
  58 void DomConditionCache::registerBranch(BranchInst *BI) {
  59   assert(BI->isConditional() && "Must be conditional branch");
  60   SmallVector<Value *, 16> Affected;
  61   findAffectedValues(BI->getCondition(), Affected);
  62   for (Value *V : Affected) {
  63     auto &AV = AffectedValues[V];
  64     if (!is_contained(AV, BI))
  65       AV.push_back(BI);
  66   }
  67 }