File Manager

003 File Manager

Current Path: /usr/src/contrib/llvm-project/llvm/lib/Analysis

usr / src / contrib / llvm-project / llvm / lib / Analysis /

📁 ..
📄 AliasAnalysis.cpp(33.55 KB)
📄 AliasAnalysisEvaluator.cpp(15.64 KB)
📄 AliasAnalysisSummary.cpp(3.49 KB)
📄 AliasAnalysisSummary.h(10.17 KB)
📄 AliasSetTracker.cpp(25.86 KB)
📄 Analysis.cpp(5.29 KB)
📄 AssumeBundleQueries.cpp(7.96 KB)
📄 AssumptionCache.cpp(10.94 KB)
📄 BasicAliasAnalysis.cpp(85.81 KB)
📄 BlockFrequencyInfo.cpp(12.39 KB)
📄 BlockFrequencyInfoImpl.cpp(28.6 KB)
📄 BranchProbabilityInfo.cpp(43.48 KB)
📄 CFG.cpp(9.9 KB)
📄 CFGPrinter.cpp(11.2 KB)
📄 CFLAndersAliasAnalysis.cpp(33.01 KB)
📄 CFLGraph.h(21.23 KB)
📄 CFLSteensAliasAnalysis.cpp(13.24 KB)
📄 CGSCCPassManager.cpp(31.2 KB)
📄 CallGraph.cpp(12.86 KB)
📄 CallGraphSCCPass.cpp(26.31 KB)
📄 CallPrinter.cpp(9.48 KB)
📄 CaptureTracking.cpp(15.38 KB)
📄 CmpInstAnalysis.cpp(4.63 KB)
📄 CodeMetrics.cpp(6.99 KB)
📄 ConstantFolding.cpp(105.15 KB)
📄 CostModel.cpp(3.87 KB)
📄 DDG.cpp(11.29 KB)
📄 Delinearization.cpp(4.49 KB)
📄 DemandedBits.cpp(16.27 KB)
📄 DependenceAnalysis.cpp(150.78 KB)
📄 DependenceGraphBuilder.cpp(19.24 KB)
📄 DivergenceAnalysis.cpp(15.59 KB)
📄 DomPrinter.cpp(9.67 KB)
📄 DomTreeUpdater.cpp(15.21 KB)
📄 DominanceFrontier.cpp(3.2 KB)
📄 EHPersonalities.cpp(5.89 KB)
📄 GlobalsModRef.cpp(41 KB)
📄 GuardUtils.cpp(3.27 KB)
📄 HeatUtils.cpp(2.85 KB)
📄 IVDescriptors.cpp(42.28 KB)
📄 IVUsers.cpp(16.12 KB)
📄 IndirectCallPromotionAnalysis.cpp(4.33 KB)
📄 InlineAdvisor.cpp(15.28 KB)
📄 InlineCost.cpp(99.47 KB)
📄 InlineFeaturesAnalysis.cpp(1.59 KB)
📄 InlineSizeEstimatorAnalysis.cpp(10.95 KB)
📄 InstCount.cpp(2.45 KB)
📄 InstructionPrecedenceTracking.cpp(4.8 KB)
📄 InstructionSimplify.cpp(216.91 KB)
📄 Interval.cpp(1.78 KB)
📄 IntervalPartition.cpp(4.5 KB)
📄 LazyBlockFrequencyInfo.cpp(2.81 KB)
📄 LazyBranchProbabilityInfo.cpp(2.96 KB)
📄 LazyCallGraph.cpp(67.33 KB)
📄 LazyValueInfo.cpp(76.38 KB)
📄 LegacyDivergenceAnalysis.cpp(14.82 KB)
📄 Lint.cpp(29.07 KB)
📄 Loads.cpp(20.6 KB)
📄 LoopAccessAnalysis.cpp(88.02 KB)
📄 LoopAnalysisManager.cpp(6.6 KB)
📄 LoopCacheAnalysis.cpp(23.53 KB)
📄 LoopInfo.cpp(37.15 KB)
📄 LoopNestAnalysis.cpp(10.62 KB)
📄 LoopPass.cpp(12.89 KB)
📄 LoopUnrollAnalyzer.cpp(7.26 KB)
📄 MLInlineAdvisor.cpp(11.36 KB)
📄 MemDepPrinter.cpp(5.13 KB)
📄 MemDerefPrinter.cpp(2.53 KB)
📄 MemoryBuiltins.cpp(41.14 KB)
📄 MemoryDependenceAnalysis.cpp(69.89 KB)
📄 MemoryLocation.cpp(7.92 KB)
📄 MemorySSA.cpp(90.16 KB)
📄 MemorySSAUpdater.cpp(57.9 KB)
📄 ModuleDebugInfoPrinter.cpp(4.02 KB)
📄 ModuleSummaryAnalysis.cpp(38.13 KB)
📄 MustExecute.cpp(31.18 KB)
📄 ObjCARCAliasAnalysis.cpp(5.81 KB)
📄 ObjCARCAnalysisUtils.cpp(1.07 KB)
📄 ObjCARCInstKind.cpp(23.15 KB)
📄 OptimizationRemarkEmitter.cpp(4.23 KB)
📄 PHITransAddr.cpp(16.05 KB)
📄 PhiValues.cpp(8.4 KB)
📄 PostDominators.cpp(3.59 KB)
📄 ProfileSummaryInfo.cpp(18.07 KB)
📄 PtrUseVisitor.cpp(1.28 KB)
📄 RegionInfo.cpp(6.5 KB)
📄 RegionPass.cpp(9.23 KB)
📄 RegionPrinter.cpp(8.61 KB)
📄 ReleaseModeModelRunner.cpp(2.83 KB)
📄 ScalarEvolution.cpp(475.26 KB)
📄 ScalarEvolutionAliasAnalysis.cpp(5.96 KB)
📄 ScalarEvolutionDivision.cpp(7.51 KB)
📄 ScalarEvolutionNormalization.cpp(4.59 KB)
📄 ScopedNoAliasAA.cpp(7.38 KB)
📄 StackLifetime.cpp(12.22 KB)
📄 StackSafetyAnalysis.cpp(31.81 KB)
📄 StratifiedSets.h(18.67 KB)
📄 SyncDependenceAnalysis.cpp(12.97 KB)
📄 SyntheticCountsUtils.cpp(3.81 KB)
📄 TFUtils.cpp(8.99 KB)
📄 TargetLibraryInfo.cpp(58.98 KB)
📄 TargetTransformInfo.cpp(48.15 KB)
📄 Trace.cpp(1.8 KB)
📄 TypeBasedAliasAnalysis.cpp(26.04 KB)
📄 TypeMetadataUtils.cpp(5.93 KB)
📄 VFABIDemangling.cpp(16.46 KB)
📄 ValueLattice.cpp(1.19 KB)
📄 ValueLatticeUtils.cpp(1.53 KB)
📄 ValueTracking.cpp(243.08 KB)
📄 VectorUtils.cpp(48.57 KB)
📁 models

Editing: AssumptionCache.cpp

//===- AssumptionCache.cpp - Cache finding @llvm.assume calls -------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contains a pass that keeps track of @llvm.assume intrinsics in
// the functions of a module.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/AssumeBundleQueries.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <utility>

using namespace llvm;
using namespace llvm::PatternMatch;

static cl::opt<bool>
    VerifyAssumptionCache("verify-assumption-cache", cl::Hidden,
                          cl::desc("Enable verification of assumption cache"),
                          cl::init(false));

SmallVector<AssumptionCache::ResultElem, 1> &
AssumptionCache::getOrInsertAffectedValues(Value *V) {
  // Try using find_as first to avoid creating extra value handles just for the
  // purpose of doing the lookup.
  auto AVI = AffectedValues.find_as(V);
  if (AVI != AffectedValues.end())
    return AVI->second;

auto AVIP = AffectedValues.insert(
      {AffectedValueCallbackVH(V, this), SmallVector<ResultElem, 1>()});
  return AVIP.first->second;
}

static void
findAffectedValues(CallInst *CI,
                   SmallVectorImpl<AssumptionCache::ResultElem> &Affected) {
  // Note: This code must be kept in-sync with the code in
  // computeKnownBitsFromAssume in ValueTracking.

auto AddAffected = [&Affected](Value *V, unsigned Idx =
                                               AssumptionCache::ExprResultIdx) {
    if (isa<Argument>(V)) {
      Affected.push_back({V, Idx});
    } else if (auto *I = dyn_cast<Instruction>(V)) {
      Affected.push_back({I, Idx});

// Peek through unary operators to find the source of the condition.
      Value *Op;
      if (match(I, m_BitCast(m_Value(Op))) ||
          match(I, m_PtrToInt(m_Value(Op))) || match(I, m_Not(m_Value(Op)))) {
        if (isa<Instruction>(Op) || isa<Argument>(Op))
          Affected.push_back({Op, Idx});
      }
    }
  };

for (unsigned Idx = 0; Idx != CI->getNumOperandBundles(); Idx++) {
    if (CI->getOperandBundleAt(Idx).Inputs.size() > ABA_WasOn &&
        CI->getOperandBundleAt(Idx).getTagName() != IgnoreBundleTag)
      AddAffected(CI->getOperandBundleAt(Idx).Inputs[ABA_WasOn], Idx);
  }

Value *Cond = CI->getArgOperand(0), *A, *B;
  AddAffected(Cond);

CmpInst::Predicate Pred;
  if (match(Cond, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
    AddAffected(A);
    AddAffected(B);

if (Pred == ICmpInst::ICMP_EQ) {
      // For equality comparisons, we handle the case of bit inversion.
      auto AddAffectedFromEq = [&AddAffected](Value *V) {
        Value *A;
        if (match(V, m_Not(m_Value(A)))) {
          AddAffected(A);
          V = A;
        }

Value *B;
        ConstantInt *C;
        // (A & B) or (A | B) or (A ^ B).
        if (match(V, m_BitwiseLogic(m_Value(A), m_Value(B)))) {
          AddAffected(A);
          AddAffected(B);
        // (A << C) or (A >>_s C) or (A >>_u C) where C is some constant.
        } else if (match(V, m_Shift(m_Value(A), m_ConstantInt(C)))) {
          AddAffected(A);
        }
      };

AddAffectedFromEq(A);
      AddAffectedFromEq(B);
    }
  }
}

void AssumptionCache::updateAffectedValues(CallInst *CI) {
  SmallVector<AssumptionCache::ResultElem, 16> Affected;
  findAffectedValues(CI, Affected);

for (auto &AV : Affected) {
    auto &AVV = getOrInsertAffectedValues(AV.Assume);
    if (std::find_if(AVV.begin(), AVV.end(), [&](ResultElem &Elem) {
          return Elem.Assume == CI && Elem.Index == AV.Index;
        }) == AVV.end())
      AVV.push_back({CI, AV.Index});
  }
}

void AssumptionCache::unregisterAssumption(CallInst *CI) {
  SmallVector<AssumptionCache::ResultElem, 16> Affected;
  findAffectedValues(CI, Affected);

for (auto &AV : Affected) {
    auto AVI = AffectedValues.find_as(AV.Assume);
    if (AVI == AffectedValues.end())
      continue;
    bool Found = false;
    bool HasNonnull = false;
    for (ResultElem &Elem : AVI->second) {
      if (Elem.Assume == CI) {
        Found = true;
        Elem.Assume = nullptr;
      }
      HasNonnull |= !!Elem.Assume;
      if (HasNonnull && Found)
        break;
    }
    assert(Found && "already unregistered or incorrect cache state");
    if (!HasNonnull)
      AffectedValues.erase(AVI);
  }

AssumeHandles.erase(
      remove_if(AssumeHandles, [CI](ResultElem &RE) { return CI == RE; }),
      AssumeHandles.end());
}

void AssumptionCache::AffectedValueCallbackVH::deleted() {
  auto AVI = AC->AffectedValues.find(getValPtr());
  if (AVI != AC->AffectedValues.end())
    AC->AffectedValues.erase(AVI);
  // 'this' now dangles!
}

void AssumptionCache::transferAffectedValuesInCache(Value *OV, Value *NV) {
  auto &NAVV = getOrInsertAffectedValues(NV);
  auto AVI = AffectedValues.find(OV);
  if (AVI == AffectedValues.end())
    return;

for (auto &A : AVI->second)
    if (std::find(NAVV.begin(), NAVV.end(), A) == NAVV.end())
      NAVV.push_back(A);
  AffectedValues.erase(OV);
}

void AssumptionCache::AffectedValueCallbackVH::allUsesReplacedWith(Value *NV) {
  if (!isa<Instruction>(NV) && !isa<Argument>(NV))
    return;

// Any assumptions that affected this value now affect the new value.

AC->transferAffectedValuesInCache(getValPtr(), NV);
  // 'this' now might dangle! If the AffectedValues map was resized to add an
  // entry for NV then this object might have been destroyed in favor of some
  // copy in the grown map.
}

void AssumptionCache::scanFunction() {
  assert(!Scanned && "Tried to scan the function twice!");
  assert(AssumeHandles.empty() && "Already have assumes when scanning!");

// Go through all instructions in all blocks, add all calls to @llvm.assume
  // to this cache.
  for (BasicBlock &B : F)
    for (Instruction &II : B)
      if (match(&II, m_Intrinsic<Intrinsic::assume>()))
        AssumeHandles.push_back({&II, ExprResultIdx});

// Mark the scan as complete.
  Scanned = true;

// Update affected values.
  for (auto &A : AssumeHandles)
    updateAffectedValues(cast<CallInst>(A));
}

void AssumptionCache::registerAssumption(CallInst *CI) {
  assert(match(CI, m_Intrinsic<Intrinsic::assume>()) &&
         "Registered call does not call @llvm.assume");

// If we haven't scanned the function yet, just drop this assumption. It will
  // be found when we scan later.
  if (!Scanned)
    return;

AssumeHandles.push_back({CI, ExprResultIdx});

#ifndef NDEBUG
  assert(CI->getParent() &&
         "Cannot register @llvm.assume call not in a basic block");
  assert(&F == CI->getParent()->getParent() &&
         "Cannot register @llvm.assume call not in this function");

// We expect the number of assumptions to be small, so in an asserts build
  // check that we don't accumulate duplicates and that all assumptions point
  // to the same function.
  SmallPtrSet<Value *, 16> AssumptionSet;
  for (auto &VH : AssumeHandles) {
    if (!VH)
      continue;

assert(&F == cast<Instruction>(VH)->getParent()->getParent() &&
           "Cached assumption not inside this function!");
    assert(match(cast<CallInst>(VH), m_Intrinsic<Intrinsic::assume>()) &&
           "Cached something other than a call to @llvm.assume!");
    assert(AssumptionSet.insert(VH).second &&
           "Cache contains multiple copies of a call!");
  }
#endif

updateAffectedValues(CI);
}

AnalysisKey AssumptionAnalysis::Key;

PreservedAnalyses AssumptionPrinterPass::run(Function &F,
                                             FunctionAnalysisManager &AM) {
  AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);

OS << "Cached assumptions for function: " << F.getName() << "\n";
  for (auto &VH : AC.assumptions())
    if (VH)
      OS << "  " << *cast<CallInst>(VH)->getArgOperand(0) << "\n";

return PreservedAnalyses::all();
}

void AssumptionCacheTracker::FunctionCallbackVH::deleted() {
  auto I = ACT->AssumptionCaches.find_as(cast<Function>(getValPtr()));
  if (I != ACT->AssumptionCaches.end())
    ACT->AssumptionCaches.erase(I);
  // 'this' now dangles!
}

AssumptionCache &AssumptionCacheTracker::getAssumptionCache(Function &F) {
  // We probe the function map twice to try and avoid creating a value handle
  // around the function in common cases. This makes insertion a bit slower,
  // but if we have to insert we're going to scan the whole function so that
  // shouldn't matter.
  auto I = AssumptionCaches.find_as(&F);
  if (I != AssumptionCaches.end())
    return *I->second;

// Ok, build a new cache by scanning the function, insert it and the value
  // handle into our map, and return the newly populated cache.
  auto IP = AssumptionCaches.insert(std::make_pair(
      FunctionCallbackVH(&F, this), std::make_unique<AssumptionCache>(F)));
  assert(IP.second && "Scanning function already in the map?");
  return *IP.first->second;
}

AssumptionCache *AssumptionCacheTracker::lookupAssumptionCache(Function &F) {
  auto I = AssumptionCaches.find_as(&F);
  if (I != AssumptionCaches.end())
    return I->second.get();
  return nullptr;
}

void AssumptionCacheTracker::verifyAnalysis() const {
  // FIXME: In the long term the verifier should not be controllable with a
  // flag. We should either fix all passes to correctly update the assumption
  // cache and enable the verifier unconditionally or somehow arrange for the
  // assumption list to be updated automatically by passes.
  if (!VerifyAssumptionCache)
    return;

SmallPtrSet<const CallInst *, 4> AssumptionSet;
  for (const auto &I : AssumptionCaches) {
    for (auto &VH : I.second->assumptions())
      if (VH)
        AssumptionSet.insert(cast<CallInst>(VH));

for (const BasicBlock &B : cast<Function>(*I.first))
      for (const Instruction &II : B)
        if (match(&II, m_Intrinsic<Intrinsic::assume>()) &&
            !AssumptionSet.count(cast<CallInst>(&II)))
          report_fatal_error("Assumption in scanned function not in cache");
  }
}

AssumptionCacheTracker::AssumptionCacheTracker() : ImmutablePass(ID) {
  initializeAssumptionCacheTrackerPass(*PassRegistry::getPassRegistry());
}

AssumptionCacheTracker::~AssumptionCacheTracker() = default;

char AssumptionCacheTracker::ID = 0;

INITIALIZE_PASS(AssumptionCacheTracker, "assumption-cache-tracker",
                "Assumption Cache Tracker", false, true)

003 File Manager

Editing: AssumptionCache.cpp

Upload File

Create Folder