90 #define DEBUG_TYPE "cfl-anders-aa" 101 FlowFromReadOnly = 0,
107 FlowFromMemAliasNoReadWrite,
108 FlowFromMemAliasReadOnly,
120 FlowToMemAliasWriteOnly,
121 FlowToMemAliasReadWrite,
124 using StateSet = std::bitset<7>;
126 const unsigned ReadOnlyStateMask =
127 (1U << static_cast<uint8_t>(MatchState::FlowFromReadOnly)) |
128 (1U << static_cast<uint8_t>(MatchState::FlowFromMemAliasReadOnly));
129 const unsigned WriteOnlyStateMask =
130 (1U << static_cast<uint8_t>(MatchState::FlowToWriteOnly)) |
131 (1U << static_cast<uint8_t>(MatchState::FlowToMemAliasWriteOnly));
139 bool operator==(OffsetValue LHS, OffsetValue RHS) {
140 return LHS.Val == RHS.Val && LHS.Offset == RHS.Offset;
142 bool operator<(OffsetValue LHS, OffsetValue RHS) {
143 return std::less<const Value *>()(LHS.Val, RHS.Val) ||
144 (LHS.Val == RHS.Val && LHS.Offset < RHS.Offset);
148 struct OffsetInstantiatedValue {
153 bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) {
154 return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset;
159 class ReachabilitySet {
163 ValueReachMap ReachMap;
166 using const_valuestate_iterator = ValueStateMap::const_iterator;
167 using const_value_iterator = ValueReachMap::const_iterator;
172 auto &States = ReachMap[To][
From];
173 auto Idx =
static_cast<size_t>(State);
174 if (!States.test(Idx)) {
184 auto Itr = ReachMap.find(V);
185 if (Itr == ReachMap.end())
186 return make_range<const_valuestate_iterator>(const_valuestate_iterator(),
187 const_valuestate_iterator());
188 return make_range<const_valuestate_iterator>(Itr->second.begin(),
193 return make_range<const_value_iterator>(ReachMap.begin(), ReachMap.end());
206 using const_mem_iterator = MemSet::const_iterator;
212 return MemMap[LHS].insert(RHS).second;
216 auto Itr = MemMap.find(V);
217 if (Itr == MemMap.end())
230 using const_iterator = MapType::const_iterator;
233 auto &OldAttr = AttrMap[V];
234 auto NewAttr = OldAttr | Attr;
235 if (OldAttr == NewAttr)
243 auto Itr = AttrMap.find(V);
244 if (Itr != AttrMap.end())
250 return make_range<const_iterator>(AttrMap.begin(), AttrMap.end());
254 struct WorkListItem {
260 struct ValueSummary {
286 std::make_pair(OVal.Val, OVal.Offset));
289 static bool isEqual(
const OffsetValue &LHS,
const OffsetValue &RHS) {
297 return OffsetInstantiatedValue{
303 return OffsetInstantiatedValue{
310 std::make_pair(OVal.IVal, OVal.Offset));
313 static bool isEqual(
const OffsetInstantiatedValue &LHS,
314 const OffsetInstantiatedValue &RHS) {
338 const ReachabilitySet &,
const AliasAttrMap &);
345 return (Set & StateSet(ReadOnlyStateMask)).any();
349 return (Set & StateSet(WriteOnlyStateMask)).any();
355 auto Val = IValue.
Val;
358 if (
auto Arg = dyn_cast<Argument>(Val))
359 Index =
Arg->getArgNo() + 1;
369 const AliasAttrMap &AMap) {
370 for (
const auto &Mapping : AMap.mappings()) {
371 auto IVal = Mapping.first;
374 auto &Attr = AttrMap[IVal.Val];
376 if (IVal.DerefLevel == 0)
377 Attr |= Mapping.second;
383 const ReachabilitySet &ReachSet) {
384 for (
const auto &OuterMapping : ReachSet.value_mappings()) {
386 if (OuterMapping.first.DerefLevel > 0)
389 auto Val = OuterMapping.first.Val;
390 auto &AliasList = AliasMap[Val];
391 for (
const auto &InnerMapping : OuterMapping.second) {
393 if (InnerMapping.first.DerefLevel == 0)
394 AliasList.push_back(OffsetValue{InnerMapping.first.Val,
UnknownOffset});
408 for (
const auto &
Arg : Fn.
args()) {
430 for (
const auto &OuterMapping : ReachSet.value_mappings()) {
432 for (
const auto &InnerMapping : OuterMapping.second) {
444 auto SrcIVal = InnerMapping.first;
446 ValueMap[SrcIVal.Val].FromRecords.push_back(
447 ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
449 ValueMap[SrcIVal.Val].ToRecords.push_back(
450 ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
456 for (
const auto &Mapping : ValueMap) {
457 for (
const auto &FromRecord : Mapping.second.FromRecords) {
458 for (
const auto &ToRecord : Mapping.second.ToRecords) {
459 auto ToLevel = ToRecord.DerefLevel;
460 auto FromLevel = FromRecord.DerefLevel;
462 if (ToLevel == FromLevel)
465 auto SrcIndex = FromRecord.IValue.Index;
466 auto SrcLevel = FromRecord.IValue.DerefLevel;
467 auto DstIndex = ToRecord.IValue.Index;
468 auto DstLevel = ToRecord.IValue.DerefLevel;
469 if (ToLevel > FromLevel)
470 SrcLevel += ToLevel - FromLevel;
472 DstLevel += FromLevel - ToLevel;
483 ExtRelations.
erase(std::unique(ExtRelations.
begin(), ExtRelations.
end()),
490 for (
const auto &Mapping : AMap.mappings()) {
501 const ReachabilitySet &ReachSet,
const AliasAttrMap &AMap) {
509 CFLAndersAAResult::FunctionInfo::getAttrs(
const Value *V)
const {
512 auto Itr = AttrMap.find(V);
513 if (Itr != AttrMap.end())
526 auto MaybeAttrsA = getAttrs(LHS);
527 auto MaybeAttrsB = getAttrs(RHS);
528 if (!MaybeAttrsA || !MaybeAttrsB)
532 auto AttrsA = *MaybeAttrsA;
533 auto AttrsB = *MaybeAttrsB;
545 auto Itr = AliasMap.find(LHS);
546 if (Itr != AliasMap.end()) {
549 auto Comparator = [](OffsetValue LHS, OffsetValue RHS) {
550 return std::less<const Value *>()(LHS.Val, RHS.Val);
552 #ifdef EXPENSIVE_CHECKS 553 assert(std::is_sorted(Itr->second.begin(), Itr->second.end(), Comparator));
555 auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(),
556 OffsetValue{RHS, 0}, Comparator);
558 if (RangePair.first != RangePair.second) {
564 const uint64_t LHSSize = MaybeLHSSize.
getValue();
565 const uint64_t RHSSize = MaybeRHSSize.
getValue();
567 for (
const auto &OVal :
make_range(RangePair)) {
581 auto LHSStart = OVal.Offset;
583 auto LHSEnd = OVal.Offset +
static_cast<int64_t
>(LHSSize);
585 auto RHSEnd =
static_cast<int64_t
>(RHSSize);
586 if (LHSEnd > RHSStart && LHSStart < RHSEnd)
597 std::vector<WorkListItem> &WorkList) {
600 if (ReachSet.insert(From, To, State))
601 WorkList.push_back(WorkListItem{From, To, State});
605 ReachabilitySet &ReachSet,
608 auto Val = Mapping.first;
617 for (
auto &Edge :
ValueInfo.getNodeInfoAtLevel(I).Edges) {
618 propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet,
620 propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet,
630 if (Graph.getNode(NodeBelow))
636 ReachabilitySet &ReachSet, AliasMemSet &MemSet,
637 std::vector<WorkListItem> &WorkList) {
638 auto FromNode = Item.From;
639 auto ToNode = Item.To;
641 auto NodeInfo = Graph.getNode(ToNode);
642 assert(NodeInfo !=
nullptr);
654 if (FromNodeBelow && ToNodeBelow &&
655 MemSet.insert(*FromNodeBelow, *ToNodeBelow)) {
657 MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList);
658 for (
const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) {
659 auto Src = Mapping.first;
661 if (Mapping.second.test(static_cast<size_t>(FromState)))
662 propagate(Src, *ToNodeBelow, ToState, ReachSet, WorkList);
665 MemAliasPropagate(MatchState::FlowFromReadOnly,
666 MatchState::FlowFromMemAliasReadOnly);
667 MemAliasPropagate(MatchState::FlowToWriteOnly,
668 MatchState::FlowToMemAliasWriteOnly);
669 MemAliasPropagate(MatchState::FlowToReadWrite,
670 MatchState::FlowToMemAliasReadWrite);
682 auto NextAssignState = [&](
MatchState State) {
683 for (
const auto &AssignEdge : NodeInfo->Edges)
684 propagate(FromNode, AssignEdge.Other, State, ReachSet, WorkList);
686 auto NextRevAssignState = [&](
MatchState State) {
687 for (
const auto &RevAssignEdge : NodeInfo->ReverseEdges)
688 propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList);
691 if (
auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
692 for (
const auto &MemAlias : *
AliasSet)
693 propagate(FromNode, MemAlias, State, ReachSet, WorkList);
697 switch (Item.State) {
698 case MatchState::FlowFromReadOnly:
699 NextRevAssignState(MatchState::FlowFromReadOnly);
700 NextAssignState(MatchState::FlowToReadWrite);
701 NextMemState(MatchState::FlowFromMemAliasReadOnly);
704 case MatchState::FlowFromMemAliasNoReadWrite:
705 NextRevAssignState(MatchState::FlowFromReadOnly);
706 NextAssignState(MatchState::FlowToWriteOnly);
709 case MatchState::FlowFromMemAliasReadOnly:
710 NextRevAssignState(MatchState::FlowFromReadOnly);
711 NextAssignState(MatchState::FlowToReadWrite);
714 case MatchState::FlowToWriteOnly:
715 NextAssignState(MatchState::FlowToWriteOnly);
716 NextMemState(MatchState::FlowToMemAliasWriteOnly);
719 case MatchState::FlowToReadWrite:
720 NextAssignState(MatchState::FlowToReadWrite);
721 NextMemState(MatchState::FlowToMemAliasReadWrite);
724 case MatchState::FlowToMemAliasWriteOnly:
725 NextAssignState(MatchState::FlowToWriteOnly);
728 case MatchState::FlowToMemAliasReadWrite:
729 NextAssignState(MatchState::FlowToReadWrite);
735 const ReachabilitySet &ReachSet) {
736 AliasAttrMap AttrMap;
737 std::vector<InstantiatedValue> WorkList, NextList;
741 auto Val = Mapping.first;
745 AttrMap.add(Node,
ValueInfo.getNodeInfoAtLevel(I).Attr);
746 WorkList.push_back(Node);
750 while (!WorkList.empty()) {
751 for (
const auto &Dst : WorkList) {
752 auto DstAttr = AttrMap.getAttrs(Dst);
757 for (
const auto &Mapping : ReachSet.reachableValueAliases(Dst)) {
758 auto Src = Mapping.first;
759 if (AttrMap.add(Src, DstAttr))
760 NextList.push_back(Src);
766 if (AttrMap.add(*DstBelow, DstAttr)) {
767 NextList.push_back(*DstBelow);
773 WorkList.swap(NextList);
781 CFLAndersAAResult::buildInfoFrom(
const Function &Fn) {
785 const_cast<Function &>(Fn));
788 ReachabilitySet ReachSet;
791 std::vector<WorkListItem> WorkList, NextList;
794 while (!WorkList.empty()) {
795 for (
const auto &Item : WorkList)
798 NextList.swap(WorkList);
807 std::move(IValueAttrMap));
810 void CFLAndersAAResult::scan(
const Function &Fn) {
813 assert(InsertPair.second &&
814 "Trying to scan a function that has already been cached");
819 auto FunInfo = buildInfoFrom(Fn);
820 Cache[&Fn] = std::move(FunInfo);
821 Handles.emplace_front(const_cast<Function *>(&Fn),
this);
827 CFLAndersAAResult::ensureCached(
const Function &Fn) {
828 auto Iter = Cache.find(&Fn);
829 if (Iter == Cache.end()) {
831 Iter = Cache.find(&Fn);
832 assert(Iter != Cache.end());
833 assert(Iter->second.hasValue());
839 auto &FunInfo = ensureCached(Fn);
840 if (FunInfo.hasValue())
841 return &FunInfo->getAliasSummary();
848 auto *ValA = LocA.
Ptr;
849 auto *ValB = LocB.
Ptr;
851 if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
862 <<
"CFLAndersAA: could not extract parent function information.\n");
870 auto &FunInfo = ensureCached(*Fn);
873 if (FunInfo->mayAlias(ValA, LocA.
Size, ValB, LocB.
Size))
888 if (isa<Constant>(LocA.
Ptr) && isa<Constant>(LocB.
Ptr))
906 "Inclusion-Based CFL Alias Analysis",
false,
true)
917 auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
static void populateExternalAttributes(SmallVectorImpl< ExternalAttribute > &ExtAttributes, const Function &Fn, const SmallVectorImpl< Value *> &RetVals, const AliasAttrMap &AMap)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
void evict(const Function *Fn)
Evict the given function from cache.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
This is the interface for LLVM's inclusion-based alias analysis implemented with CFL graph reachabili...
This class represents lattice values for constants.
static OffsetInstantiatedValue getEmptyKey()
We use ExternalRelation to describe an externally visible aliasing relations between parameters/retur...
static void populateAliasMap(DenseMap< const Value *, std::vector< OffsetValue >> &AliasMap, const ReachabilitySet &ReachSet)
static bool mayAlias(MachineInstr &MIa, MachineInstr &MIb, AliasAnalysis *AA)
static constexpr LocationSize unknown()
Implements a dense probed hash-table based set.
void push_back(const T &Elt)
This is the result of instantiating InterfaceValue at a particular callsite.
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
void initializeCFLAndersAAWrapperPassPass(PassRegistry &)
void initializePass() override
initializePass - This method may be overriden by immutable passes to allow them to perform various in...
The Program Expression Graph (PEG) of CFL analysis CFLGraph is auxiliary data structure used by CFL-b...
The two locations do not alias at all.
static OffsetValue getTombstoneKey()
static void populateAttrMap(DenseMap< const Value *, AliasAttrs > &AttrMap, const AliasAttrMap &AMap)
We use ExternalAttribute to describe an externally visible AliasAttrs for parameters/return value...
#define LLVM_UNLIKELY(EXPR)
We use InterfaceValue to describe parameters/return value, as well as potential memory locations that...
AnalysisUsage & addRequired()
static AliasAttrMap buildAttrMap(const CFLGraph &Graph, const ReachabilitySet &ReachSet)
FunctionInfo(const Function &, const SmallVectorImpl< Value *> &, const ReachabilitySet &, const AliasAttrMap &)
static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS)
CFLAndersAAResult(const TargetLibraryInfo &TLI)
const cflaa::AliasSummary * getAliasSummary(const Function &)
Get the alias summary for the given function Return nullptr if the summary is not found or not availa...
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
static bool isEqual(const OffsetInstantiatedValue &LHS, const OffsetInstantiatedValue &RHS)
static OffsetValue getEmptyKey()
AliasResult
The possible results of an alias query.
uint64_t getValue() const
static unsigned getHashValue(const OffsetInstantiatedValue &OVal)
AliasResult query(const MemoryLocation &, const MemoryLocation &)
static OffsetInstantiatedValue getTombstoneKey()
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
static bool hasWriteOnlyState(StateSet Set)
Legacy wrapper pass to provide the CFLAndersAAResult object.
static void populateExternalRelations(SmallVectorImpl< ExternalRelation > &ExtRelations, const Function &Fn, const SmallVectorImpl< Value *> &RetVals, const ReachabilitySet &ReachSet)
Represent the analysis usage information of a pass.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known...
const SmallVector< Value *, 4 > & getReturnValues() const
bool isGlobalOrArgAttr(AliasAttrs Attr)
iterator erase(const_iterator CI)
void sort(IteratorTy Start, IteratorTy End)
Struct that holds a reference to a particular GUID in a global value summary.
The two locations may or may not alias. This is the least precise result.
const Value * Ptr
The address of the start of the location.
Representation for a specific memory location.
The two locations precisely alias each other.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
ImmutablePass class - This class is used to provide information that does not need to be run...
BlockVerifier::State From
static void initializeWorkList(std::vector< WorkListItem > &WorkList, ReachabilitySet &ReachSet, const CFLGraph &Graph)
INITIALIZE_PASS(CFLAndersAAWrapperPass, "cfl-anders-aa", "Inclusion-Based CFL Alias Analysis", false, true) ImmutablePass *llvm
AliasAttrs getExternallyVisibleAttrs(AliasAttrs Attr)
Given an AliasAttrs, return a new AliasAttrs that only contains attributes meaningful to the caller...
A builder class used to create CFLGraph instance from a given function The CFL-AA that uses this buil...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Provides information about what library functions are available for the current target.
iterator_range< const_value_iterator > value_mappings() const
Alias summary information.
This file defines various utility types and functions useful to summary-based alias analysis...
static Optional< InterfaceValue > getInterfaceValue(InstantiatedValue IValue, const SmallVectorImpl< Value *> &RetVals)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
A range adaptor for a pair of iterators.
void setPreservesAll()
Set by analyses that do not transform their input at all.
This file defines CFLGraph, an auxiliary data structure used by CFL-based alias analysis.
static void propagate(InstantiatedValue From, InstantiatedValue To, MatchState State, ReachabilitySet &ReachSet, std::vector< WorkListItem > &WorkList)
amdgpu Simplify well known AMD library false Value Value * Arg
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
static const int64_t UnknownOffset
This file provides utility analysis objects describing memory locations.
static Optional< InstantiatedValue > getNodeBelow(const CFLGraph &Graph, InstantiatedValue V)
static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph, ReachabilitySet &ReachSet, AliasMemSet &MemSet, std::vector< WorkListItem > &WorkList)
bool hasUnknownOrCallerAttr(AliasAttrs Attr)
std::bitset< NumAliasAttrs > AliasAttrs
These are attributes that an alias analysis can use to mark certain special properties of a given poi...
static bool hasReadOnlyState(StateSet Set)
const AliasSummary & getAliasSummary() const
Analysis pass providing the TargetLibraryInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
CFLAndersAAResult run(Function &F, FunctionAnalysisManager &AM)
static const Function * parentFunctionOfValue(const Value *Val)
bool operator<(int64_t V1, const APSInt &V2)
LLVM Value Representation.
const CFLGraph & getCFLGraph() const
A container for analyses that lazily runs them and caches their results.
AliasResult alias(const MemoryLocation &, const MemoryLocation &)
bool operator==(uint64_t V1, const APInt &V2)
ImmutablePass * createCFLAndersAAWrapperPass()
bool mayAlias(const Value *, LocationSize, const Value *, LocationSize) const
static unsigned getHashValue(const OffsetValue &OVal)
This header defines various interfaces for pass management in LLVM.
A special type used by analysis passes to provide an address that identifies that particular analysis...
iterator_range< arg_iterator > args()
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.