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: CFLSteensAliasAnalysis.cpp

//===- CFLSteensAliasAnalysis.cpp - Unification-based Alias Analysis ------===//
//
// 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 implements a CFL-base, summary-based alias analysis algorithm. It
// does not depend on types. The algorithm is a mixture of the one described in
// "Demand-driven alias analysis for C" by Xin Zheng and Radu Rugina, and "Fast
// algorithms for Dyck-CFL-reachability with applications to Alias Analysis" by
// Zhang Q, Lyu M R, Yuan H, and Su Z. -- to summarize the papers, we build a
// graph of the uses of a variable, where each node is a memory location, and
// each edge is an action that happened on that memory location.  The "actions"
// can be one of Dereference, Reference, or Assign. The precision of this
// analysis is roughly the same as that of an one level context-sensitive
// Steensgaard's algorithm.
//
// Two variables are considered as aliasing iff you can reach one value's node
// from the other value's node and the language formed by concatenating all of
// the edge labels (actions) conforms to a context-free grammar.
//
// Because this algorithm requires a graph search on each query, we execute the
// algorithm outlined in "Fast algorithms..." (mentioned above)
// in order to transform the graph into sets of variables that may alias in
// ~nlogn time (n = number of variables), which makes queries take constant
// time.
//===----------------------------------------------------------------------===//

// N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
// CFLSteensAA is interprocedural. This is *technically* A Bad Thing, because
// FunctionPasses are only allowed to inspect the Function that they're being
// run on. Realistically, this likely isn't a problem until we allow
// FunctionPasses to run concurrently.

#include "llvm/Analysis/CFLSteensAliasAnalysis.h"
#include "AliasAnalysisSummary.h"
#include "CFLGraph.h"
#include "StratifiedSets.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <limits>
#include <memory>
#include <utility>

using namespace llvm;
using namespace llvm::cflaa;

#define DEBUG_TYPE "cfl-steens-aa"

CFLSteensAAResult::CFLSteensAAResult(
    std::function<const TargetLibraryInfo &(Function &F)> GetTLI)
    : AAResultBase(), GetTLI(std::move(GetTLI)) {}
CFLSteensAAResult::CFLSteensAAResult(CFLSteensAAResult &&Arg)
    : AAResultBase(std::move(Arg)), GetTLI(std::move(Arg.GetTLI)) {}
CFLSteensAAResult::~CFLSteensAAResult() = default;

/// Information we have about a function and would like to keep around.
class CFLSteensAAResult::FunctionInfo {
  StratifiedSets<InstantiatedValue> Sets;
  AliasSummary Summary;

public:
  FunctionInfo(Function &Fn, const SmallVectorImpl<Value *> &RetVals,
               StratifiedSets<InstantiatedValue> S);

const StratifiedSets<InstantiatedValue> &getStratifiedSets() const {
    return Sets;
  }

const AliasSummary &getAliasSummary() const { return Summary; }
};

const StratifiedIndex StratifiedLink::SetSentinel =
    std::numeric_limits<StratifiedIndex>::max();

//===----------------------------------------------------------------------===//
// Function declarations that require types defined in the namespace above
//===----------------------------------------------------------------------===//

/// Determines whether it would be pointless to add the given Value to our sets.
static bool canSkipAddingToSets(Value *Val) {
  // Constants can share instances, which may falsely unify multiple
  // sets, e.g. in
  // store i32* null, i32** %ptr1
  // store i32* null, i32** %ptr2
  // clearly ptr1 and ptr2 should not be unified into the same set, so
  // we should filter out the (potentially shared) instance to
  // i32* null.
  if (isa<Constant>(Val)) {
    // TODO: Because all of these things are constant, we can determine whether
    // the data is *actually* mutable at graph building time. This will probably
    // come for free/cheap with offset awareness.
    bool CanStoreMutableData = isa<GlobalValue>(Val) ||
                               isa<ConstantExpr>(Val) ||
                               isa<ConstantAggregate>(Val);
    return !CanStoreMutableData;
  }

return false;
}

CFLSteensAAResult::FunctionInfo::FunctionInfo(
    Function &Fn, const SmallVectorImpl<Value *> &RetVals,
    StratifiedSets<InstantiatedValue> S)
    : Sets(std::move(S)) {
  // Historically, an arbitrary upper-bound of 50 args was selected. We may want
  // to remove this if it doesn't really matter in practice.
  if (Fn.arg_size() > MaxSupportedArgsInSummary)
    return;

DenseMap<StratifiedIndex, InterfaceValue> InterfaceMap;

// Our intention here is to record all InterfaceValues that share the same
  // StratifiedIndex in RetParamRelations. For each valid InterfaceValue, we
  // have its StratifiedIndex scanned here and check if the index is presented
  // in InterfaceMap: if it is not, we add the correspondence to the map;
  // otherwise, an aliasing relation is found and we add it to
  // RetParamRelations.

auto AddToRetParamRelations = [&](unsigned InterfaceIndex,
                                    StratifiedIndex SetIndex) {
    unsigned Level = 0;
    while (true) {
      InterfaceValue CurrValue{InterfaceIndex, Level};

auto Itr = InterfaceMap.find(SetIndex);
      if (Itr != InterfaceMap.end()) {
        if (CurrValue != Itr->second)
          Summary.RetParamRelations.push_back(
              ExternalRelation{CurrValue, Itr->second, UnknownOffset});
        break;
      }

auto &Link = Sets.getLink(SetIndex);
      InterfaceMap.insert(std::make_pair(SetIndex, CurrValue));
      auto ExternalAttrs = getExternallyVisibleAttrs(Link.Attrs);
      if (ExternalAttrs.any())
        Summary.RetParamAttributes.push_back(
            ExternalAttribute{CurrValue, ExternalAttrs});

if (!Link.hasBelow())
        break;

++Level;
      SetIndex = Link.Below;
    }
  };

// Populate RetParamRelations for return values
  for (auto *RetVal : RetVals) {
    assert(RetVal != nullptr);
    assert(RetVal->getType()->isPointerTy());
    auto RetInfo = Sets.find(InstantiatedValue{RetVal, 0});
    if (RetInfo.hasValue())
      AddToRetParamRelations(0, RetInfo->Index);
  }

// Populate RetParamRelations for parameters
  unsigned I = 0;
  for (auto &Param : Fn.args()) {
    if (Param.getType()->isPointerTy()) {
      auto ParamInfo = Sets.find(InstantiatedValue{&Param, 0});
      if (ParamInfo.hasValue())
        AddToRetParamRelations(I + 1, ParamInfo->Index);
    }
    ++I;
  }
}

// Builds the graph + StratifiedSets for a function.
CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) {
  CFLGraphBuilder<CFLSteensAAResult> GraphBuilder(*this, GetTLI(*Fn), *Fn);
  StratifiedSetsBuilder<InstantiatedValue> SetBuilder;

// Add all CFLGraph nodes and all Dereference edges to StratifiedSets
  auto &Graph = GraphBuilder.getCFLGraph();
  for (const auto &Mapping : Graph.value_mappings()) {
    auto Val = Mapping.first;
    if (canSkipAddingToSets(Val))
      continue;
    auto &ValueInfo = Mapping.second;

assert(ValueInfo.getNumLevels() > 0);
    SetBuilder.add(InstantiatedValue{Val, 0});
    SetBuilder.noteAttributes(InstantiatedValue{Val, 0},
                              ValueInfo.getNodeInfoAtLevel(0).Attr);
    for (unsigned I = 0, E = ValueInfo.getNumLevels() - 1; I < E; ++I) {
      SetBuilder.add(InstantiatedValue{Val, I + 1});
      SetBuilder.noteAttributes(InstantiatedValue{Val, I + 1},
                                ValueInfo.getNodeInfoAtLevel(I + 1).Attr);
      SetBuilder.addBelow(InstantiatedValue{Val, I},
                          InstantiatedValue{Val, I + 1});
    }
  }

// Add all assign edges to StratifiedSets
  for (const auto &Mapping : Graph.value_mappings()) {
    auto Val = Mapping.first;
    if (canSkipAddingToSets(Val))
      continue;
    auto &ValueInfo = Mapping.second;

for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
      auto Src = InstantiatedValue{Val, I};
      for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges)
        SetBuilder.addWith(Src, Edge.Other);
    }
  }

return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build());
}

void CFLSteensAAResult::scan(Function *Fn) {
  auto InsertPair = Cache.insert(std::make_pair(Fn, Optional<FunctionInfo>()));
  (void)InsertPair;
  assert(InsertPair.second &&
         "Trying to scan a function that has already been cached");

// Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
  // may get evaluated after operator[], potentially triggering a DenseMap
  // resize and invalidating the reference returned by operator[]
  auto FunInfo = buildSetsFrom(Fn);
  Cache[Fn] = std::move(FunInfo);

Handles.emplace_front(Fn, this);
}

void CFLSteensAAResult::evict(Function *Fn) { Cache.erase(Fn); }

/// Ensures that the given function is available in the cache, and returns the
/// entry.
const Optional<CFLSteensAAResult::FunctionInfo> &
CFLSteensAAResult::ensureCached(Function *Fn) {
  auto Iter = Cache.find(Fn);
  if (Iter == Cache.end()) {
    scan(Fn);
    Iter = Cache.find(Fn);
    assert(Iter != Cache.end());
    assert(Iter->second.hasValue());
  }
  return Iter->second;
}

const AliasSummary *CFLSteensAAResult::getAliasSummary(Function &Fn) {
  auto &FunInfo = ensureCached(&Fn);
  if (FunInfo.hasValue())
    return &FunInfo->getAliasSummary();
  else
    return nullptr;
}

AliasResult CFLSteensAAResult::query(const MemoryLocation &LocA,
                                     const MemoryLocation &LocB) {
  auto *ValA = const_cast<Value *>(LocA.Ptr);
  auto *ValB = const_cast<Value *>(LocB.Ptr);

if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
    return NoAlias;

Function *Fn = nullptr;
  Function *MaybeFnA = const_cast<Function *>(parentFunctionOfValue(ValA));
  Function *MaybeFnB = const_cast<Function *>(parentFunctionOfValue(ValB));
  if (!MaybeFnA && !MaybeFnB) {
    // The only times this is known to happen are when globals + InlineAsm are
    // involved
    LLVM_DEBUG(
        dbgs()
        << "CFLSteensAA: could not extract parent function information.\n");
    return MayAlias;
  }

if (MaybeFnA) {
    Fn = MaybeFnA;
    assert((!MaybeFnB || MaybeFnB == MaybeFnA) &&
           "Interprocedural queries not supported");
  } else {
    Fn = MaybeFnB;
  }

assert(Fn != nullptr);
  auto &MaybeInfo = ensureCached(Fn);
  assert(MaybeInfo.hasValue());

auto &Sets = MaybeInfo->getStratifiedSets();
  auto MaybeA = Sets.find(InstantiatedValue{ValA, 0});
  if (!MaybeA.hasValue())
    return MayAlias;

auto MaybeB = Sets.find(InstantiatedValue{ValB, 0});
  if (!MaybeB.hasValue())
    return MayAlias;

auto SetA = *MaybeA;
  auto SetB = *MaybeB;
  auto AttrsA = Sets.getLink(SetA.Index).Attrs;
  auto AttrsB = Sets.getLink(SetB.Index).Attrs;

// If both values are local (meaning the corresponding set has attribute
  // AttrNone or AttrEscaped), then we know that CFLSteensAA fully models them:
  // they may-alias each other if and only if they are in the same set.
  // If at least one value is non-local (meaning it either is global/argument or
  // it comes from unknown sources like integer cast), the situation becomes a
  // bit more interesting. We follow three general rules described below:
  // - Non-local values may alias each other
  // - AttrNone values do not alias any non-local values
  // - AttrEscaped do not alias globals/arguments, but they may alias
  // AttrUnknown values
  if (SetA.Index == SetB.Index)
    return MayAlias;
  if (AttrsA.none() || AttrsB.none())
    return NoAlias;
  if (hasUnknownOrCallerAttr(AttrsA) || hasUnknownOrCallerAttr(AttrsB))
    return MayAlias;
  if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB))
    return MayAlias;
  return NoAlias;
}

AnalysisKey CFLSteensAA::Key;

CFLSteensAAResult CFLSteensAA::run(Function &F, FunctionAnalysisManager &AM) {
  auto GetTLI = [&AM](Function &F) -> const TargetLibraryInfo & {
    return AM.getResult<TargetLibraryAnalysis>(F);
  };
  return CFLSteensAAResult(GetTLI);
}

char CFLSteensAAWrapperPass::ID = 0;
INITIALIZE_PASS(CFLSteensAAWrapperPass, "cfl-steens-aa",
                "Unification-Based CFL Alias Analysis", false, true)

ImmutablePass *llvm::createCFLSteensAAWrapperPass() {
  return new CFLSteensAAWrapperPass();
}

CFLSteensAAWrapperPass::CFLSteensAAWrapperPass() : ImmutablePass(ID) {
  initializeCFLSteensAAWrapperPassPass(*PassRegistry::getPassRegistry());
}

void CFLSteensAAWrapperPass::initializePass() {
  auto GetTLI = [this](Function &F) -> const TargetLibraryInfo & {
    return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
  };
  Result.reset(new CFLSteensAAResult(GetTLI));
}

void CFLSteensAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.setPreservesAll();
  AU.addRequired<TargetLibraryInfoWrapperPass>();
}

003 File Manager

Editing: CFLSteensAliasAnalysis.cpp

Upload File

Create Folder