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 @@ -892,13 +892,15 @@ // TODO: use the function scope once we have call site AAReturnedValues. const IRPosition &QueryIRP = IRPosition::function(*AssociatedFunction); - const auto &LivenessAA = - getAAFor(QueryingAA, QueryIRP, /* TrackDependence */ false); + const auto *LivenessAA = + CheckBBLivenessOnly ? nullptr + : &(getAAFor(QueryingAA, QueryIRP, + /* TrackDependence */ false)); auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(*AssociatedFunction); if (!checkForAllInstructionsImpl(this, OpcodeInstMap, Pred, &QueryingAA, - &LivenessAA, Opcodes, CheckBBLivenessOnly)) + LivenessAA, Opcodes, CheckBBLivenessOnly)) return false; return true; 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 @@ -1168,7 +1168,19 @@ /// 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; + const Instruction *I, + Attributor &A) const = 0; + + /// Return an assumed unique ICV value if a single candidate is found. If + /// there cannot be one, return a nullptr. If it is not clear yet, return the + /// Optional::NoneType. + virtual Optional getUniqueReplacementValue(InternalControlVar ICV, + const Instruction *I, + Attributor &A) const = 0; + + /// Actual implementation of finding the unique ICV value. + virtual Optional getUniqueValue(InternalControlVar ICV, + Attributor &A) const = 0; /// Check if any value was tracked. virtual bool hasTrackedValue(InternalControlVar &ICV) const { return false; } @@ -1184,7 +1196,8 @@ /// See AbstractAttribute::getIdAddr() const char *getIdAddr() const override { return &ID; } - /// This function should return true if the type of the \p AA is AAICVTracker + /// This function should return true if the type of the \p AA is + /// AAICVTracker static bool classof(const AbstractAttribute *AA) { return (AA->getIdAddr() == &ID); } @@ -1240,18 +1253,13 @@ return Changed; } - // Map of ICV to their values at specific program point. - EnumeratedArray, InternalControlVar, - InternalControlVar::ICV___last> - ICVValuesMap; - // Map of ICV to their values at specific program point. EnumeratedArray, InternalControlVar, InternalControlVar::ICV___last> ICVReplacementValuesMap; bool hasTrackedValue(InternalControlVar &ICV) const override { - return !ICVValuesMap[ICV].empty(); + return !ICVReplacementValuesMap[ICV].empty(); } bool hasUnknownCall(InternalControlVar &ICV, Attributor &A) const override { @@ -1284,7 +1292,9 @@ // FIXME: handle setters with more that 1 arguments. /// Track new value. - if (ICVValuesMap[ICV].insert(ICVValue(CI, CI->getArgOperand(0)))) + if (ICVReplacementValuesMap[ICV] + .insert(std::make_pair(CI, CI->getArgOperand(0))) + .second) HasChanged = ChangeStatus::CHANGED; return false; @@ -1309,8 +1319,24 @@ return false; }; + auto CheckReturnInst = [&](Instruction &I) { + Value *ReplVal = getReplacementValue(ICV, &I, A); + if (ICVReplacementValuesMap[ICV] + .insert(std::make_pair(&I, ReplVal)) + .second) + HasChanged = ChangeStatus::CHANGED; + + return true; + }; + + // Track all changes of an ICV. SetterRFI.foreachUse(TrackValues, F); + // Map all getters to a value if possible. GetterRFI.foreachUse(MapReplacementValues, F); + // Get ICV value at every return instruction. If all return instruction + // have the same value, that is the ICV value after this function call. + A.checkForAllInstructions(CheckReturnInst, *this, {Instruction::Ret}, + /* CheckBBLivenessOnly */ true); } return HasChanged; @@ -1341,69 +1367,115 @@ A.getAAFor(*this, IRPosition::function(*CalledFunction)); if (ICVTrackingAA.isAssumedTracked()) - return !ICVTrackingAA.hasTrackedValue(ICV) && + return ICVTrackingAA.hasTrackedValue(ICV) && ICVTrackingAA.hasUnknownCall(ICV, A); return true; } + Optional getUniqueReplacementValue(InternalControlVar ICV, + const Instruction *I, + Attributor &A) const override { + Optional UniqueReplVal; + const auto *CB = dyn_cast(I); + assert(CB && "Instruction must be a call."); + + Function *CalledFunction = CB->getCalledFunction(); + + if (CalledFunction->isDeclaration()) { + UniqueReplVal = nullptr; + return UniqueReplVal; + } + + const auto &ICVTrackingAA = + A.getAAFor(*this, IRPosition::function(*CalledFunction)); + + if (ICVTrackingAA.isAssumedTracked()) + return ICVTrackingAA.getUniqueValue(ICV, A); + + UniqueReplVal = nullptr; + return UniqueReplVal; + } + + Optional getUniqueValue(InternalControlVar ICV, + Attributor &A) const override { + Optional UniqueICVValue; + auto CheckReturnInst = [&](Instruction &I) { + Value *ReplVal = getReplacementValue(ICV, &I, A); + + // If we found a second ICV value there is no unique returned value. + if (UniqueICVValue.hasValue() && UniqueICVValue != ReplVal) { + UniqueICVValue = nullptr; + return false; + } + + UniqueICVValue = ReplVal; + + return true; + }; + + if (!A.checkForAllInstructions(CheckReturnInst, *this, {Instruction::Ret}, + /* CheckBBLivenessOnly */ true)) + UniqueICVValue = nullptr; + + return UniqueICVValue; + } + /// Return the value with which \p I can be replaced for specific \p ICV. Value *getReplacementValue(InternalControlVar ICV, const Instruction *I, - Attributor &A) override { + Attributor &A) const override { if (ICVReplacementValuesMap[ICV].count(I)) return ICVReplacementValuesMap[ICV].lookup(I); const BasicBlock *CurrBB = I->getParent(); - auto &ValuesSet = ICVValuesMap[ICV]; - - for (const auto &ICVVal : ValuesSet) { - if (CurrBB == ICVVal.Inst->getParent()) { - if (!ICVVal.Inst->comesBefore(I)) - continue; + auto &ValuesMap = ICVReplacementValuesMap[ICV]; - // both instructions are in the same BB and at \p I we know the ICV - // value. - const Instruction *CurrInst = I; - while (CurrInst != ICVVal.Inst) { - // we don't yet know if a call might update an ICV. - // TODO: check callsite AA for value. - if (callChangesICV(A, CurrInst, ICV)) - return nullptr; + // both instructions are in the same BB and at \p I we know the ICV + // value. + const Instruction *CurrInst = I; + while ((CurrInst = CurrInst->getPrevNode())) { + if (ValuesMap.count(CurrInst)) + return ValuesMap.lookup(CurrInst); - CurrInst = CurrInst->getPrevNode(); - } + // TODO: check callsite AA for value. + if (!callChangesICV(A, CurrInst, ICV)) + continue; - // No call in between, return the value. - return ICVVal.TrackedValue; - } + Optional UniqueReplVal = + getUniqueReplacementValue(ICV, CurrInst, A); + // if we have value return it. + if (UniqueReplVal.hasValue()) + return UniqueReplVal.getValue(); - auto &OMPInfoCache = static_cast(A.getInfoCache()); - auto &Explorer = OMPInfoCache.getMustBeExecutedContextExplorer(); - for (const BasicBlock *Pred : predecessors(CurrBB)) { - if (ICVVal.Inst->getParent() == Pred) { - if (!Explorer.findInContextOf(ICVVal.Inst, I)) - return nullptr; - Instruction *CurrInst = ICVVal.Inst->getNextNode(); - while (CurrInst != Pred->getTerminator()) { - // If any of the calls after the tracked value, might change the - // ICV, we don't know the value. - if (callChangesICV(A, CurrInst, ICV)) - return nullptr; - CurrInst = CurrInst->getNextNode(); - } - return ICVVal.TrackedValue; - } + return nullptr; + } - // if any of the calls in a block that doesn't have tracked value might - // change the ICV, we don't know the value. - for (const Instruction &Inst : *Pred) - if (callChangesICV(A, &Inst, ICV)) - return nullptr; + auto &OMPInfoCache = static_cast(A.getInfoCache()); + auto &Explorer = OMPInfoCache.getMustBeExecutedContextExplorer(); + for (const BasicBlock *Pred : predecessors(CurrBB)) { + for (auto It = Pred->rbegin(), E = Pred->rend(); It != E; ++It) { + // Find a call that changes the ICV and if the value is tracked, return + // it. + const Instruction *CurrInst = &*It; + if (!callChangesICV(A, CurrInst, ICV)) + continue; + if (!Explorer.findInContextOf(CurrInst, I)) + return nullptr; + if (ICVReplacementValuesMap[ICV].count(CurrInst)) + return ICVReplacementValuesMap[ICV].lookup(CurrInst); + + Optional UniqueReplVal = + getUniqueReplacementValue(ICV, CurrInst, A); + // if we have a value, return it. + if (UniqueReplVal.hasValue()) + return UniqueReplVal.getValue(); + + return nullptr; } } - // No value was tracked. + // Couldn't find a replacement value. return nullptr; } }; 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 @@ -1,4 +1,4 @@ -; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes --check-attributes ; RUN: opt -S -openmpopt < %s | FileCheck %s ; RUN: opt -S -passes=openmpopt < %s | FileCheck %s @@ -251,6 +251,34 @@ ret void } + +define void @known_unique_icv(i1 %0) { +; CHECK-LABEL: define {{[^@]+}}@known_unique_icv +; CHECK-SAME: (i1 [[TMP0:%.*]]) +; CHECK-NEXT: call void @omp_set_num_threads(i32 2) +; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i1 [[TMP0]], false +; CHECK-NEXT: br i1 [[TMP2]], label [[TMP5:%.*]], label [[TMP3:%.*]] +; CHECK: 3: +; CHECK-NEXT: [[TMP4:%.*]] = call i32 @icv_free_use(i32 10) +; CHECK-NEXT: br label [[TMP5]] +; CHECK: 5: +; CHECK-NEXT: [[TMP6:%.*]] = call i32 @icv_free_use(i32 2) +; CHECK-NEXT: ret void +; + call void @omp_set_num_threads(i32 2) + %2 = icmp eq i1 %0, 0 + br i1 %2, label %5, label %3 + +3: ; preds = %1 + %4 = call i32 @icv_free_use(i32 10) + br label %5 + +5: ; preds = %3, %1 + %6 = call i32 @omp_get_max_threads() + %7 = call i32 @icv_free_use(i32 %6) + ret void +} + define void @test2(i1 %0) { ; CHECK-LABEL: define {{[^@]+}}@test2 ; CHECK-SAME: (i1 [[TMP0:%.*]]) @@ -263,6 +291,32 @@ ; CHECK-NEXT: [[TMP5:%.*]] = call i32 @omp_get_max_threads() ; CHECK-NEXT: call void @use(i32 [[TMP5]]) ; CHECK-NEXT: ret void +; +%2 = icmp eq i1 %0, 0 + br i1 %2, label %4, label %3 + +3: ; preds = %1 + call void @omp_set_num_threads(i32 4) + br label %4 + +4: ; preds = %3, %1 + %5 = call i32 @omp_get_max_threads() + call void @use(i32 %5) + ret void +} + +define void @test3(i1 %0) { +; CHECK-LABEL: define {{[^@]+}}@test3 +; CHECK-SAME: (i1 [[TMP0:%.*]]) +; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i1 [[TMP0]], false +; CHECK-NEXT: br i1 [[TMP2]], label [[TMP4:%.*]], label [[TMP3:%.*]] +; CHECK: 3: +; CHECK-NEXT: call void @omp_set_num_threads(i32 4) +; CHECK-NEXT: br label [[TMP4]] +; CHECK: 4: +; CHECK-NEXT: call void @known_unique_icv(i1 [[TMP0]]) +; CHECK-NEXT: [[TMP5:%.*]] = call i32 @icv_free_use(i32 2) +; CHECK-NEXT: ret void ; %2 = icmp eq i1 %0, 0 br i1 %2, label %4, label %3 @@ -271,8 +325,37 @@ call void @omp_set_num_threads(i32 4) br label %4 +4: ; preds = %3, %1 + call void @known_unique_icv(i1 %0) + %5 = call i32 @omp_get_max_threads() + %6 = call i32 @icv_free_use(i32 %5) + ret void +} + +define void @test4(i1 %0) { +; CHECK-LABEL: define {{[^@]+}}@test4 +; CHECK-SAME: (i1 [[TMP0:%.*]]) +; CHECK-NEXT: call void @known_unique_icv(i1 [[TMP0]]) +; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i1 [[TMP0]], false +; CHECK-NEXT: br i1 [[TMP2]], label [[TMP4:%.*]], label [[TMP3:%.*]] +; CHECK: 3: +; CHECK-NEXT: [[VAL:%.*]] = call i32 @icv_free_use(i32 10) +; CHECK-NEXT: br label [[TMP4]] +; CHECK: 4: +; CHECK-NEXT: call void @use(i32 2) +; CHECK-NEXT: ret void +; + call void @known_unique_icv(i1 %0) + %2 = icmp eq i1 %0, 0 + br i1 %2, label %4, label %3 + +3: ; preds = %1 + %val = call i32 @icv_free_use(i32 10) + br label %4 + 4: ; preds = %3, %1 %5 = call i32 @omp_get_max_threads() + ; %6 = call i32 @icv_free_use(i32 %5) call void @use(i32 %5) ret void }