Index: llvm/include/llvm/Transforms/IPO/Attributor.h =================================================================== --- llvm/include/llvm/Transforms/IPO/Attributor.h +++ llvm/include/llvm/Transforms/IPO/Attributor.h @@ -97,8 +97,10 @@ #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H +#include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/SCCIterator.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumeBundleQueries.h" @@ -116,10 +118,13 @@ #include "llvm/IR/ConstantRange.h" #include "llvm/IR/PassManager.h" #include "llvm/Support/Allocator.h" +#include "llvm/Support/DOTGraphTraits.h" +#include "llvm/Support/GraphWriter.h" #include "llvm/Transforms/Utils/CallGraphUpdater.h" namespace llvm { +struct AADepGraph; struct Attributor; struct AbstractAttribute; struct InformationCache; @@ -912,6 +917,9 @@ /// Return the internal information cache. InformationCache &getInfoCache() { return InfoCache; } + /// Return the first element of the AA list + AbstractAttribute *getEntryAA() { return AllAbstractAttributes.front(); } + /// Return true if this is a module pass, false otherwise. bool isModulePass() const { return !Functions.empty() && @@ -1206,12 +1214,18 @@ bool checkForAllReadWriteInstructions(function_ref Pred, AbstractAttribute &QueryingAA); + /// Print All dependencies for every AbstractAttribute in the AA list + /// For debug use only. + void printAllDependency(raw_ostream &); + /// Return the data layout associated with the anchor scope. const DataLayout &getDataLayout() const { return InfoCache.DL; } /// The allocator used to allocate memory, e.g. for `AbstractAttribute`s. BumpPtrAllocator &Allocator; + AADepGraph *DG; + private: /// This method will do fixpoint iteration until fixpoint or the /// maximum iteration count is reached. @@ -1405,6 +1419,8 @@ SmallPtrSet ToBeDeletedFunctions; SmallPtrSet ToBeDeletedBlocks; SmallDenseSet ToBeDeletedInsts; + + friend AADepGraph; ///} }; @@ -1453,6 +1469,33 @@ virtual ChangeStatus indicatePessimisticFixpoint() = 0; }; +/// The data structure for the dependency graph +struct AADepGraph { + AADepGraph(Attributor &A) : A(A) {} + ~AADepGraph() {} + + Attributor &A; + + using AAVector = SmallVector; + + AbstractAttribute *GetEntryNode() const { + return A.AllAbstractAttributes.front(); + } + + using iterator = AAVector::iterator; + + iterator begin() { return A.AllAbstractAttributes.begin(); } + iterator end() { return A.AllAbstractAttributes.end(); } + + void viewGraph(); + + /// Dump graph to file + void dumpGraph(); + + /// Print dependency graph + void print(); +}; + /// Simple state with integers encoding. /// /// The interface ensures that the assumed bits are always a subset of the known @@ -2007,10 +2050,14 @@ /// Helper functions, for debug purposes only. ///{ virtual void print(raw_ostream &OS) const; + virtual void printDeps(raw_ostream &OS) const; void dump() const { print(dbgs()); } /// This function should return the "summarized" assumed state as string. virtual const std::string getAsStr() const = 0; + + /// This function should return the corrsponding IR attribute name + virtual const std::string getName() const = 0; ///} /// Allow the Attributor access to the protected methods. @@ -2054,6 +2101,9 @@ /// if there is an optional of required dependence. using DepTy = PointerIntPair; TinyPtrVector Deps; + +public: + TinyPtrVector &getDeps() { return Deps; } }; /// Forward declarations of output streams for debug purposes. @@ -2922,6 +2972,8 @@ return getMemoryLocationsAsStr(getAssumedNotAccessedLocation()); } + const std::string getName() const override { return "AAMemoryLocation"; } + /// Unique ID (due to the unique address) static const char ID; }; Index: llvm/lib/Transforms/IPO/Attributor.cpp =================================================================== --- llvm/lib/Transforms/IPO/Attributor.cpp +++ llvm/lib/Transforms/IPO/Attributor.cpp @@ -15,7 +15,10 @@ #include "llvm/Transforms/IPO/Attributor.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/Statistic.h" +#include "llvm/ADT/TinyPtrVector.h" #include "llvm/Analysis/LazyValueInfo.h" #include "llvm/Analysis/MustExecute.h" #include "llvm/Analysis/ValueTracking.h" @@ -23,10 +26,15 @@ #include "llvm/IR/NoFolder.h" #include "llvm/IR/Verifier.h" #include "llvm/InitializePasses.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/FileSystem.h" +#include "llvm/Support/GraphWriter.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Local.h" #include +#include using namespace llvm; @@ -77,6 +85,19 @@ "wrappers for non-exact definitions."), cl::init(false)); +static cl::opt + DumpDepGraph("attributor-dump-dep-graph", cl::Hidden, + cl::desc("Dump the dependency graph to dot files."), + cl::init(false)); + +static cl::opt ViewDepGraph("attributor-view-dep-graph", cl::Hidden, + cl::desc("View the dependency graph."), + cl::init(false)); + +static cl::opt PrintDependencies("attributor-print-dep", cl::Hidden, + cl::desc("Print attribute dependencies"), + cl::init(false)); + /// Logic operators for the change status enum class. /// ///{ @@ -1088,155 +1109,154 @@ ChangeStatus Attributor::cleanupIR() { // Delete stuff at the end to avoid invalid references and a nice order. - LLVM_DEBUG(dbgs() << "\n[Attributor] Delete at least " - << ToBeDeletedFunctions.size() << " functions and " - << ToBeDeletedBlocks.size() << " blocks and " - << ToBeDeletedInsts.size() << " instructions and " - << ToBeChangedUses.size() << " uses\n"); - - SmallVector DeadInsts; - SmallVector TerminatorsToFold; - - for (auto &It : ToBeChangedUses) { - Use *U = It.first; - Value *NewV = It.second; - Value *OldV = U->get(); - - // Do not replace uses in returns if the value is a must-tail call we will - // not delete. - if (isa(U->getUser())) - if (auto *CI = dyn_cast(OldV->stripPointerCasts())) - if (CI->isMustTailCall() && !ToBeDeletedInsts.count(CI)) - continue; - - LLVM_DEBUG(dbgs() << "Use " << *NewV << " in " << *U->getUser() - << " instead of " << *OldV << "\n"); - U->set(NewV); - // Do not modify call instructions outside the SCC. - if (auto *CB = dyn_cast(OldV)) - if (!Functions.count(CB->getCaller())) + LLVM_DEBUG(dbgs() << "\n[Attributor] Delete at least " + << ToBeDeletedFunctions.size() << " functions and " + << ToBeDeletedBlocks.size() << " blocks and " + << ToBeDeletedInsts.size() << " instructions and " + << ToBeChangedUses.size() << " uses\n"); + + SmallVector DeadInsts; + SmallVector TerminatorsToFold; + + for (auto &It : ToBeChangedUses) { + Use *U = It.first; + Value *NewV = It.second; + Value *OldV = U->get(); + + // Do not replace uses in returns if the value is a must-tail call we will + // not delete. + if (isa(U->getUser())) + if (auto *CI = dyn_cast(OldV->stripPointerCasts())) + if (CI->isMustTailCall() && !ToBeDeletedInsts.count(CI)) continue; - if (Instruction *I = dyn_cast(OldV)) { - CGModifiedFunctions.insert(I->getFunction()); - if (!isa(I) && !ToBeDeletedInsts.count(I) && - isInstructionTriviallyDead(I)) - DeadInsts.push_back(I); - } - if (isa(NewV) && isa(U->getUser())) { - Instruction *UserI = cast(U->getUser()); - if (isa(NewV)) { - ToBeChangedToUnreachableInsts.insert(UserI); - } else { - TerminatorsToFold.push_back(UserI); - } + + LLVM_DEBUG(dbgs() << "Use " << *NewV << " in " << *U->getUser() + << " instead of " << *OldV << "\n"); + U->set(NewV); + // Do not modify call instructions outside the SCC. + if (auto *CB = dyn_cast(OldV)) + if (!Functions.count(CB->getCaller())) + continue; + if (Instruction *I = dyn_cast(OldV)) { + CGModifiedFunctions.insert(I->getFunction()); + if (!isa(I) && !ToBeDeletedInsts.count(I) && + isInstructionTriviallyDead(I)) + DeadInsts.push_back(I); + } + if (isa(NewV) && isa(U->getUser())) { + Instruction *UserI = cast(U->getUser()); + if (isa(NewV)) { + ToBeChangedToUnreachableInsts.insert(UserI); + } else { + TerminatorsToFold.push_back(UserI); } } - for (auto &V : InvokeWithDeadSuccessor) - if (InvokeInst *II = dyn_cast_or_null(V)) { - bool UnwindBBIsDead = II->hasFnAttr(Attribute::NoUnwind); - bool NormalBBIsDead = II->hasFnAttr(Attribute::NoReturn); - bool Invoke2CallAllowed = - !AAIsDead::mayCatchAsynchronousExceptions(*II->getFunction()); - assert((UnwindBBIsDead || NormalBBIsDead) && - "Invoke does not have dead successors!"); - BasicBlock *BB = II->getParent(); - BasicBlock *NormalDestBB = II->getNormalDest(); - if (UnwindBBIsDead) { - Instruction *NormalNextIP = &NormalDestBB->front(); - if (Invoke2CallAllowed) { - changeToCall(II); - NormalNextIP = BB->getTerminator(); - } - if (NormalBBIsDead) - ToBeChangedToUnreachableInsts.insert(NormalNextIP); - } else { - assert(NormalBBIsDead && "Broken invariant!"); - if (!NormalDestBB->getUniquePredecessor()) - NormalDestBB = SplitBlockPredecessors(NormalDestBB, {BB}, ".dead"); - ToBeChangedToUnreachableInsts.insert(&NormalDestBB->front()); + } + for (auto &V : InvokeWithDeadSuccessor) + if (InvokeInst *II = dyn_cast_or_null(V)) { + bool UnwindBBIsDead = II->hasFnAttr(Attribute::NoUnwind); + bool NormalBBIsDead = II->hasFnAttr(Attribute::NoReturn); + bool Invoke2CallAllowed = + !AAIsDead::mayCatchAsynchronousExceptions(*II->getFunction()); + assert((UnwindBBIsDead || NormalBBIsDead) && + "Invoke does not have dead successors!"); + BasicBlock *BB = II->getParent(); + BasicBlock *NormalDestBB = II->getNormalDest(); + if (UnwindBBIsDead) { + Instruction *NormalNextIP = &NormalDestBB->front(); + if (Invoke2CallAllowed) { + changeToCall(II); + NormalNextIP = BB->getTerminator(); } + if (NormalBBIsDead) + ToBeChangedToUnreachableInsts.insert(NormalNextIP); + } else { + assert(NormalBBIsDead && "Broken invariant!"); + if (!NormalDestBB->getUniquePredecessor()) + NormalDestBB = SplitBlockPredecessors(NormalDestBB, {BB}, ".dead"); + ToBeChangedToUnreachableInsts.insert(&NormalDestBB->front()); } - for (Instruction *I : TerminatorsToFold) { + } + for (Instruction *I : TerminatorsToFold) { + CGModifiedFunctions.insert(I->getFunction()); + ConstantFoldTerminator(I->getParent()); + } + for (auto &V : ToBeChangedToUnreachableInsts) + if (Instruction *I = dyn_cast_or_null(V)) { CGModifiedFunctions.insert(I->getFunction()); - ConstantFoldTerminator(I->getParent()); + changeToUnreachable(I, /* UseLLVMTrap */ false); } - for (auto &V : ToBeChangedToUnreachableInsts) - if (Instruction *I = dyn_cast_or_null(V)) { - CGModifiedFunctions.insert(I->getFunction()); - changeToUnreachable(I, /* UseLLVMTrap */ false); - } - for (auto &V : ToBeDeletedInsts) { - if (Instruction *I = dyn_cast_or_null(V)) { - I->dropDroppableUses(); - CGModifiedFunctions.insert(I->getFunction()); - if (!I->getType()->isVoidTy()) - I->replaceAllUsesWith(UndefValue::get(I->getType())); - if (!isa(I) && isInstructionTriviallyDead(I)) - DeadInsts.push_back(I); - else - I->eraseFromParent(); - } + for (auto &V : ToBeDeletedInsts) { + if (Instruction *I = dyn_cast_or_null(V)) { + I->dropDroppableUses(); + CGModifiedFunctions.insert(I->getFunction()); + if (!I->getType()->isVoidTy()) + I->replaceAllUsesWith(UndefValue::get(I->getType())); + if (!isa(I) && isInstructionTriviallyDead(I)) + DeadInsts.push_back(I); + else + I->eraseFromParent(); } + } - RecursivelyDeleteTriviallyDeadInstructions(DeadInsts); + RecursivelyDeleteTriviallyDeadInstructions(DeadInsts); - if (unsigned NumDeadBlocks = ToBeDeletedBlocks.size()) { - SmallVector ToBeDeletedBBs; - ToBeDeletedBBs.reserve(NumDeadBlocks); - for (BasicBlock *BB : ToBeDeletedBlocks) { - CGModifiedFunctions.insert(BB->getParent()); - ToBeDeletedBBs.push_back(BB); - } - // Actually we do not delete the blocks but squash them into a single - // unreachable but untangling branches that jump here is something we need - // to do in a more generic way. - DetatchDeadBlocks(ToBeDeletedBBs, nullptr); + if (unsigned NumDeadBlocks = ToBeDeletedBlocks.size()) { + SmallVector ToBeDeletedBBs; + ToBeDeletedBBs.reserve(NumDeadBlocks); + for (BasicBlock *BB : ToBeDeletedBlocks) { + CGModifiedFunctions.insert(BB->getParent()); + ToBeDeletedBBs.push_back(BB); } + // Actually we do not delete the blocks but squash them into a single + // unreachable but untangling branches that jump here is something we need + // to do in a more generic way. + DetatchDeadBlocks(ToBeDeletedBBs, nullptr); + } - // Identify dead internal functions and delete them. This happens outside - // the other fixpoint analysis as we might treat potentially dead functions - // as live to lower the number of iterations. If they happen to be dead, the - // below fixpoint loop will identify and eliminate them. - SmallVector InternalFns; - for (Function *F : Functions) - if (F->hasLocalLinkage()) - InternalFns.push_back(F); - - bool FoundDeadFn = true; - while (FoundDeadFn) { - FoundDeadFn = false; - for (unsigned u = 0, e = InternalFns.size(); u < e; ++u) { - Function *F = InternalFns[u]; - if (!F) - continue; + // Identify dead internal functions and delete them. This happens outside + // the other fixpoint analysis as we might treat potentially dead functions + // as live to lower the number of iterations. If they happen to be dead, the + // below fixpoint loop will identify and eliminate them. + SmallVector InternalFns; + for (Function *F : Functions) + if (F->hasLocalLinkage()) + InternalFns.push_back(F); + + bool FoundDeadFn = true; + while (FoundDeadFn) { + FoundDeadFn = false; + for (unsigned u = 0, e = InternalFns.size(); u < e; ++u) { + Function *F = InternalFns[u]; + if (!F) + continue; - bool AllCallSitesKnown; - if (!checkForAllCallSites( - [this](AbstractCallSite ACS) { - return ToBeDeletedFunctions.count( - ACS.getInstruction()->getFunction()); - }, - *F, true, nullptr, AllCallSitesKnown)) - continue; + bool AllCallSitesKnown; + if (!checkForAllCallSites( + [this](AbstractCallSite ACS) { + return ToBeDeletedFunctions.count( + ACS.getInstruction()->getFunction()); + }, + *F, true, nullptr, AllCallSitesKnown)) + continue; - ToBeDeletedFunctions.insert(F); - InternalFns[u] = nullptr; - FoundDeadFn = true; - } + ToBeDeletedFunctions.insert(F); + InternalFns[u] = nullptr; + FoundDeadFn = true; } + } // Rewrite the functions as requested during manifest. - ChangeStatus ManifestChange = - rewriteFunctionSignatures(CGModifiedFunctions); + ChangeStatus ManifestChange = rewriteFunctionSignatures(CGModifiedFunctions); - for (Function *Fn : CGModifiedFunctions) - CGUpdater.reanalyzeFunction(*Fn); + for (Function *Fn : CGModifiedFunctions) + CGUpdater.reanalyzeFunction(*Fn); - for (Function *Fn : ToBeDeletedFunctions) - CGUpdater.removeFunction(*Fn); + for (Function *Fn : ToBeDeletedFunctions) + CGUpdater.removeFunction(*Fn); - NumFnDeleted += ToBeDeletedFunctions.size(); + NumFnDeleted += ToBeDeletedFunctions.size(); #ifdef EXPENSIVE_CHECKS for (Function *F : Functions) { @@ -1251,6 +1271,17 @@ ChangeStatus Attributor::run() { runTillFixpoint(); + + // dump graphs on demand + if (DumpDepGraph) + DG->dumpGraph(); + + if (ViewDepGraph) + DG->viewGraph(); + + if (PrintDependencies) + DG->print(); + ChangeStatus ManifestChange = manifestAttributes(); ChangeStatus CleanupChange = cleanupIR(); return ManifestChange | CleanupChange; @@ -2008,8 +2039,31 @@ } void AbstractAttribute::print(raw_ostream &OS) const { - OS << "[P: " << getIRPosition() << "][" << getAsStr() << "][S: " << getState() - << "]"; + OS << "["; + OS << getName(); + OS << "] for CtxI "; + + if (auto *I = getCtxI()) { + OS << "'"; + I->print(OS); + OS << "'"; + } else + OS << "<>"; + + OS << " at position " << getIRPosition() << " with state " << getAsStr() + << '\n'; +} + +void AbstractAttribute::printDeps(raw_ostream &OS) const { + print(OS); + + for (const auto DepAA : Deps) { + auto *AA = DepAA.getPointer(); + OS << " depends on "; + AA->print(OS); + } + + OS << '\n'; } ///} @@ -2031,6 +2085,8 @@ // while we identify default attribute opportunities. Attributor A(Functions, InfoCache, CGUpdater); + A.DG = new AADepGraph(A); + // Create shallow wrappers for all functions that are not IPO amendable if (AllowShallowWrappers) for (Function *F : Functions) @@ -2044,8 +2100,8 @@ NumFnWithoutExactDefinition++; // We look at internal functions only on-demand but if any use is not a - // direct call or outside the current set of analyzed functions, we have to - // do it eagerly. + // direct call or outside the current set of analyzed functions, we have + // to do it eagerly. if (F->hasLocalLinkage()) { if (llvm::all_of(F->uses(), [&Functions](const Use &U) { const auto *CB = dyn_cast(U.getUser()); @@ -2061,11 +2117,51 @@ } ChangeStatus Changed = A.run(); + LLVM_DEBUG(dbgs() << "[Attributor] Done with " << Functions.size() << " functions, result: " << Changed << ".\n"); return Changed == ChangeStatus::CHANGED; } +void Attributor::printAllDependency(raw_ostream &OS) { + for (AbstractAttribute *AA : AllAbstractAttributes) { + AA->printDeps(OS); + } +} + +void AADepGraph::viewGraph() { llvm::ViewGraph(this, "Dependency Graph"); } + +void AADepGraph::dumpGraph() { + static int CallTimes = 0; + std::string Filename = "dot_file_" + std::to_string(CallTimes) + ".dot"; + + errs() << "Dependency graph dump to " << Filename << ".\n"; + + std::error_code EC; + + raw_fd_ostream File(Filename, EC, sys::fs::OF_Text); + if (!EC) + llvm::WriteGraph(File, this); + + CallTimes++; +} + +void AADepGraph::print() { + SmallVector AAs; + AAs.reserve(A.AllAbstractAttributes.size()); + + for (auto tAA : A.AllAbstractAttributes) { + AAs.push_back(tAA); + } + + llvm::sort(AAs, [](AbstractAttribute *LHS, AbstractAttribute *RHS) { + return LHS->getName() < RHS->getName(); + }); + + for (AbstractAttribute *AA : AAs) + AA->printDeps(errs()); +} + PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) { FunctionAnalysisManager &FAM = AM.getResult(M).getManager(); @@ -2112,6 +2208,64 @@ return PreservedAnalyses::all(); } +namespace llvm { + +template <> struct llvm::GraphTraits { + using NodeRef = AbstractAttribute *; + using DepTy = PointerIntPair; + using EdgeRef = PointerIntPair; + + static NodeRef getEntryNode(AbstractAttribute *AA) { return AA; } + static NodeRef DepGetVal(DepTy &DT) { return DT.getPointer(); } + + using ChildIteratorType = + mapped_iterator::iterator, decltype(&DepGetVal)>; + using ChildEdgeIteratorType = TinyPtrVector::iterator; + + static ChildIteratorType child_begin(NodeRef N) { + return ChildIteratorType(N->getDeps().begin(), &DepGetVal); + } + + static ChildIteratorType child_end(NodeRef N) { + return ChildIteratorType(N->getDeps().end(), &DepGetVal); + } + + static ChildEdgeIteratorType child_edge_begin(NodeRef N) { + return N->getDeps().begin(); + } + + static ChildEdgeIteratorType child_edge_end(NodeRef N) { + return N->getDeps().end(); + } +}; + +template <> +struct llvm::GraphTraits + : public GraphTraits { + static NodeRef getEntryNode(AADepGraph *DG) { return DG->GetEntryNode(); } + + using nodes_iterator = SmallVector::iterator; + + static nodes_iterator nodes_begin(AADepGraph *DG) { return DG->begin(); } + + static nodes_iterator nodes_end(AADepGraph *DG) { return DG->end(); } +}; + +template <> +struct llvm::DOTGraphTraits : public DefaultDOTGraphTraits { + DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} + + static std::string getNodeLabel(const AbstractAttribute *Node, + const AADepGraph *DG) { + std::string AAString = ""; + raw_string_ostream O(AAString); + Node->print(O); + return AAString; + } +}; + +} // end namespace llvm + namespace { struct AttributorLegacyPass : public ModulePass { Index: llvm/lib/Transforms/IPO/AttributorAttributes.cpp =================================================================== --- llvm/lib/Transforms/IPO/AttributorAttributes.cpp +++ llvm/lib/Transforms/IPO/AttributorAttributes.cpp @@ -678,6 +678,8 @@ return getAssumed() ? "nounwind" : "may-unwind"; } + const std::string getName() const override { return "AANoUnwind"; } + /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { auto Opcodes = { @@ -851,6 +853,8 @@ /// Pretty print the attribute similar to the IR representation. const std::string getAsStr() const override; + const std::string getName() const override { return "AAReturnedValues"; } + /// See AbstractState::isAtFixpoint(). bool isAtFixpoint() const override { return IsFixed; } @@ -1051,9 +1055,10 @@ // map, NewRVsMap. decltype(ReturnedValues) NewRVsMap; - auto HandleReturnValue = [&](Value *RV, SmallSetVector &RIs) { - LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned value: " << *RV - << " by #" << RIs.size() << " RIs\n"); + auto HandleReturnValue = [&](Value *RV, + SmallSetVector &RIs) { + LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned value: " << *RV << " by #" + << RIs.size() << " RIs\n"); CallBase *CB = dyn_cast(RV); if (!CB || UnresolvedCalls.count(CB)) return; @@ -1208,6 +1213,8 @@ return getAssumed() ? "nosync" : "may-sync"; } + const std::string getName() const override { return "AANoSync"; } + /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override; @@ -1419,6 +1426,8 @@ const std::string getAsStr() const override { return getAssumed() ? "nofree" : "may-free"; } + + const std::string getName() const override { return "AANoFree"; } }; struct AANoFreeFunction final : public AANoFreeImpl { @@ -1704,6 +1713,8 @@ return getAssumed() ? "nonnull" : "may-null"; } + const std::string getName() const override { return "AANonNull"; } + /// Flag to determine if the underlying value can be null and still allow /// valid accesses. const bool NullIsDefined; @@ -1807,6 +1818,8 @@ const std::string getAsStr() const override { return getAssumed() ? "norecurse" : "may-recurse"; } + + const std::string getName() const override { return "AANoRecurse"; } }; struct AANoRecurseFunction final : AANoRecurseImpl { @@ -2033,6 +2046,8 @@ return getAssumed() ? "undefined-behavior" : "no-ub"; } + const std::string getName() const override { return "AAUndefinedBehavior"; } + /// Note: The correctness of this analysis depends on the fact that the /// following 2 sets will stop changing after some point. /// "Change" here means that their size changes. @@ -2179,6 +2194,8 @@ const std::string getAsStr() const override { return getAssumed() ? "willreturn" : "may-noreturn"; } + + const std::string getName() const override { return "AAWillReturn"; } }; struct AAWillReturnFunction final : AAWillReturnImpl { @@ -2231,6 +2248,8 @@ return "reachable"; } + const std::string getName() const override { return "AAReachability"; } + /// See AbstractAttribute::initialize(...). void initialize(Attributor &A) override { indicatePessimisticFixpoint(); } @@ -2259,6 +2278,8 @@ const std::string getAsStr() const override { return getAssumed() ? "noalias" : "may-alias"; } + + const std::string getName() const override { return "AANoAlias"; } }; /// NoAlias attribute for a floating value. @@ -2647,6 +2668,8 @@ return isAssumedDead() ? "assumed-dead" : "assumed-live"; } + const std::string getName() const override { return "AAIsDeadValue"; } + /// Check if all uses are assumed dead. bool areAllUsesAssumedDead(Attributor &A, Value &V) { auto UsePred = [&](const Use &U, bool &Follow) { return false; }; @@ -2866,6 +2889,10 @@ : (getAssumed() ? "assumed-dead-users" : "assumed-live"); } + const std::string getName() const override { + return "AAIsDeadCallSiteReturned"; + } + private: bool IsAssumedSideEffectFree; }; @@ -2933,6 +2960,8 @@ std::to_string(KnownDeadEnds.size()) + "]"; } + const std::string getName() const override { return "AAIsDeadFunction"; } + /// See AbstractAttribute::manifest(...). ChangeStatus manifest(Attributor &A) override { assert(getState().isValidState() && @@ -3390,6 +3419,8 @@ std::to_string(getKnownDereferenceableBytes()) + "-" + std::to_string(getAssumedDereferenceableBytes()) + ">"; } + + const std::string getName() const override { return "AADereferenceable"; } }; /// Dereferenceable attribute for a floating value. @@ -3424,7 +3455,6 @@ T.GlobalState &= DS.GlobalState; } - // For now we do not try to "increase" dereferenceability due to negative // indices as we first have to come up with code to deal with loops and // for overflows of the dereferenceable bytes. @@ -3682,6 +3712,8 @@ "-" + std::to_string(getAssumedAlign()) + ">") : "unknown-align"; } + + const std::string getName() const override { return "AAAlign"; } }; /// Align attribute for a floating value. @@ -3826,6 +3858,8 @@ return getAssumed() ? "noreturn" : "may-return"; } + const std::string getName() const override { return "AANoReturn"; } + /// See AbstractAttribute::updateImpl(Attributor &A). virtual ChangeStatus updateImpl(Attributor &A) override { auto CheckForNoReturn = [](Instruction &) { return false; }; @@ -3975,6 +4009,8 @@ return "assumed not-captured-maybe-returned"; return "assumed-captured"; } + + const std::string getName() const override { return "AANoCapture"; } }; /// Attributor-aware capture tracker. @@ -4316,6 +4352,8 @@ : "not-simple"; } + const std::string getName() const override { return "AAValueSimplify"; } + /// See AbstractAttribute::trackStatistics() void trackStatistics() const override {} @@ -4683,6 +4721,8 @@ return "[H2S] Mallocs: " + std::to_string(MallocCalls.size()); } + const std::string getName() const override { return "AAHeapToStack"; } + ChangeStatus manifest(Attributor &A) override { assert(getState().isValidState() && "Attempted to manifest an invalid state!"); @@ -4956,6 +4996,8 @@ return isAssumedPrivatizablePtr() ? "[priv]" : "[no-priv]"; } + const std::string getName() const override { return "AAPrivatizablePtr"; } + protected: Optional PrivatizableType; }; @@ -5594,6 +5636,8 @@ return "may-read/write"; } + const std::string getName() const override { return "AAMemoryBehavior"; } + /// The set of IR attributes AAMemoryBehavior deals with. static const Attribute::AttrKind AttrKinds[3]; }; @@ -6574,6 +6618,8 @@ return OS.str(); } + const std::string getName() const override { return "AAValueConstantRange"; } + /// Helper function to get a SCEV expr for the associated value at program /// point \p I. const SCEV *getSCEV(Attributor &A, const Instruction *I = nullptr) const { Index: llvm/test/Transforms/Attributor/depgraph.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/Attributor/depgraph.ll @@ -0,0 +1,88 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -passes=attributor-cgscc -disable-output -attributor-print-dep < %s 2>&1 | FileCheck %s + +; Test 0 +; +; test copied from the attributor introduction video: checkAndAdvance(), and the C code is: +; int *checkAndAdvance(int * __attribute__((aligned(16))) p) { +; if (*p == 0) +; return checkAndAdvance(p + 4); +; return p; +; } +; +define i32* @checkAndAdvance(i32* align 16 %0) { + %2 = alloca i32* + %3 = alloca i32* + store i32* %0, i32** %3 + %4 = load i32*, i32** %3 + %5 = load i32, i32* %4 + %6 = icmp eq i32 %5, 0 + br i1 %6, label %7, label %11 + +7: ; preds = %1 + %8 = load i32*, i32** %3 + %9 = getelementptr inbounds i32, i32* %8, i64 4 + %10 = call i32* @checkAndAdvance(i32* %9) + store i32* %10, i32** %2 + br label %13 + +11: ; preds = %1 + %12 = load i32*, i32** %3 + store i32* %12, i32** %2 + br label %13 + +13: ; preds = %11, %7 + %14 = load i32*, i32** %2 + ret i32* %14 +} + +; +; AAMemoryLocation +; + +; CHECK: [AAMemoryLocation] for CtxI ' %10 = call i32* @checkAndAdvance(i32* %9)' at position {cs: [@-1]} +; CHECK: depends on [AAMemoryLocation] for CtxI ' %2 = alloca i32*, align 8' at position {fn:checkAndAdvance [checkAndAdvance@-1]} + +; CHECK: [AAMemoryLocation] for CtxI ' %2 = alloca i32*, align 8' at position {fn:checkAndAdvance [checkAndAdvance@-1]} +; CHECK: depends on [AAMemoryLocation] for CtxI ' %10 = call i32* @checkAndAdvance(i32* %9)' at position {cs: [@-1]} +; CHECK: depends on [AAMemoryLocation] for CtxI ' %10 = call i32* @checkAndAdvance(i32* %9)' at position {cs: [@-1]} + +; +; AANoFree +; + +; CHECK: [AANoFree] for CtxI ' %2 = alloca i32*, align 8' at position {fn:checkAndAdvance [checkAndAdvance@-1]} +; CHECK: depends on [AANoFree] for CtxI ' %2 = alloca i32*, align 8' at position {arg: [@0]} +; CHECK: depends on [AANoFree] for CtxI ' %2 = alloca i32*, align 8' at position {arg: [@0]} +; CHECK: depends on [AANoFree] for CtxI ' %10 = call i32* @checkAndAdvance(i32* %9)' at position {cs: [@-1]} +; CHECK: depends on [AANoFree] for CtxI ' %10 = call i32* @checkAndAdvance(i32* %9)' at position {cs: [@-1]} + +; CHECK: [AANoFree] for CtxI ' %2 = alloca i32*, align 8' at position {arg: [@0]} +; CHECK: depends on [AANoFree] for CtxI ' %10 = call i32* @checkAndAdvance(i32* %9)' at position {cs_arg: [@0]} + +; CHECK: [AANoFree] for CtxI ' %10 = call i32* @checkAndAdvance(i32* %9)' at position {cs: [@-1]} +; CHECK: depends on [AANoFree] for CtxI ' %2 = alloca i32*, align 8' at position {fn:checkAndAdvance [checkAndAdvance@-1]} + +; +; AANoSync +; + +; CHECK: [AANoSync] for CtxI ' %10 = call i32* @checkAndAdvance(i32* %9)' at position {cs: [@-1]} with state nosync +; CHECK: depends on [AANoSync] for CtxI ' %2 = alloca i32*, align 8' at position {fn:checkAndAdvance [checkAndAdvance@-1]} with state nosync +; CHECK: depends on [AANoSync] for CtxI ' %2 = alloca i32*, align 8' at position {fn:checkAndAdvance [checkAndAdvance@-1]} with state nosync + +; CHECK: [AANoSync] for CtxI ' %2 = alloca i32*, align 8' at position {fn:checkAndAdvance [checkAndAdvance@-1]} with state nosync +; CHECK: depends on [AANoSync] for CtxI ' %10 = call i32* @checkAndAdvance(i32* %9)' at position {cs: [@-1]} with state nosync +; CHECK: depends on [AANoSync] for CtxI ' %10 = call i32* @checkAndAdvance(i32* %9)' at position {cs: [@-1]} with state nosync + +; CHECK: [AANoUnwind] for CtxI ' %2 = alloca i32*, align 8' at position {fn:checkAndAdvance [checkAndAdvance@-1]} with state nounwind +; CHECK: depends on [AANoUnwind] for CtxI ' %10 = call i32* @checkAndAdvance(i32* %9)' at position {cs: [@-1]} with state nounwind +; CHECK: depends on [AANoUnwind] for CtxI ' %10 = call i32* @checkAndAdvance(i32* %9)' at position {cs: [@-1]} with state nounwind + +; CHECK: [AANoUnwind] for CtxI ' %10 = call i32* @checkAndAdvance(i32* %9)' at position {cs: [@-1]} with state nounwind +; CHECK: depends on [AAIsDeadCallSiteReturned] for CtxI ' %10 = call i32* @checkAndAdvance(i32* %9)' at position {cs_ret: [@-1]} with state assumed-live +; CHECK: depends on [AANoUnwind] for CtxI ' %2 = alloca i32*, align 8' at position {fn:checkAndAdvance [checkAndAdvance@-1]} with state nounwind + +; CHECK: [AANonNull] for CtxI ' %9 = getelementptr inbounds i32, i32* %8, i64 4' at position {flt: [@-1]} with state nonnull +; CHECK: depends on [AANonNull] for CtxI ' %9 = getelementptr inbounds i32, i32* %8, i64 4' at position {flt: [@-1]} with state nonnull +; CHECK: depends on [AANonNull] for CtxI ' %10 = call i32* @checkAndAdvance(i32* %9)' at position {cs_arg: [@0]} with state nonnull