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,14 @@ 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 @@ -54,8 +54,47 @@ static constexpr auto TAG = "[" DEBUG_TYPE "]"; #endif +/// Helper struct to store tracked ICV values at specif instructions. +struct ICVValue { + Instruction *Inst; + Value *TrackedValue; + + ICVValue(Instruction *I, Value *Val) : Inst(I), TrackedValue(Val) {} +}; + +namespace llvm { + +// Provide DenseMapInfo for ICVValue +template <> struct DenseMapInfo { + using InstInfo = DenseMapInfo; + using ValueInfo = DenseMapInfo; + + static inline ICVValue getEmptyKey() { + return ICVValue(InstInfo::getEmptyKey(), ValueInfo::getEmptyKey()); + }; + + static inline ICVValue getTombstoneKey() { + return ICVValue(InstInfo::getTombstoneKey(), ValueInfo::getTombstoneKey()); + }; + + static unsigned getHashValue(const ICVValue &ICVVal) { + return detail::combineHashValue( + InstInfo::getHashValue(ICVVal.Inst), + ValueInfo::getHashValue(ICVVal.TrackedValue)); + } + + static bool isEqual(const ICVValue &LHS, const ICVValue &RHS) { + return InstInfo::isEqual(LHS.Inst, RHS.Inst) && + ValueInfo::isEqual(LHS.TrackedValue, RHS.TrackedValue); + } +}; + +} // end namespace llvm + namespace { +struct AAICVTracker; + /// OpenMP specific information. For now, stores RFIs and ICVs also needed for /// Attributor runs. struct OMPInformationCache : public InformationCache { @@ -122,9 +161,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; } @@ -180,7 +219,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. @@ -330,9 +369,9 @@ OpenMPOpt(SmallVectorImpl &SCC, CallGraphUpdater &CGUpdater, OptimizationRemarkGetter OREGetter, - OMPInformationCache &OMPInfoCache) + OMPInformationCache &OMPInfoCache, Attributor &A) : M(*(*SCC.begin())->getParent()), SCC(SCC), CGUpdater(CGUpdater), - OREGetter(OREGetter), OMPInfoCache(OMPInfoCache) {} + OREGetter(OREGetter), OMPInfoCache(OMPInfoCache), A(A) {} /// Run all OpenMP optimizations on the underlying SCC/ModuleSlice. bool run() { @@ -363,6 +402,7 @@ } } + Changed |= runAttributor(); Changed |= deduplicateRuntimeCalls(); Changed |= deleteParallelRegions(); @@ -724,9 +764,206 @@ /// OpenMP-specific information cache. Also Used for Attributor runs. OMPInformationCache &OMPInfoCache; + + /// Attributor instance. + Attributor &A; + + /// Helper function to run Attributor on SCC. + 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; + } + + /// Populate the Attributor with abstract attribute opportunities in the + /// function. + void registerAAs() { + for (Function *F : SCC) { + if (F->isDeclaration()) + continue; + + A.getOrCreateAAFor(IRPosition::function(*F)); + } + } +}; + +/// Abstract Attribute for tracking ICV values. +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(); } + + /// Create an abstract attribute biew for the position \p IRP. + static AAICVTracker &createForPosition(const IRPosition &IRP, Attributor &A); + + /// Return the value with which \p I can be replaced for specific \p ICV. + virtual Value *getReplacementValue(InternalControlVar ICV, + const Instruction *I, Attributor &A) = 0; + + /// See AbstractAttribute::getName() + const std::string getName() const override { return "AAICVTracker"; } + + 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) { + auto &OMPInfoCache = static_cast(A.getInfoCache()); + auto &ICVInfo = OMPInfoCache.ICVs[ICV]; + auto &GetterRFI = OMPInfoCache.RFIs[ICVInfo.Getter]; + + bool Changed = false; + + auto ReplaceAndDeleteCB = [&](Use &U, Function &Caller) { + CallInst *CI = OpenMPOpt::getCallIfRegularCall(U, &GetterRFI); + 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; + }; + + GetterRFI.foreachUse(ReplaceAndDeleteCB); + return Changed; + } + + // Map of ICV to their values at specific program point. + EnumeratedArray, 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 &SetterRFI = 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(ICVValue(CI, CI->getArgOperand(0)))) + HasChanged = ChangeStatus::CHANGED; + + return false; + }; + + SetterRFI.foreachUse(TrackValues, F); + } + + return HasChanged; + } + + /// Return the value with which \p I can be replaced for specific \p ICV. + Value *getReplacementValue(InternalControlVar ICV, const Instruction *I, + Attributor &A) override { + const BasicBlock *CurrBB = I->getParent(); + + auto &ValuesSet = ICVValuesMap[ICV]; + auto &OMPInfoCache = static_cast(A.getInfoCache()); + auto &GetterRFI = OMPInfoCache.RFIs[OMPInfoCache.ICVs[ICV].Getter]; + + for (const auto &ICVVal : ValuesSet) { + if (CurrBB == ICVVal.Inst->getParent()) { + if (!ICVVal.Inst->comesBefore(I)) + continue; + + // both instructions are in the same BB and at \p I we know the ICV + // value. + while (I != ICVVal.Inst) { + // we don't yet know if a call might update an ICV. + // TODO: check callsite AA for value. + if (const auto *CB = dyn_cast(I)) + if (CB->getCalledFunction() != GetterRFI.Declaration) + return nullptr; + + I = I->getPrevNode(); + } + + // No call in between, return the value. + return ICVVal.TrackedValue; + } + } + + // 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) { @@ -763,8 +1000,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(); @@ -828,8 +1067,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,15 +47,13 @@ ; 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. %3 = tail call i32 @omp_get_max_threads() %4 = tail call i32 @omp_get_max_threads() tail call void @use(i32 %4) -; FIXME: this value ( min(%3, 10) ) should be tracked and the rest of the getters deduplicated and replaced with it. tail call void @omp_set_num_threads(i32 10) %5 = tail call i32 @omp_get_max_threads() tail call void @use(i32 %5) @@ -74,10 +68,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 +90,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()