diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h --- a/llvm/include/llvm/Transforms/IPO/Attributor.h +++ b/llvm/include/llvm/Transforms/IPO/Attributor.h @@ -256,6 +256,22 @@ OAS.getOffset() < getOffset() + getSize(); } + OffsetAndSize &operator&=(const OffsetAndSize &R) { + if (getOffset() == Unassigned) + first = R.getOffset(); + else if (R.getOffset() != Unassigned && R.getOffset() != getOffset()) + first = Unknown; + + if (getSize() == Unassigned) + second = R.getSize(); + else if (getSize() == Unknown || R.getSize() == Unknown) + second = Unknown; + else if (R.getSize() != Unassigned) + second = std::max(second, R.getSize()); + + return *this; + } + /// Constants used to represent special offsets or sizes. static constexpr int64_t Unassigned = -1; static constexpr int64_t Unknown = -2; @@ -4987,33 +5003,37 @@ /// An access description. struct Access { - Access(Instruction *I, Optional Content, AccessKind Kind, Type *Ty) - : LocalI(I), RemoteI(I), Content(Content), Kind(Kind), Ty(Ty) { + Access(Instruction *I, int64_t Offset, int64_t Size, + Optional Content, AccessKind Kind, Type *Ty) + : LocalI(I), RemoteI(I), Content(Content), OAS(Offset, Size), + Kind(Kind), Ty(Ty) { verify(); } - Access(Instruction *LocalI, Instruction *RemoteI, Optional Content, - AccessKind Kind, Type *Ty) - : LocalI(LocalI), RemoteI(RemoteI), Content(Content), Kind(Kind), - Ty(Ty) { + Access(Instruction *LocalI, Instruction *RemoteI, int64_t Offset, + int64_t Size, Optional Content, AccessKind Kind, Type *Ty) + : LocalI(LocalI), RemoteI(RemoteI), Content(Content), OAS(Offset, Size), + Kind(Kind), Ty(Ty) { verify(); } Access(const Access &Other) = default; Access(const Access &&Other) : LocalI(Other.LocalI), RemoteI(Other.RemoteI), Content(Other.Content), - Kind(Other.Kind), Ty(Other.Ty) {} + OAS(Other.OAS), Kind(Other.Kind), Ty(Other.Ty) {} Access &operator=(const Access &Other) = default; bool operator==(const Access &R) const { - return LocalI == R.LocalI && RemoteI == R.RemoteI && + return LocalI == R.LocalI && RemoteI == R.RemoteI && OAS == R.OAS && Content == R.Content && Kind == R.Kind; } bool operator!=(const Access &R) const { return !(*this == R); } Access &operator&=(const Access &R) { assert(RemoteI == R.RemoteI && "Expected same instruction!"); + assert(LocalI == R.LocalI && "Expected same instruction!"); Content = AA::combineOptionalValuesInAAValueLatice(Content, R.Content, Ty); Kind = AccessKind(Kind | R.Kind); + OAS &= R.OAS; return *this; } @@ -5061,6 +5081,9 @@ /// determined. Optional getContent() const { return Content; } + int64_t getOffset() const { return OAS.getOffset(); } + int64_t getSize() const { return OAS.getSize(); } + private: /// The instruction responsible for the access with respect to the local /// scope of the associated attribute. @@ -5073,6 +5096,8 @@ /// cannot be determined. Optional Content; + AA::OffsetAndSize OAS = AA::OffsetAndSize::getUnassigned(); + /// The access kind, e.g., READ, as bitset (could be more than one). AccessKind Kind; @@ -5108,7 +5133,7 @@ virtual bool forallInterferingAccesses( Attributor &A, const AbstractAttribute &QueryingAA, Instruction &I, function_ref CB, bool &HasBeenWrittenTo, - AA::OffsetAndSize *OASPtr = nullptr) const = 0; + AA::OffsetAndSize &OAS) const = 0; /// This function should return true if the type of the \p AA is AAPointerInfo static bool classof(const AbstractAttribute *AA) { diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -456,7 +456,7 @@ auto &PI = A.getAAFor(QueryingAA, IRPosition::value(*Obj), DepClassTy::NONE); if (!PI.forallInterferingAccesses(A, QueryingAA, I, CheckAccess, - HasBeenWrittenTo, &OAS)) { + HasBeenWrittenTo, OAS)) { LLVM_DEBUG( dbgs() << "Failed to verify all interfering accesses for underlying object: " diff --git a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp --- a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp +++ b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp @@ -740,12 +740,6 @@ /// A type to track pointer/struct usage and accesses for AAPointerInfo. struct AA::PointerInfo::State : public AbstractState { - ~State() { - // We do not delete the Accesses objects but need to destroy them still. - for (auto &It : AccessBins) - It.second->~Accesses(); - } - /// Return the best possible representable state. static State getBestState(const State &SIS) { return State(); } @@ -757,9 +751,7 @@ } State() = default; - State(State &&SIS) : AccessBins(std::move(SIS.AccessBins)) { - SIS.AccessBins.clear(); - } + State(State &&SIS) = default; const State &getAssumed() const { return *this; } @@ -785,7 +777,9 @@ if (this == &R) return *this; BS = R.BS; - AccessBins = R.AccessBins; + AccessList = R.AccessList; + OffsetBins = R.OffsetBins; + InstTupleMap = R.InstTupleMap; return *this; } @@ -793,99 +787,53 @@ if (this == &R) return *this; std::swap(BS, R.BS); - std::swap(AccessBins, R.AccessBins); + std::swap(AccessList, R.AccessList); + std::swap(OffsetBins, R.OffsetBins); + std::swap(InstTupleMap, R.InstTupleMap); return *this; } - bool operator==(const State &R) const { - if (BS != R.BS) - return false; - if (AccessBins.size() != R.AccessBins.size()) - return false; - auto It = begin(), RIt = R.begin(), E = end(); - while (It != E) { - if (It->getFirst() != RIt->getFirst()) - return false; - auto &Accs = It->getSecond(); - auto &RAccs = RIt->getSecond(); - if (Accs->size() != RAccs->size()) - return false; - for (const auto &ZipIt : llvm::zip(*Accs, *RAccs)) - if (std::get<0>(ZipIt) != std::get<1>(ZipIt)) - return false; - ++It; - ++RIt; - } - return true; - } - bool operator!=(const State &R) const { return !(*this == R); } - - /// We store accesses in a set with the instruction as key. - struct Accesses { - SmallVector Accesses; - DenseMap Map; - - unsigned size() const { return Accesses.size(); } - - using vec_iterator = decltype(Accesses)::iterator; - vec_iterator begin() { return Accesses.begin(); } - vec_iterator end() { return Accesses.end(); } - - using iterator = decltype(Map)::const_iterator; - iterator find(AAPointerInfo::Access &Acc) { - return Map.find(Acc.getRemoteInst()); - } - iterator find_end() { return Map.end(); } - - AAPointerInfo::Access &get(iterator &It) { - return Accesses[It->getSecond()]; - } - - void insert(AAPointerInfo::Access &Acc) { - Map[Acc.getRemoteInst()] = Accesses.size(); - Accesses.push_back(Acc); - } - }; - - /// We store all accesses in bins denoted by their offset and size. - using AccessBinsTy = DenseMap; - - AccessBinsTy::const_iterator begin() const { return AccessBins.begin(); } - AccessBinsTy::const_iterator end() const { return AccessBins.end(); } - -protected: - /// The bins with all the accesses for the associated pointer. - AccessBinsTy AccessBins; - - /// Add a new access to the state at offset \p Offset and with size \p Size. + /// Add a new Access to the state at offset \p Offset and with size \p Size. /// The access is associated with \p I, writes \p Content (if anything), and - /// is of kind \p Kind. + /// is of kind \p Kind. If an Access already exists for the same \p I and same + /// \p RemoteI, the two are combined, potentially losing information about + /// offset and size. The resulting access must now be moved from its original + /// OffsetBin to the bin for its new offset. + /// /// \Returns CHANGED, if the state changed, UNCHANGED otherwise. ChangeStatus addAccess(Attributor &A, int64_t Offset, int64_t Size, Instruction &I, Optional Content, AAPointerInfo::AccessKind Kind, Type *Ty, - Instruction *RemoteI = nullptr, - Accesses *BinPtr = nullptr) { - AA::OffsetAndSize Key{Offset, Size}; - Accesses *&Bin = BinPtr ? BinPtr : AccessBins[Key]; - if (!Bin) - Bin = new (A.Allocator) Accesses; - AAPointerInfo::Access Acc(&I, RemoteI ? RemoteI : &I, Content, Kind, Ty); - // Check if we have an access for this instruction in this bin, if not, - // simply add it. - auto It = Bin->find(Acc); - if (It == Bin->find_end()) { - Bin->insert(Acc); - return ChangeStatus::CHANGED; - } - // If the existing access is the same as then new one, nothing changed. - AAPointerInfo::Access &Current = Bin->get(It); - AAPointerInfo::Access Before = Current; - // The new one will be combined with the existing one. - Current &= Acc; - return Current == Before ? ChangeStatus::UNCHANGED : ChangeStatus::CHANGED; + Instruction *RemoteI = nullptr); + + using OffsetBinsTy = DenseMap>; + + using const_bin_iterator = OffsetBinsTy::const_iterator; + const_bin_iterator begin() const { return OffsetBins.begin(); } + const_bin_iterator end() const { return OffsetBins.end(); } + + const AAPointerInfo::Access &getAccess(unsigned Index) const { + return AccessList[Index]; } +protected: + // Every memory instruction results in an Access object. We maintain a list of + // all Access objects that we own, along with the following maps: + // + // - OffsetBins: OffsetAndSize -> { Access } + // - InstTupleMap: RemoteI x LocalI -> Access + // + // A RemoteI is any instruction that accesses memory. RemoteI is different + // from LocalI if and only if LocalI is a call; then RemoteI is some + // instruction in the callgraph starting from LocalI. Multiple paths in the + // callgraph from LocalI to RemoteI may produce multiple accesses, but these + // are all combined into a single Access object. This may result in loss of + // information in OffsetAndSize in the Access object. + SmallVector AccessList; + OffsetBinsTy OffsetBins; + DenseMap> + InstTupleMap; + /// See AAPointerInfo::forallInterferingAccesses. bool forallInterferingAccesses( AA::OffsetAndSize OAS, @@ -893,14 +841,16 @@ if (!isValidState()) return false; - for (const auto &It : AccessBins) { + for (const auto &It : OffsetBins) { AA::OffsetAndSize ItOAS = It.getFirst(); if (!OAS.mayOverlap(ItOAS)) continue; bool IsExact = OAS == ItOAS && !OAS.offsetOrSizeAreUnknown(); - for (auto &Access : *It.getSecond()) + for (auto Index : It.getSecond()) { + auto &Access = AccessList[Index]; if (!CB(Access, IsExact)) return false; + } } return true; } @@ -909,33 +859,23 @@ bool forallInterferingAccesses( Instruction &I, function_ref CB, - AA::OffsetAndSize *OASPtr) const { + AA::OffsetAndSize &OAS) const { if (!isValidState()) return false; - // First find the offset and size of I. - AA::OffsetAndSize OAS = AA::OffsetAndSize::getUnassigned(); - for (const auto &It : AccessBins) { - for (auto &Access : *It.getSecond()) { - if (Access.getRemoteInst() == &I) { - OAS = It.getFirst(); - break; - } - } - if (OAS.getSize() != AA::OffsetAndSize::Unassigned) - break; + auto LocalMap = InstTupleMap.find(&I); + if (LocalMap == InstTupleMap.end()) { + return true; } - if (OASPtr) - *OASPtr = OAS; - - // No access for I was found, we are done. - if (OAS.getSize() == AA::OffsetAndSize::Unassigned) - return true; + bool Changed = false; + for (auto LI : LocalMap->getSecond()) { + auto &Access = AccessList[LI.getSecond()]; + OAS &= {Access.getOffset(), Access.getSize()}; + Changed |= forallInterferingAccesses(OAS, CB); + } - // Now that we have an offset and size, find all overlapping ones and use - // the callback on the accesses. - return forallInterferingAccesses(OAS, CB); + return Changed; } private: @@ -943,6 +883,50 @@ BooleanState BS; }; +ChangeStatus AA::PointerInfo::State::addAccess(Attributor &A, int64_t Offset, + int64_t Size, Instruction &I, + Optional Content, + AAPointerInfo::AccessKind Kind, + Type *Ty, Instruction *RemoteI) { + RemoteI = RemoteI ? RemoteI : &I; + AAPointerInfo::Access Acc(&I, RemoteI, Offset, Size, Content, Kind, Ty); + + // Check if we have an access for this instruction, if not, simply add it. + auto &LocalMap = InstTupleMap[RemoteI]; + auto [AccIt, AccInserted] = LocalMap.try_emplace(&I, AccessList.size()); + auto Index = AccIt->getSecond(); + if (AccInserted) { + assert(Index == AccessList.size() && "Expected to append new access."); + AccessList.push_back(Acc); + } else { + // The new one will be combined with the existing one. + auto &Current = AccessList[Index]; + auto Before = Current; + Current &= Acc; + if (Current == Before) + return ChangeStatus::UNCHANGED; + + LLVM_DEBUG(dbgs() << "Access changed from " << Before << " to " << Current + << "\n"); + Acc = Current; + AA::OffsetAndSize Key{Before.getOffset(), Before.getSize()}; + assert(OffsetBins.count(Key) && "Existing Access must be in some bin."); + auto &Bin = OffsetBins[Key]; + assert(Bin.count(Index) && "Expected bin to actually contain the Access."); + LLVM_DEBUG(dbgs() << "[AAPointerInfo] Removing Access " << AccessList[Index] + << " with key " << '{' << Key.getOffset() << ',' + << Key.getSize() << '}' << "\n"); + Bin.erase(Index); + } + + AA::OffsetAndSize Key{Acc.getOffset(), Acc.getSize()}; + LLVM_DEBUG(dbgs() << "[AAPointerInfo] Inserting Access " << Acc + << " with key " << '{' << Key.getOffset() << ',' + << Key.getSize() << '}' << "\n"); + OffsetBins[Key].insert(Index); + return ChangeStatus::CHANGED; +} + namespace { struct AAPointerInfoImpl : public StateWrapper { @@ -953,7 +937,7 @@ const std::string getAsStr() const override { return std::string("PointerInfo ") + (isValidState() ? (std::string("#") + - std::to_string(AccessBins.size()) + " bins") + std::to_string(OffsetBins.size()) + " bins") : ""); } @@ -972,7 +956,7 @@ bool forallInterferingAccesses( Attributor &A, const AbstractAttribute &QueryingAA, Instruction &I, function_ref UserCB, bool &HasBeenWrittenTo, - AA::OffsetAndSize *OASPtr = nullptr) const override { + AA::OffsetAndSize &OAS) const override { HasBeenWrittenTo = false; SmallPtrSet DominatingWrites; @@ -1087,7 +1071,7 @@ InterferingAccesses.push_back({&Acc, Exact}); return true; }; - if (!State::forallInterferingAccesses(I, AccessCB, OASPtr)) + if (!State::forallInterferingAccesses(I, AccessCB, OAS)) return false; if (HasBeenWrittenTo) { @@ -1154,13 +1138,14 @@ // Combine the accesses bin by bin. ChangeStatus Changed = ChangeStatus::UNCHANGED; - for (const auto &It : OtherAAImpl.getState()) { + const auto &State = OtherAAImpl.getState(); + for (const auto &It : State) { AA::OffsetAndSize OAS = AA::OffsetAndSize::getUnknown(); if (Offset != AA::OffsetAndSize::Unknown) OAS = AA::OffsetAndSize(It.first.getOffset() + Offset, It.first.getSize()); - Accesses *Bin = AccessBins.lookup(OAS); - for (const AAPointerInfo::Access &RAcc : *It.second) { + for (auto Index : It.getSecond()) { + const auto &RAcc = State.getAccess(Index); if (IsByval && !RAcc.isRead()) continue; bool UsedAssumedInformation = false; @@ -1175,7 +1160,7 @@ } Changed = Changed | addAccess(A, OAS.getOffset(), OAS.getSize(), CB, Content, - AK, RAcc.getType(), RAcc.getRemoteInst(), Bin); + AK, RAcc.getType(), RAcc.getRemoteInst()); } } return Changed; @@ -1187,11 +1172,12 @@ /// Dump the state into \p O. void dumpState(raw_ostream &O) { - for (auto &It : AccessBins) { + for (auto &It : OffsetBins) { O << "[" << It.first.getOffset() << "-" << It.first.getOffset() + It.first.getSize() - << "] : " << It.getSecond()->size() << "\n"; - for (auto &Acc : *It.getSecond()) { + << "] : " << It.getSecond().size() << "\n"; + for (auto AccIndex : It.getSecond()) { + auto &Acc = AccessList[AccIndex]; O << " - " << Acc.getKind() << " - " << *Acc.getLocalInst() << "\n"; if (Acc.getLocalInst() != Acc.getRemoteInst()) O << " --> " << *Acc.getRemoteInst() diff --git a/llvm/test/Transforms/Attributor/value-simplify-pointer-info.ll b/llvm/test/Transforms/Attributor/value-simplify-pointer-info.ll --- a/llvm/test/Transforms/Attributor/value-simplify-pointer-info.ll +++ b/llvm/test/Transforms/Attributor/value-simplify-pointer-info.ll @@ -2223,6 +2223,7 @@ ; TUNIT: loop: ; TUNIT-NEXT: [[P:%.*]] = phi i8* [ bitcast (i32* @a2 to i8*), [[ENTRY:%.*]] ], [ [[G:%.*]], [[LOOP]] ] ; TUNIT-NEXT: [[I:%.*]] = phi i8 [ 0, [[ENTRY]] ], [ [[O:%.*]], [[LOOP]] ] +; TUNIT-NEXT: store i8 1, i8* [[P]], align 2 ; TUNIT-NEXT: [[G]] = getelementptr i8, i8* bitcast (i32* @a2 to i8*), i64 2 ; TUNIT-NEXT: [[O]] = add nsw i8 [[I]], 1 ; TUNIT-NEXT: [[C:%.*]] = icmp eq i8 [[O]], 7 @@ -2241,6 +2242,7 @@ ; CGSCC: loop: ; CGSCC-NEXT: [[P:%.*]] = phi i8* [ bitcast (i32* @a2 to i8*), [[ENTRY:%.*]] ], [ [[G:%.*]], [[LOOP]] ] ; CGSCC-NEXT: [[I:%.*]] = phi i8 [ 0, [[ENTRY]] ], [ [[O:%.*]], [[LOOP]] ] +; CGSCC-NEXT: store i8 1, i8* [[P]], align 2 ; CGSCC-NEXT: [[G]] = getelementptr i8, i8* bitcast (i32* @a2 to i8*), i64 2 ; CGSCC-NEXT: [[O]] = add nsw i8 [[I]], 1 ; CGSCC-NEXT: [[C:%.*]] = icmp eq i8 [[O]], 7 @@ -2281,6 +2283,7 @@ ; TUNIT: loop: ; TUNIT-NEXT: [[P:%.*]] = phi i8* [ bitcast (i32* @a3 to i8*), [[ENTRY:%.*]] ], [ [[G:%.*]], [[LOOP]] ] ; TUNIT-NEXT: [[I:%.*]] = phi i8 [ 0, [[ENTRY]] ], [ [[O:%.*]], [[LOOP]] ] +; TUNIT-NEXT: store i8 1, i8* [[P]], align 2 ; TUNIT-NEXT: [[G]] = getelementptr i8, i8* bitcast (i32* @a3 to i8*), i64 2 ; TUNIT-NEXT: [[O]] = add nsw i8 [[I]], 1 ; TUNIT-NEXT: [[C:%.*]] = icmp eq i8 [[O]], 7 @@ -2302,6 +2305,7 @@ ; CGSCC: loop: ; CGSCC-NEXT: [[P:%.*]] = phi i8* [ bitcast (i32* @a3 to i8*), [[ENTRY:%.*]] ], [ [[G:%.*]], [[LOOP]] ] ; CGSCC-NEXT: [[I:%.*]] = phi i8 [ 0, [[ENTRY]] ], [ [[O:%.*]], [[LOOP]] ] +; CGSCC-NEXT: store i8 1, i8* [[P]], align 2 ; CGSCC-NEXT: [[G]] = getelementptr i8, i8* bitcast (i32* @a3 to i8*), i64 2 ; CGSCC-NEXT: [[O]] = add nsw i8 [[I]], 1 ; CGSCC-NEXT: [[C:%.*]] = icmp eq i8 [[O]], 7