diff --git a/llvm/include/llvm/Analysis/FunctionPropertiesAnalysis.h b/llvm/include/llvm/Analysis/FunctionPropertiesAnalysis.h --- a/llvm/include/llvm/Analysis/FunctionPropertiesAnalysis.h +++ b/llvm/include/llvm/Analysis/FunctionPropertiesAnalysis.h @@ -20,6 +20,7 @@ #include "llvm/IR/PassManager.h" namespace llvm { +class DominatorTree; class Function; class LoopInfo; @@ -27,11 +28,11 @@ friend class FunctionPropertiesUpdater; void updateForBB(const BasicBlock &BB, int64_t Direction); void updateAggregateStats(const Function &F, const LoopInfo &LI); - void reIncludeBB(const BasicBlock &BB, const LoopInfo &LI); + void reIncludeBB(const BasicBlock &BB); public: - static FunctionPropertiesInfo getFunctionPropertiesInfo(const Function &F, - const LoopInfo &LI); + static FunctionPropertiesInfo + getFunctionPropertiesInfo(const Function &F, FunctionAnalysisManager &FAM); bool operator==(const FunctionPropertiesInfo &FPI) const { return std::memcmp(this, &FPI, sizeof(FunctionPropertiesInfo)) == 0; @@ -111,7 +112,7 @@ public: FunctionPropertiesUpdater(FunctionPropertiesInfo &FPI, const CallBase &CB); - void finish(const LoopInfo &LI) const; + void finish(FunctionAnalysisManager &FAM) const; private: FunctionPropertiesInfo &FPI; diff --git a/llvm/include/llvm/Analysis/MLInlineAdvisor.h b/llvm/include/llvm/Analysis/MLInlineAdvisor.h --- a/llvm/include/llvm/Analysis/MLInlineAdvisor.h +++ b/llvm/include/llvm/Analysis/MLInlineAdvisor.h @@ -103,7 +103,7 @@ const int64_t CallerIRSize; const int64_t CalleeIRSize; const int64_t CallerAndCalleeEdges; - void updateCachedCallerFPI(const LoopInfo &LI) const; + void updateCachedCallerFPI(FunctionAnalysisManager &FAM) const; private: void reportContextForRemark(DiagnosticInfoOptimizationBase &OR); diff --git a/llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp b/llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp --- a/llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp +++ b/llvm/lib/Analysis/FunctionPropertiesAnalysis.cpp @@ -13,8 +13,10 @@ #include "llvm/Analysis/FunctionPropertiesAnalysis.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SetVector.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/IR/CFG.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/Instructions.h" #include @@ -37,11 +39,8 @@ } } // namespace -void FunctionPropertiesInfo::reIncludeBB(const BasicBlock &BB, - const LoopInfo &LI) { +void FunctionPropertiesInfo::reIncludeBB(const BasicBlock &BB) { updateForBB(BB, +1); - MaxLoopDepth = - std::max(MaxLoopDepth, static_cast(LI.getLoopDepth(&BB))); } void FunctionPropertiesInfo::updateForBB(const BasicBlock &BB, @@ -70,16 +69,29 @@ Uses = getUses(F); TopLevelLoopCount = llvm::size(LI); + MaxLoopDepth = 0; + std::deque Worklist; + llvm::append_range(Worklist, LI); + while (!Worklist.empty()) { + const auto *L = Worklist.front(); + MaxLoopDepth = + std::max(MaxLoopDepth, static_cast(L->getLoopDepth())); + Worklist.pop_front(); + llvm::append_range(Worklist, L->getSubLoops()); + } } -FunctionPropertiesInfo -FunctionPropertiesInfo::getFunctionPropertiesInfo(const Function &F, - const LoopInfo &LI) { +FunctionPropertiesInfo FunctionPropertiesInfo::getFunctionPropertiesInfo( + const Function &F, FunctionAnalysisManager &FAM) { FunctionPropertiesInfo FPI; + // The const casts are due to the getResult API - there's no mutation of F. + const auto &LI = FAM.getResult(const_cast(F)); + const auto &DT = + FAM.getResult(const_cast(F)); for (const auto &BB : F) - if (!pred_empty(&BB) || BB.isEntryBlock()) - FPI.reIncludeBB(BB, LI); + if (DT.isReachableFromEntry(&BB)) + FPI.reIncludeBB(BB); FPI.updateAggregateStats(F, LI); return FPI; } @@ -102,8 +114,7 @@ FunctionPropertiesInfo FunctionPropertiesAnalysis::run(Function &F, FunctionAnalysisManager &FAM) { - return FunctionPropertiesInfo::getFunctionPropertiesInfo( - F, FAM.getResult(F)); + return FunctionPropertiesInfo::getFunctionPropertiesInfo(F, FAM); } PreservedAnalyses @@ -153,29 +164,50 @@ FPI.updateForBB(*BB, -1); } -void FunctionPropertiesUpdater::finish(const LoopInfo &LI) const { - DenseSet ReIncluded; - std::deque Worklist; +void FunctionPropertiesUpdater::finish(FunctionAnalysisManager &FAM) const { + SetVector Worklist; if (&CallSiteBB != &*Caller.begin()) { - FPI.reIncludeBB(*Caller.begin(), LI); - ReIncluded.insert(&*Caller.begin()); + FPI.reIncludeBB(*Caller.begin()); + Worklist.insert(&*Caller.begin()); } // Update feature values from the BBs that were copied from the callee, or // might have been modified because of inlining. The latter have been // subtracted in the FunctionPropertiesUpdater ctor. - Worklist.push_back(&CallSiteBB); - while (!Worklist.empty()) { - const auto *BB = Worklist.front(); - Worklist.pop_front(); - if (!ReIncluded.insert(BB).second) - continue; - FPI.reIncludeBB(*BB, LI); - if (!Successors.contains(BB)) - for (const auto *Succ : successors(BB)) - Worklist.push_back(Succ); + // There could be successors that were reached before but now are only + // reachable from elsewhere in the CFG. + // Suppose the following diamond CFG (lines are arrows pointing down): + // A + // / \ + // B C + // \ / + // D + // There's a call site in C that is inlined. Upon doing that, it turns out + // it expands to + // call void @llvm.trap() + // unreachable + // D isn't reachable from C anymore, but we did discount it when we set up + // FunctionPropertiesUpdater, so we need to re-include it here. + + const auto &DT = + FAM.getResult(const_cast(Caller)); + for (const auto *Succ : Successors) + if (DT.isReachableFromEntry(Succ) && Worklist.insert(Succ)) + FPI.reIncludeBB(*Succ); + + auto I = Worklist.size(); + bool CSInsertion = Worklist.insert(&CallSiteBB); + (void)CSInsertion; + assert(CSInsertion); + for (; I < Worklist.size(); ++I) { + const auto *BB = Worklist[I]; + FPI.reIncludeBB(*BB); + for (const auto *Succ : successors(BB)) + Worklist.insert(Succ); } + + const auto &LI = FAM.getResult(const_cast(Caller)); FPI.updateAggregateStats(Caller, LI); - assert(FPI == FunctionPropertiesInfo::getFunctionPropertiesInfo(Caller, LI)); + assert(FPI == FunctionPropertiesInfo::getFunctionPropertiesInfo(Caller, FAM)); } diff --git a/llvm/lib/Analysis/MLInlineAdvisor.cpp b/llvm/lib/Analysis/MLInlineAdvisor.cpp --- a/llvm/lib/Analysis/MLInlineAdvisor.cpp +++ b/llvm/lib/Analysis/MLInlineAdvisor.cpp @@ -23,6 +23,7 @@ #include "llvm/Analysis/MLModelRunner.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/PassManager.h" #include "llvm/Support/CommandLine.h" @@ -218,7 +219,7 @@ PreservedAnalyses PA = PreservedAnalyses::none(); FAM.invalidate(*Caller, PA); } - Advice.updateCachedCallerFPI(FAM.getResult(*Caller)); + Advice.updateCachedCallerFPI(FAM); int64_t IRSizeAfter = getIRSize(*Caller) + (CalleeWasDeleted ? 0 : Advice.CalleeIRSize); CurrentIRSize += IRSizeAfter - (Advice.CallerIRSize + Advice.CalleeIRSize); @@ -414,8 +415,8 @@ OR << NV("ShouldInline", isInliningRecommended()); } -void MLInlineAdvice::updateCachedCallerFPI(const LoopInfo &LI) const { - FPU->finish(LI); +void MLInlineAdvice::updateCachedCallerFPI(FunctionAnalysisManager &FAM) const { + FPU->finish(FAM); } void MLInlineAdvice::recordInliningImpl() { diff --git a/llvm/unittests/Analysis/FunctionPropertiesAnalysisTest.cpp b/llvm/unittests/Analysis/FunctionPropertiesAnalysisTest.cpp --- a/llvm/unittests/Analysis/FunctionPropertiesAnalysisTest.cpp +++ b/llvm/unittests/Analysis/FunctionPropertiesAnalysisTest.cpp @@ -17,6 +17,7 @@ #include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" #include "llvm/Passes/PassBuilder.h" +#include "llvm/Passes/StandardInstrumentations.h" #include "llvm/Support/SourceMgr.h" #include "llvm/Transforms/Utils/Cloning.h" #include "gtest/gtest.h" @@ -26,14 +27,25 @@ namespace { class FunctionPropertiesAnalysisTest : public testing::Test { +public: + FunctionPropertiesAnalysisTest() { + FAM.registerPass([&] { return DominatorTreeAnalysis(); }); + FAM.registerPass([&] { return LoopAnalysis(); }); + FAM.registerPass([&] { return PassInstrumentationAnalysis(); }); + } + protected: std::unique_ptr DT; std::unique_ptr LI; + FunctionAnalysisManager FAM; FunctionPropertiesInfo buildFPI(Function &F) { - DT.reset(new DominatorTree(F)); - LI.reset(new LoopInfo(*DT)); - return FunctionPropertiesInfo::getFunctionPropertiesInfo(F, *LI); + return FunctionPropertiesInfo::getFunctionPropertiesInfo(F, FAM); + } + + void invalidate(Function &F) { + PreservedAnalyses PA = PreservedAnalyses::none(); + FAM.invalidate(F, PA); } std::unique_ptr makeLLVMModule(LLVMContext &C, const char *IR) { @@ -145,7 +157,8 @@ InlineFunctionInfo IFI; auto IR = llvm::InlineFunction(*CB, IFI); EXPECT_TRUE(IR.isSuccess()); - FPU.finish(*LI); + invalidate(*F1); + FPU.finish(FAM); EXPECT_EQ(FPI, ExpectedFinal); } @@ -198,7 +211,8 @@ InlineFunctionInfo IFI; auto IR = llvm::InlineFunction(*CB, IFI); EXPECT_TRUE(IR.isSuccess()); - FPU.finish(*LI); + invalidate(*F1); + FPU.finish(FAM); EXPECT_EQ(FPI, ExpectedFinal); } @@ -264,9 +278,8 @@ auto IR = llvm::InlineFunction(*CB, IFI); EXPECT_TRUE(IR.isSuccess()); - DominatorTree DTNew(*F1); - LoopInfo LINew(DTNew); - FPU.finish(LINew); + invalidate(*F1); + FPU.finish(FAM); EXPECT_EQ(FPI, ExpectedFinal); } @@ -310,9 +323,8 @@ InlineFunctionInfo IFI; auto IR = llvm::InlineFunction(*CB, IFI); EXPECT_TRUE(IR.isSuccess()); - DominatorTree DTNew(*F1); - LoopInfo LINew(DTNew); - FPU.finish(LINew); + invalidate(*F1); + FPU.finish(FAM); EXPECT_EQ(static_cast(FPI.BasicBlockCount), F1->getBasicBlockList().size()); EXPECT_EQ(static_cast(FPI.TotalInstructionCount), @@ -365,14 +377,13 @@ InlineFunctionInfo IFI; auto IR = llvm::InlineFunction(*CB, IFI); EXPECT_TRUE(IR.isSuccess()); - DominatorTree DTNew(*F1); - LoopInfo LINew(DTNew); - FPU.finish(LINew); + invalidate(*F1); + FPU.finish(FAM); EXPECT_EQ(static_cast(FPI.BasicBlockCount), F1->getBasicBlockList().size() - 1); EXPECT_EQ(static_cast(FPI.TotalInstructionCount), F1->getInstructionCount() - 2); - EXPECT_EQ(FPI, FunctionPropertiesInfo::getFunctionPropertiesInfo(*F1, LINew)); + EXPECT_EQ(FPI, FunctionPropertiesInfo::getFunctionPropertiesInfo(*F1, FAM)); } TEST_F(FunctionPropertiesAnalysisTest, Rethrow) { @@ -421,14 +432,13 @@ InlineFunctionInfo IFI; auto IR = llvm::InlineFunction(*CB, IFI); EXPECT_TRUE(IR.isSuccess()); - DominatorTree DTNew(*F1); - LoopInfo LINew(DTNew); - FPU.finish(LINew); + invalidate(*F1); + FPU.finish(FAM); EXPECT_EQ(static_cast(FPI.BasicBlockCount), F1->getBasicBlockList().size() - 1); EXPECT_EQ(static_cast(FPI.TotalInstructionCount), F1->getInstructionCount() - 2); - EXPECT_EQ(FPI, FunctionPropertiesInfo::getFunctionPropertiesInfo(*F1, LINew)); + EXPECT_EQ(FPI, FunctionPropertiesInfo::getFunctionPropertiesInfo(*F1, FAM)); } TEST_F(FunctionPropertiesAnalysisTest, LPadChanges) { @@ -475,14 +485,13 @@ InlineFunctionInfo IFI; auto IR = llvm::InlineFunction(*CB, IFI); EXPECT_TRUE(IR.isSuccess()); - DominatorTree DTNew(*F1); - LoopInfo LINew(DTNew); - FPU.finish(LINew); + invalidate(*F1); + FPU.finish(FAM); EXPECT_EQ(static_cast(FPI.BasicBlockCount), F1->getBasicBlockList().size() - 1); EXPECT_EQ(static_cast(FPI.TotalInstructionCount), F1->getInstructionCount() - 2); - EXPECT_EQ(FPI, FunctionPropertiesInfo::getFunctionPropertiesInfo(*F1, LINew)); + EXPECT_EQ(FPI, FunctionPropertiesInfo::getFunctionPropertiesInfo(*F1, FAM)); } TEST_F(FunctionPropertiesAnalysisTest, LPadChangesConditional) { @@ -533,14 +542,13 @@ InlineFunctionInfo IFI; auto IR = llvm::InlineFunction(*CB, IFI); EXPECT_TRUE(IR.isSuccess()); - DominatorTree DTNew(*F1); - LoopInfo LINew(DTNew); - FPU.finish(LINew); + invalidate(*F1); + FPU.finish(FAM); EXPECT_EQ(static_cast(FPI.BasicBlockCount), F1->getBasicBlockList().size() - 1); EXPECT_EQ(static_cast(FPI.TotalInstructionCount), F1->getInstructionCount() - 2); - EXPECT_EQ(FPI, FunctionPropertiesInfo::getFunctionPropertiesInfo(*F1, LINew)); + EXPECT_EQ(FPI, FunctionPropertiesInfo::getFunctionPropertiesInfo(*F1, FAM)); } TEST_F(FunctionPropertiesAnalysisTest, InlineSameLoopBB) { @@ -606,7 +614,69 @@ InlineFunctionInfo IFI; auto IR = llvm::InlineFunction(*CB, IFI); EXPECT_TRUE(IR.isSuccess()); - FPU.finish(*LI); + invalidate(*F1); + FPU.finish(FAM); + EXPECT_EQ(FPI, ExpectedFinal); +} + +TEST_F(FunctionPropertiesAnalysisTest, Unreachable) { + LLVMContext C; + std::unique_ptr M = makeLLVMModule(C, + R"IR( +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-pc-linux-gnu" + +define i64 @f1(i32 noundef %value) { +entry: + br i1 true, label %cond.true, label %cond.false + +cond.true: ; preds = %entry + %conv2 = sext i32 %value to i64 + br label %cond.end + +cond.false: ; preds = %entry + %call3 = call noundef i64 @f2() + br label %cond.end + +cond.end: ; preds = %cond.false, %cond.true + %cond = phi i64 [ %conv2, %cond.true ], [ %call3, %cond.false ] + ret i64 %cond +} + +define i64 @f2() { +entry: + tail call void @llvm.trap() + unreachable +} + +declare void @llvm.trap() +)IR"); + + Function *F1 = M->getFunction("f1"); + CallBase *CB = findCall(*F1); + EXPECT_NE(CB, nullptr); + + FunctionPropertiesInfo ExpectedInitial; + ExpectedInitial.BasicBlockCount = 4; + ExpectedInitial.TotalInstructionCount = 7; + ExpectedInitial.BlocksReachedFromConditionalInstruction = 2; + ExpectedInitial.Uses = 1; + ExpectedInitial.DirectCallsToDefinedFunctions = 1; + + FunctionPropertiesInfo ExpectedFinal = ExpectedInitial; + ExpectedFinal.BasicBlockCount = 4; + ExpectedFinal.DirectCallsToDefinedFunctions = 0; + ExpectedFinal.TotalInstructionCount = 7; + + auto FPI = buildFPI(*F1); + EXPECT_EQ(FPI, ExpectedInitial); + + FunctionPropertiesUpdater FPU(FPI, *CB); + InlineFunctionInfo IFI; + auto IR = llvm::InlineFunction(*CB, IFI); + EXPECT_TRUE(IR.isSuccess()); + invalidate(*F1); + FPU.finish(FAM); EXPECT_EQ(FPI, ExpectedFinal); }