90 #define DEBUG_TYPE "cfl-anders-aa"
101 enum class MatchState : uint8_t {
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));
145 return std::less<const Value *>()(
LHS.Val,
RHS.Val) ||
150 struct OffsetInstantiatedValue {
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));
299 return OffsetInstantiatedValue{
305 return OffsetInstantiatedValue{
312 std::make_pair(OVal.IVal, OVal.Offset));
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))
361 Index =
Arg->getArgNo() + 1;
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;
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) {
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)
597 MatchState State, ReachabilitySet &ReachSet,
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;
661 auto MemAliasPropagate = [&](MatchState FromState, MatchState ToState) {
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);
691 auto NextMemState = [&](MatchState State) {
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)),
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())
853 return AliasResult::NoAlias;
863 <<
"CFLAndersAA: could not extract parent function information.\n");
864 return AliasResult::MayAlias;
871 auto &FunInfo = ensureCached(*Fn);
874 if (FunInfo->mayAlias(ValA, LocA.
Size, ValB, LocB.
Size))
875 return AliasResult::MayAlias;
876 return AliasResult::NoAlias;
883 return AliasResult::MustAlias;
890 if (isa<Constant>(LocA.
Ptr) && isa<Constant>(LocB.
Ptr))
891 return AAResultBase::alias(LocA, LocB, AAQI);
894 if (QueryResult == AliasResult::MayAlias)
895 return AAResultBase::alias(LocA, LocB, AAQI);
911 "Inclusion-Based CFL Alias Analysis",
false,
true)
923 return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);