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 @@ -1036,6 +1036,13 @@ identifyDefaultAbstractAttributes(const_cast(F)); } + /// Helper function to remove callsite. + void removeCallSite(CallInst *CI) { + if (!CI) + return; + + CGUpdater.removeCallSite(*CI); + } /// Record that \p U is to be replaces with \p NV after information was /// manifested. This also triggers deletion of trivially dead istructions. bool changeUseAfterManifest(Use &U, Value &NV) { diff --git a/llvm/lib/Transforms/IPO/OpenMPOpt.cpp b/llvm/lib/Transforms/IPO/OpenMPOpt.cpp --- a/llvm/lib/Transforms/IPO/OpenMPOpt.cpp +++ b/llvm/lib/Transforms/IPO/OpenMPOpt.cpp @@ -56,6 +56,7 @@ namespace { +struct AAICVTracker; /// OpenMP specific information. For now, stores RFIs and ICVs also needed for /// Attributor runs. struct OMPInformationCache : public InformationCache { @@ -124,9 +125,9 @@ /// Return the vector of uses in function \p F. UseVector &getOrCreateUseVector(Function *F) { - std::unique_ptr &UV = UsesMap[F]; + std::shared_ptr &UV = UsesMap[F]; if (!UV) - UV = std::make_unique(); + UV = std::make_shared(); return *UV; } @@ -182,7 +183,7 @@ private: /// Map from functions to all uses of this runtime function contained in /// them. - DenseMap> UsesMap; + DenseMap> UsesMap; }; /// The slice of the module we are allowed to look at. @@ -332,10 +333,10 @@ OpenMPOpt(SmallVectorImpl &SCC, CallGraphUpdater &CGUpdater, OptimizationRemarkGetter OREGetter, - OMPInformationCache &OMPInfoCache) + OMPInformationCache &OMPInfoCache, Attributor &A) : M(*(*SCC.begin())->getParent()), SCC(SCC), ModuleSlice(OMPInfoCache.ModuleSlice), CGUpdater(CGUpdater), - OREGetter(OREGetter), OMPInfoCache(OMPInfoCache) {} + OREGetter(OREGetter), OMPInfoCache(OMPInfoCache), A(A) {} /// Run all OpenMP optimizations on the underlying SCC/ModuleSlice. bool run() { @@ -366,6 +367,8 @@ } } + Changed |= runAttributor(); + Changed |= deduplicateRuntimeCalls(); Changed |= deleteParallelRegions(); @@ -730,9 +733,206 @@ /// OpenMP-specific information cache. Also Used for Attributor runs. OMPInformationCache &OMPInfoCache; + + /// Attributor instance. + Attributor &A; + + bool runAttributor() { + if (SCC.empty()) + return false; + + registerAAs(); + + ChangeStatus Changed = A.run(); + + LLVM_DEBUG(dbgs() << "[Attributor] Done with " << SCC.size() + << " functions, result: " << Changed << ".\n"); + + return Changed == ChangeStatus::CHANGED; + } + + void registerAAs() { + for (Function *F : SCC) { + if (F->isDeclaration()) + continue; + + A.getOrCreateAAFor(IRPosition::function(*F)); + } + } +}; + +struct AAICVTracker : public StateWrapper { + using Base = StateWrapper; + AAICVTracker(const IRPosition &IRP, Attributor &A) : Base(IRP) {} + + /// Returns true if value is assumed to be tracked. + bool isAssumedTracked() const { return getAssumed(); } + + /// Returns true if value is known to be tracked. + bool isKnownTracked() const { return getAssumed(); } + + /// TODO: figure out how to get hold of ICV infos here. + /// Create an abstract attribute biew for the position \p IRP. + static AAICVTracker &createForPosition(const IRPosition &IRP, Attributor &A); + + virtual Value *getReplacementValue(InternalControlVar ICV, + const Instruction *I, Attributor &A) = 0; + + static const char ID; +}; + +struct AAICVTrackerFunction : public AAICVTracker { + AAICVTrackerFunction(const IRPosition &IRP, Attributor &A) + : AAICVTracker(IRP, A) {} + + // FIXME: come up with better string. + const std::string getAsStr() const override { return "ICVTracker"; } + + // FIXME: come up with some stats. + void trackStatistics() const override {} + + /// TODO: decide whether to deduplicate here, or use current + /// deduplicateRuntimeCalls function. + ChangeStatus manifest(Attributor &A) override { + ChangeStatus Changed = ChangeStatus::UNCHANGED; + + for (InternalControlVar ICV : TrackableICVs) + if (deduplicateICVGetters(ICV, A)) + Changed = ChangeStatus::CHANGED; + + return Changed; + } + + bool deduplicateICVGetters(InternalControlVar ICV, Attributor &A) { + Function *F = getAnchorScope(); + + auto &OMPInfoCache = static_cast(A.getInfoCache()); + auto ICVInfo = OMPInfoCache.ICVs[ICV]; + auto Getter = OMPInfoCache.RFIs[ICVInfo.Getter]; + + auto *UV = Getter.getUseVector(*F); + + if (!UV || UV->size() == 0) + return false; + + bool Changed = false; + + auto ReplaceAndDeleteCB = [&](Use &U, Function &Caller) { + CallInst *CI = OpenMPOpt::getCallIfRegularCall(U, &Getter); + Instruction *UserI = cast(U.getUser()); + Value *ReplVal = getReplacementValue(ICV, UserI, A); + + if (!ReplVal || !CI) + return false; + + A.removeCallSite(CI); + CI->replaceAllUsesWith(ReplVal); + CI->eraseFromParent(); + Changed = true; + return true; + }; + + Getter.foreachUse(ReplaceAndDeleteCB); + return Changed; + } + + // Map of ICV to their values at specific program point. + EnumeratedArray, 4>, + InternalControlVar, InternalControlVar::ICV___last> + ICVValuesMap; + + // Currently only nthreads is being tracked. + // this array will only grow with time. + InternalControlVar TrackableICVs[1] = {ICV_nthreads}; + + ChangeStatus updateImpl(Attributor &A) override { + ChangeStatus HasChanged = ChangeStatus::UNCHANGED; + + Function *F = getAnchorScope(); + + auto &OMPInfoCache = static_cast(A.getInfoCache()); + + for (InternalControlVar ICV : TrackableICVs) { + auto Setter = OMPInfoCache.RFIs[OMPInfoCache.ICVs[ICV].Setter]; + + auto TrackValues = [&](Use &U, Function &) { + CallInst *CI = OpenMPOpt::getCallIfRegularCall(U); + if (!CI) + return false; + + // FIXME: handle setters with more that 1 arguments. + /// Track new value. + if (ICVValuesMap[ICV].insert(std::make_pair(CI, CI->getArgOperand(0)))) + HasChanged = ChangeStatus::CHANGED; + + return false; + }; + + Setter.foreachUse(TrackValues, F); + } + + return HasChanged; + } + + /// Return the value with which \p can be replaced. + Value *getReplacementValue(InternalControlVar ICV, const Instruction *I, + Attributor &A) override { + BasicBlock *CurrBB = const_cast(I->getParent()); + + auto ValuesSet = ICVValuesMap[ICV]; + + auto &OMPInfoCache = static_cast(A.getInfoCache()); + auto Getter = OMPInfoCache.RFIs[OMPInfoCache.ICVs[ICV].Getter]; + for (auto &pair : ValuesSet) { + if (CurrBB == pair.first->getParent()) { + if (!pair.first->comesBefore(I)) + continue; + + // both instructions are in the same BB and at \p I we know the ICV + // value. + while (I != pair.first) { + // we don't yet know if a call might update an ICV. + // TODO: check callsite AA for value. + if (auto *CB = dyn_cast(I)) + if (CB->getCalledFunction() != Getter.Declaration) + return nullptr; + + I = I->getPrevNode(); + } + + // No call in between, return the value. + return pair.second; + } + } + + // No value was tracked. + return nullptr; + } }; } // namespace +const char AAICVTracker::ID = 0; + +AAICVTracker &AAICVTracker::createForPosition(const IRPosition &IRP, + Attributor &A) { + AAICVTracker *AA = nullptr; + switch (IRP.getPositionKind()) { + case IRPosition::IRP_INVALID: + case IRPosition::IRP_FLOAT: + case IRPosition::IRP_ARGUMENT: + case IRPosition::IRP_RETURNED: + case IRPosition::IRP_CALL_SITE_RETURNED: + case IRPosition::IRP_CALL_SITE_ARGUMENT: + case IRPosition::IRP_CALL_SITE: + llvm_unreachable("ICVTracker can only be created for function position!"); + case IRPosition::IRP_FUNCTION: + AA = new (A.Allocator) AAICVTrackerFunction(IRP, A); + break; + } + + return *AA; +} + PreservedAnalyses OpenMPOptPass::run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR) { @@ -769,8 +969,10 @@ OMPInformationCache InfoCache(*(Functions.back()->getParent()), AG, Allocator, /*CGSCC*/ &Functions, ModuleSlice); + Attributor A(Functions, InfoCache, CGUpdater); + // TODO: Compute the module slice we are allowed to look at. - OpenMPOpt OMPOpt(SCC, CGUpdater, OREGetter, InfoCache); + OpenMPOpt OMPOpt(SCC, CGUpdater, OREGetter, InfoCache, A); bool Changed = OMPOpt.run(); (void)Changed; return PreservedAnalyses::all(); @@ -834,8 +1036,10 @@ Allocator, /*CGSCC*/ &Functions, ModuleSlice); + Attributor A(Functions, InfoCache, CGUpdater); + // TODO: Compute the module slice we are allowed to look at. - OpenMPOpt OMPOpt(SCC, CGUpdater, OREGetter, InfoCache); + OpenMPOpt OMPOpt(SCC, CGUpdater, OREGetter, InfoCache, A); return OMPOpt.run(); } diff --git a/llvm/test/Transforms/OpenMP/icv_tracking.ll b/llvm/test/Transforms/OpenMP/icv_tracking.ll --- a/llvm/test/Transforms/OpenMP/icv_tracking.ll +++ b/llvm/test/Transforms/OpenMP/icv_tracking.ll @@ -11,16 +11,12 @@ ; CHECK-LABEL: define {{[^@]+}}@foo ; CHECK-SAME: (i32 [[TMP0:%.*]], i32 [[TMP1:%.*]]) ; CHECK-NEXT: tail call void @omp_set_num_threads(i32 [[TMP0]]) -; CHECK-NEXT: [[TMP3:%.*]] = tail call i32 @omp_get_max_threads() ; CHECK-NEXT: tail call void @omp_set_num_threads(i32 [[TMP1]]) -; CHECK-NEXT: [[TMP4:%.*]] = tail call i32 @omp_get_max_threads() -; CHECK-NEXT: [[TMP5:%.*]] = tail call i32 @omp_get_max_threads() -; CHECK-NEXT: [[TMP6:%.*]] = tail call i32 @omp_get_max_threads() -; CHECK-NEXT: tail call void @use(i32 [[TMP4]]) -; CHECK-NEXT: tail call void @use(i32 [[TMP5]]) +; CHECK-NEXT: tail call void @use(i32 [[TMP1]]) +; CHECK-NEXT: tail call void @use(i32 [[TMP1]]) ; CHECK-NEXT: tail call void (%struct.ident_t*, i32, void (i32*, i32*, ...)*, ...) @__kmpc_fork_call(%struct.ident_t* nonnull @0, i32 0, void (i32*, i32*, ...)* bitcast (void (i32*, i32*)* @.omp_outlined. to void (i32*, i32*, ...)*)) -; CHECK-NEXT: [[TMP7:%.*]] = tail call i32 @omp_get_max_threads() -; CHECK-NEXT: tail call void @use(i32 [[TMP7]]) +; CHECK-NEXT: [[TMP3:%.*]] = tail call i32 @omp_get_max_threads() +; CHECK-NEXT: tail call void @use(i32 [[TMP3]]) ; CHECK-NEXT: ret i32 0 ; tail call void @omp_set_num_threads(i32 %0) @@ -51,8 +47,7 @@ ; CHECK-NEXT: [[TMP4:%.*]] = tail call i32 @omp_get_max_threads() ; CHECK-NEXT: tail call void @use(i32 [[TMP4]]) ; CHECK-NEXT: tail call void @omp_set_num_threads(i32 10) -; CHECK-NEXT: [[TMP5:%.*]] = tail call i32 @omp_get_max_threads() -; CHECK-NEXT: tail call void @use(i32 [[TMP5]]) +; CHECK-NEXT: tail call void @use(i32 10) ; CHECK-NEXT: ret void ; ; FIXME: this value should be tracked and the rest of the getters deduplicated and replaced with it. @@ -74,10 +69,9 @@ ; CHECK-NEXT: [[TMP3:%.*]] = icmp sgt i32 [[TMP0]], [[TMP1]] ; CHECK-NEXT: [[TMP4:%.*]] = select i1 [[TMP3]], i32 [[TMP0]], i32 [[TMP1]] ; CHECK-NEXT: tail call void @omp_set_num_threads(i32 [[TMP4]]) -; CHECK-NEXT: [[TMP5:%.*]] = tail call i32 @omp_get_max_threads() ; CHECK-NEXT: tail call void (%struct.ident_t*, i32, void (i32*, i32*, ...)*, ...) @__kmpc_fork_call(%struct.ident_t* nonnull @0, i32 0, void (i32*, i32*, ...)* bitcast (void (i32*, i32*)* @.omp_outlined..1 to void (i32*, i32*, ...)*)) -; CHECK-NEXT: [[TMP6:%.*]] = tail call i32 @omp_get_max_threads() -; CHECK-NEXT: tail call void @use(i32 [[TMP6]]) +; CHECK-NEXT: [[TMP5:%.*]] = tail call i32 @omp_get_max_threads() +; CHECK-NEXT: tail call void @use(i32 [[TMP5]]) ; CHECK-NEXT: ret i32 0 ; %3 = icmp sgt i32 %0, %1 @@ -97,10 +91,9 @@ ; CHECK-NEXT: [[TMP3:%.*]] = tail call i32 @omp_get_max_threads() ; CHECK-NEXT: tail call void @use(i32 [[TMP3]]) ; CHECK-NEXT: tail call void @omp_set_num_threads(i32 10) +; CHECK-NEXT: tail call void @use(i32 10) ; CHECK-NEXT: [[TMP4:%.*]] = tail call i32 @omp_get_max_threads() ; CHECK-NEXT: tail call void @use(i32 [[TMP4]]) -; CHECK-NEXT: [[TMP5:%.*]] = tail call i32 @omp_get_max_threads() -; CHECK-NEXT: tail call void @use(i32 [[TMP5]]) ; CHECK-NEXT: ret void ; %3 = tail call i32 @omp_get_max_threads()