1 //===- LastRunTrackingAnalysis.h - Avoid running redundant pass -*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This is an analysis pass to track a set of passes that have been run, so that 10 // we can avoid running a pass again if there is no change since the last run of 11 // the pass. 12 // 13 // In this analysis we track a set of passes S for each function with the 14 // following transition rules: 15 // 1. If pass P makes changes, set S = {P}. 16 // 2. If pass P doesn't make changes, set S = S + {P}. 17 // 18 // Before running a pass P which satisfies P(P(x)) == P(x), we check if P is in 19 // S. If so, we skip this pass since we know that there will be no change. 20 // 21 // Notes: 22 // 1. Some transform passes have parameters that may vary in the optimization 23 // pipeline. We should check if parameters in current run is compatible with 24 // that in the last run. 25 // 2. This pass only tracks at the module/function level. Loop passes are not 26 // supported for now. 27 // 28 //===----------------------------------------------------------------------===// 29 30 #ifndef LLVM_ANALYSIS_LASTRUNTRACKINGANALYSIS_H 31 #define LLVM_ANALYSIS_LASTRUNTRACKINGANALYSIS_H 32 33 #include "llvm/ADT/DenseMap.h" 34 #include "llvm/IR/PassManager.h" 35 #include "llvm/Support/Compiler.h" 36 #include <functional> 37 38 namespace llvm { 39 40 /// This class is used to track the last run of a set of module/function passes. 41 /// Invalidation are conservatively handled by the pass manager if a pass 42 /// doesn't explicitly preserve the result. 43 /// If we want to skip a pass, we should define a unique ID \p PassID to 44 /// identify the pass, which is usually a pointer to a static member. If a pass 45 /// has parameters, they should be stored in a struct \p OptionT with a method 46 /// bool isCompatibleWith(const OptionT& LastOpt) const to check compatibility. 47 class LastRunTrackingInfo { 48 public: 49 using PassID = const void *; 50 using OptionPtr = const void *; 51 // CompatibilityCheckFn is a closure that stores the parameters of last run. 52 using CompatibilityCheckFn = std::function<bool(OptionPtr)>; 53 54 /// Check if we should skip a pass. 55 /// \param ID The unique ID of the pass. 56 /// \param Opt The parameters of the pass. If the pass has no parameters, use 57 /// shouldSkip(PassID ID) instead. 58 /// \return True if we should skip the pass. 59 /// \sa shouldSkip(PassID ID) 60 template <typename OptionT> shouldSkip(PassID ID,const OptionT & Opt)61 bool shouldSkip(PassID ID, const OptionT &Opt) const { 62 return shouldSkipImpl(ID, &Opt); 63 } shouldSkip(PassID ID)64 bool shouldSkip(PassID ID) const { return shouldSkipImpl(ID, nullptr); } 65 66 /// Update the tracking info. 67 /// \param ID The unique ID of the pass. 68 /// \param Changed Whether the pass makes changes. 69 /// \param Opt The parameters of the pass. It must have the same type as the 70 /// parameters of the last run. If the pass has no parameters, use 71 /// update(PassID ID, bool Changed) instead. 72 /// \sa update(PassID ID, bool Changed) 73 template <typename OptionT> update(PassID ID,bool Changed,const OptionT & Opt)74 void update(PassID ID, bool Changed, const OptionT &Opt) { 75 updateImpl(ID, Changed, [Opt](OptionPtr Ptr) { 76 return static_cast<const OptionT *>(Ptr)->isCompatibleWith(Opt); 77 }); 78 } update(PassID ID,bool Changed)79 void update(PassID ID, bool Changed) { 80 updateImpl(ID, Changed, CompatibilityCheckFn{}); 81 } 82 83 private: 84 LLVM_ABI bool shouldSkipImpl(PassID ID, OptionPtr Ptr) const; 85 LLVM_ABI void updateImpl(PassID ID, bool Changed, 86 CompatibilityCheckFn CheckFn); 87 88 DenseMap<PassID, CompatibilityCheckFn> TrackedPasses; 89 }; 90 91 /// A function/module analysis which provides an empty \c LastRunTrackingInfo. 92 class LastRunTrackingAnalysis final 93 : public AnalysisInfoMixin<LastRunTrackingAnalysis> { 94 friend AnalysisInfoMixin<LastRunTrackingAnalysis>; 95 LLVM_ABI static AnalysisKey Key; 96 97 public: 98 using Result = LastRunTrackingInfo; run(Function & F,FunctionAnalysisManager &)99 LastRunTrackingInfo run(Function &F, FunctionAnalysisManager &) { 100 return LastRunTrackingInfo(); 101 } run(Module & M,ModuleAnalysisManager &)102 LastRunTrackingInfo run(Module &M, ModuleAnalysisManager &) { 103 return LastRunTrackingInfo(); 104 } 105 }; 106 107 } // namespace llvm 108 109 #endif // LLVM_ANALYSIS_LASTRUNTRACKINGANALYSIS_H 110