90 #define DEBUG_TYPE "cfl-anders-aa" 103 FlowFromReadOnly = 0,
109 FlowFromMemAliasNoReadWrite,
110 FlowFromMemAliasReadOnly,
122 FlowToMemAliasWriteOnly,
123 FlowToMemAliasReadWrite,
126 using StateSet = std::bitset<7>;
128 const unsigned ReadOnlyStateMask =
129 (1U << static_cast<uint8_t>(MatchState::FlowFromReadOnly)) |
130 (1U << static_cast<uint8_t>(MatchState::FlowFromMemAliasReadOnly));
131 const unsigned WriteOnlyStateMask =
132 (1U << static_cast<uint8_t>(MatchState::FlowToWriteOnly)) |
133 (1U << static_cast<uint8_t>(MatchState::FlowToMemAliasWriteOnly));
141 bool operator==(OffsetValue LHS, OffsetValue RHS) {
142 return LHS.Val == RHS.Val && LHS.Offset == RHS.Offset;
144 bool operator<(OffsetValue LHS, OffsetValue RHS) {
145 return std::less<const Value *>()(LHS.Val, RHS.Val) ||
146 (LHS.Val == RHS.Val && LHS.Offset < RHS.Offset);
150 struct OffsetInstantiatedValue {
155 bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) {
156 return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset;
161 class ReachabilitySet {
165 ValueReachMap ReachMap;
168 using const_valuestate_iterator = ValueStateMap::const_iterator;
169 using const_value_iterator = ValueReachMap::const_iterator;
174 auto &States = ReachMap[To][
From];
175 auto Idx = static_cast<size_t>(State);
176 if (!States.test(Idx)) {
186 auto Itr = ReachMap.find(V);
187 if (Itr == ReachMap.end())
188 return make_range<const_valuestate_iterator>(const_valuestate_iterator(),
189 const_valuestate_iterator());
190 return make_range<const_valuestate_iterator>(Itr->second.begin(),
195 return make_range<const_value_iterator>(ReachMap.begin(), ReachMap.end());
208 using const_mem_iterator = MemSet::const_iterator;
214 return MemMap[LHS].insert(RHS).second;
218 auto Itr = MemMap.find(V);
219 if (Itr == MemMap.end())
232 using const_iterator = MapType::const_iterator;
235 auto &OldAttr = AttrMap[V];
236 auto NewAttr = OldAttr | Attr;
237 if (OldAttr == NewAttr)
245 auto Itr = AttrMap.find(V);
246 if (Itr != AttrMap.end())
252 return make_range<const_iterator>(AttrMap.begin(), AttrMap.end());
256 struct WorkListItem {
262 struct ValueSummary {
288 std::make_pair(OVal.Val, OVal.Offset));
291 static bool isEqual(
const OffsetValue &LHS,
const OffsetValue &RHS) {
299 return OffsetInstantiatedValue{
305 return OffsetInstantiatedValue{
312 std::make_pair(OVal.IVal, OVal.Offset));
315 static bool isEqual(
const OffsetInstantiatedValue &LHS,
316 const OffsetInstantiatedValue &RHS) {
340 const ReachabilitySet &,
const AliasAttrMap &);
347 return (Set & StateSet(ReadOnlyStateMask)).any();
351 return (Set & StateSet(WriteOnlyStateMask)).any();
357 auto Val = IValue.
Val;
360 if (
auto Arg = dyn_cast<Argument>(Val))
371 const AliasAttrMap &AMap) {
372 for (
const auto &Mapping : AMap.mappings()) {
373 auto IVal = Mapping.first;
376 auto &Attr = AttrMap[IVal.Val];
378 if (IVal.DerefLevel == 0)
379 Attr |= Mapping.second;
385 const ReachabilitySet &ReachSet) {
386 for (
const auto &OuterMapping : ReachSet.value_mappings()) {
388 if (OuterMapping.first.DerefLevel > 0)
391 auto Val = OuterMapping.first.Val;
392 auto &AliasList = AliasMap[Val];
393 for (
const auto &InnerMapping : OuterMapping.second) {
395 if (InnerMapping.first.DerefLevel == 0)
396 AliasList.push_back(OffsetValue{InnerMapping.first.Val,
UnknownOffset});
410 for (
const auto &
Arg : Fn.
args()) {
432 for (
const auto &OuterMapping : ReachSet.value_mappings()) {
434 for (
const auto &InnerMapping : OuterMapping.second) {
446 auto SrcIVal = InnerMapping.first;
448 ValueMap[SrcIVal.Val].FromRecords.push_back(
449 ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
451 ValueMap[SrcIVal.Val].ToRecords.push_back(
452 ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
458 for (
const auto &Mapping :
ValueMap) {
459 for (
const auto &FromRecord : Mapping.second.FromRecords) {
460 for (
const auto &ToRecord : Mapping.second.ToRecords) {
461 auto ToLevel = ToRecord.DerefLevel;
462 auto FromLevel = FromRecord.DerefLevel;
464 if (ToLevel == FromLevel)
467 auto SrcIndex = FromRecord.IValue.Index;
468 auto SrcLevel = FromRecord.IValue.DerefLevel;
469 auto DstIndex = ToRecord.IValue.Index;
470 auto DstLevel = ToRecord.IValue.DerefLevel;
471 if (ToLevel > FromLevel)
472 SrcLevel += ToLevel - FromLevel;
474 DstLevel += FromLevel - ToLevel;
485 ExtRelations.
erase(std::unique(ExtRelations.
begin(), ExtRelations.
end()),
492 for (
const auto &Mapping : AMap.mappings()) {
503 const ReachabilitySet &ReachSet,
const AliasAttrMap &AMap) {
511 CFLAndersAAResult::FunctionInfo::getAttrs(
const Value *V)
const {
514 auto Itr = AttrMap.find(V);
515 if (Itr != AttrMap.end())
528 auto MaybeAttrsA = getAttrs(LHS);
529 auto MaybeAttrsB = getAttrs(RHS);
530 if (!MaybeAttrsA || !MaybeAttrsB)
534 auto AttrsA = *MaybeAttrsA;
535 auto AttrsB = *MaybeAttrsB;
547 auto Itr = AliasMap.find(LHS);
548 if (Itr != AliasMap.end()) {
551 auto Comparator = [](OffsetValue LHS, OffsetValue RHS) {
552 return std::less<const Value *>()(LHS.Val, RHS.Val);
554 #ifdef EXPENSIVE_CHECKS 557 auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(),
558 OffsetValue{RHS, 0}, Comparator);
560 if (RangePair.first != RangePair.second) {
565 const uint64_t LHSSize = MaybeLHSSize.
getValue();
566 const uint64_t RHSSize = MaybeRHSSize.
getValue();
568 for (
const auto &OVal :
make_range(RangePair)) {
582 auto LHSStart = OVal.Offset;
584 auto LHSEnd = OVal.Offset + static_cast<int64_t>(LHSSize);
586 auto RHSEnd = static_cast<int64_t>(RHSSize);
587 if (LHSEnd > RHSStart && LHSStart < RHSEnd)
598 std::vector<WorkListItem> &WorkList) {
601 if (ReachSet.insert(
From, To, State))
602 WorkList.push_back(WorkListItem{From, To, State});
606 ReachabilitySet &ReachSet,
609 auto Val = Mapping.first;
618 for (
auto &Edge :
ValueInfo.getNodeInfoAtLevel(
I).Edges) {
619 propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet,
621 propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet,
631 if (Graph.getNode(NodeBelow))
637 ReachabilitySet &ReachSet, AliasMemSet &MemSet,
638 std::vector<WorkListItem> &WorkList) {
639 auto FromNode = Item.From;
640 auto ToNode = Item.To;
642 auto NodeInfo = Graph.getNode(ToNode);
643 assert(NodeInfo !=
nullptr);
655 if (FromNodeBelow && ToNodeBelow &&
656 MemSet.insert(*FromNodeBelow, *ToNodeBelow)) {
658 MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList);
659 for (
const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) {
660 auto Src = Mapping.first;
662 if (Mapping.second.test(static_cast<size_t>(FromState)))
663 propagate(Src, *ToNodeBelow, ToState, ReachSet, WorkList);
666 MemAliasPropagate(MatchState::FlowFromReadOnly,
667 MatchState::FlowFromMemAliasReadOnly);
668 MemAliasPropagate(MatchState::FlowToWriteOnly,
669 MatchState::FlowToMemAliasWriteOnly);
670 MemAliasPropagate(MatchState::FlowToReadWrite,
671 MatchState::FlowToMemAliasReadWrite);
683 auto NextAssignState = [&](
MatchState State) {
684 for (
const auto &AssignEdge : NodeInfo->Edges)
685 propagate(FromNode, AssignEdge.Other, State, ReachSet, WorkList);
687 auto NextRevAssignState = [&](
MatchState State) {
688 for (
const auto &RevAssignEdge : NodeInfo->ReverseEdges)
689 propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList);
692 if (
auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
693 for (
const auto &MemAlias : *
AliasSet)
694 propagate(FromNode, MemAlias, State, ReachSet, WorkList);
698 switch (Item.State) {
699 case MatchState::FlowFromReadOnly:
700 NextRevAssignState(MatchState::FlowFromReadOnly);
701 NextAssignState(MatchState::FlowToReadWrite);
702 NextMemState(MatchState::FlowFromMemAliasReadOnly);
705 case MatchState::FlowFromMemAliasNoReadWrite:
706 NextRevAssignState(MatchState::FlowFromReadOnly);
707 NextAssignState(MatchState::FlowToWriteOnly);
710 case MatchState::FlowFromMemAliasReadOnly:
711 NextRevAssignState(MatchState::FlowFromReadOnly);
712 NextAssignState(MatchState::FlowToReadWrite);
715 case MatchState::FlowToWriteOnly:
716 NextAssignState(MatchState::FlowToWriteOnly);
717 NextMemState(MatchState::FlowToMemAliasWriteOnly);
720 case MatchState::FlowToReadWrite:
721 NextAssignState(MatchState::FlowToReadWrite);
722 NextMemState(MatchState::FlowToMemAliasReadWrite);
725 case MatchState::FlowToMemAliasWriteOnly:
726 NextAssignState(MatchState::FlowToWriteOnly);
729 case MatchState::FlowToMemAliasReadWrite:
730 NextAssignState(MatchState::FlowToReadWrite);
736 const ReachabilitySet &ReachSet) {
737 AliasAttrMap AttrMap;
738 std::vector<InstantiatedValue> WorkList, NextList;
742 auto Val = Mapping.first;
746 AttrMap.add(Node,
ValueInfo.getNodeInfoAtLevel(
I).Attr);
747 WorkList.push_back(Node);
751 while (!WorkList.empty()) {
752 for (
const auto &Dst : WorkList) {
753 auto DstAttr = AttrMap.getAttrs(Dst);
758 for (
const auto &Mapping : ReachSet.reachableValueAliases(Dst)) {
759 auto Src = Mapping.first;
760 if (AttrMap.add(Src, DstAttr))
761 NextList.push_back(Src);
767 if (AttrMap.add(*DstBelow, DstAttr)) {
768 NextList.push_back(*DstBelow);
774 WorkList.swap(NextList);
782 CFLAndersAAResult::buildInfoFrom(
const Function &Fn) {
784 *
this, GetTLI(const_cast<Function &>(Fn)),
786 const_cast<Function &>(Fn));
787 auto &Graph = GraphBuilder.getCFLGraph();
789 ReachabilitySet ReachSet;
792 std::vector<WorkListItem> WorkList, NextList;
795 while (!WorkList.empty()) {
796 for (
const auto &Item : WorkList)
799 NextList.swap(WorkList);
807 return FunctionInfo(Fn, GraphBuilder.getReturnValues(), ReachSet,
814 assert(InsertPair.second &&
815 "Trying to scan a function that has already been cached");
820 auto FunInfo = buildInfoFrom(Fn);
822 Handles.emplace_front(const_cast<Function *>(&Fn),
this);
825 void CFLAndersAAResult::evict(
const Function *Fn) { Cache.erase(Fn); }
828 CFLAndersAAResult::ensureCached(
const Function &Fn) {
829 auto Iter = Cache.find(&Fn);
830 if (Iter == Cache.end()) {
832 Iter = Cache.find(&Fn);
833 assert(Iter != Cache.end());
834 assert(Iter->second.hasValue());
840 auto &FunInfo = ensureCached(Fn);
841 if (FunInfo.hasValue())
842 return &FunInfo->getAliasSummary();
849 auto *ValA = LocA.
Ptr;
850 auto *ValB = LocB.
Ptr;
852 if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
863 <<
"CFLAndersAA: could not extract parent function information.\n");
871 auto &FunInfo = ensureCached(*Fn);
874 if (FunInfo->mayAlias(ValA, LocA.
Size, ValB, LocB.
Size))
890 if (isa<Constant>(LocA.
Ptr) && isa<Constant>(LocB.
Ptr))
891 return AAResultBase::alias(LocA, LocB, AAQI);
895 return AAResultBase::alias(LocA, LocB, AAQI);
911 "Inclusion-Based CFL Alias Analysis",
false,
true)
923 return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
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)
#define LLVM_UNLIKELY(EXPR)
Implements a dense probed hash-table based set.
void push_back(const T &Elt)
This is the result of instantiating InterfaceValue at a particular call.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
void initializeCFLAndersAAWrapperPassPass(PassRegistry &)
This class stores info we want to provide to or retain within an alias query.
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.
We use InterfaceValue to describe parameters/return value, as well as potential memory locations that...
static void query(const MachineInstr &MI, AliasAnalysis &AA, bool &Read, bool &Write, bool &Effects, bool &StackPointer)
AnalysisUsage & addRequired()
CFLAndersAAResult(std::function< const TargetLibraryInfo &(Function &F)> GetTLI)
static AliasAttrMap buildAttrMap(const CFLGraph &Graph, const ReachabilitySet &ReachSet)
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS)
static Optional< InterfaceValue > getInterfaceValue(InstantiatedValue IValue, const SmallVectorImpl< Value * > &RetVals)
A CRTP-driven "mixin" base class to help implement the function alias analysis results concept.
static void populateExternalAttributes(SmallVectorImpl< ExternalAttribute > &ExtAttributes, const Function &Fn, const SmallVectorImpl< Value * > &RetVals, const AliasAttrMap &AMap)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
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)
static OffsetInstantiatedValue getTombstoneKey()
bool is_sorted(R &&Range, Compare C)
Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static bool hasWriteOnlyState(StateSet Set)
Legacy wrapper pass to provide the CFLAndersAAResult object.
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.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
void sort(IteratorTy Start, IteratorTy End)
bool isGlobalOrArgAttr(AliasAttrs Attr)
iterator erase(const_iterator CI)
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.
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)
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...
FunctionInfo(const Function &, const SmallVectorImpl< Value * > &, const ReachabilitySet &, const AliasAttrMap &)
static bool hasReadOnlyState(StateSet Set)
const AliasSummary & getAliasSummary() const
Analysis pass providing the TargetLibraryInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static const Function * parentFunctionOfValue(const Value *Val)
bool operator<(int64_t V1, const APSInt &V2)
LLVM Value Representation.
print Print MemDeps of function
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
A container for analyses that lazily runs them and caches their results.
static void populateExternalRelations(SmallVectorImpl< ExternalRelation > &ExtRelations, const Function &Fn, const SmallVectorImpl< Value * > &RetVals, const ReachabilitySet &ReachSet)
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...
static Expected< BitVector > scan(StringRef &S, StringRef Original)
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.