[NFC][MLInliner] Presort instruction successions.

[dblaikie]

Looks good - thanks!

Few other bits of optional feedback, I don't mean to dredge up old code that I know we discussed somewhat in the past - but some thoughts in case any resonate/make more sense now than in the past, and some minor bits of stuff that can be cleaned up without pre-commit review.

llvm/lib/Analysis/InlineSizeEstimatorAnalysis.cpp

90–92

Could replace this with llvm::is_sorted(FunctionFeatures::ImportantInstructionSuccessions); while you're here

105

This could be a static variable here ^ rather than being a member variable - would save all the IRToNativeSizeLearning::FunctionFeatures:: qualification - doesn't look like that qualification adds a lot of value to the variable name? (I tend to think "longer variable names for wider scopes" - given the effective scope of this variable is just two functions here - maybe doesn't need such a long name (at least the qualifiers, "ImportantInstructionSuccessions" is probably sufficiently unambiguous?)

141–143

Throughout the file there are a fair few non-const references that could be const, which would be preferred. (generally top level const on local values is less interesting - but usually if a reference can be const, it should be made so)

176–177

'int' would be appropriate here - 'auto' isn't helping readability, it's longer than 'int'

180–182

Could simplify this a bit with llvm::find(FunctionFeatures::ImportantInstructionSuccessions, std::make_pair(a, b)) - separate commit, doesn't need precommit review, etc.

191–193

range-based-for loop, perhaps?

280–286

Hmm - I know when went around a few times on the API a while ago - and perhaps there's good reasons I've since forgotten (sorry :/) but this sort of if/else is something I was hoping to avoid. (by, eg: Having a virtual interface, a TF implementation and a non-TF stub implementation (or fallbacks in the calling code that tested for the absence of an implementation - "if null do the stub/default thing"), and then one function with the #if/else that - and then a single always-compiled function that has a conditional #include and then a "get estimator" function that returns null/default, or the TF implementation if available) - having lots of surface area like this means more chance of failures when someone's building only in one mode or the other. Specifically having different implementations of the same function I think is something best avoided where possible (LLVM has some in the platform APIs, for instance - open a file for Windows, open a file for Linux, etc - but in this case I hope it could be simpler by having only one very small amount of preprocessor conditionalized implementation)

[mtrofin]

llvm/lib/Analysis/InlineSizeEstimatorAnalysis.cpp

280–286

We did that for the big things - the inline advisor. Here, there's not much of a surface area, and seemed more pragmatic to do it this way.

[mtrofin]

feedback

[mtrofin]

llvm/lib/Analysis/InlineSizeEstimatorAnalysis.cpp

141–143

yup - thanks, fixed.

llvm/lib/Analysis/InlineSizeEstimatorAnalysis.cpp

enum class NamedFeatureIndex : size_t {
     MaxLoopDepth,
     MaxDomTreeLevel,
 
     NumNamedFeatures
   };
   static const size_t NumNamedFeatures =
       static_cast<size_t>(NamedFeatureIndex::NumNamedFeatures);
   struct FunctionFeatures {
-    static std::vector<std::pair<size_t, size_t>>
+    static const std::array<std::pair<size_t, size_t>, 137>
         ImportantInstructionSuccessions;
     static const size_t FeatureCount;
 
     std::array<int32_t, NumNamedFeatures> NamedFeatures = {0};
     std::vector<int32_t> InstructionHistogram;
     std::vector<int32_t> InstructionPairHistogram;
 
     void fillTensor(int32_t *Ptr) const;
     int32_t &operator[](NamedFeatureIndex Pos) {
       return NamedFeatures[static_cast<size_t>(Pos)];
     }
   };
   IRToNativeSizeLearning() = default;
 
   static FunctionFeatures getFunctionFeatures(Function &F,
                                               FunctionAnalysisManager &FAM);
 
 private:
-  /// Sort once the feature tuples.
-  struct SortFeatureTuples {
-    bool IsSorted = false;
-    SortFeatureTuples() {
-      std::sort(FunctionFeatures::ImportantInstructionSuccessions.begin(),
-                FunctionFeatures::ImportantInstructionSuccessions.end());
-      IsSorted = true;
-    }
-  };
+  static bool ensureSortedTuples() {
+    return std::is_sorted(
+        FunctionFeatures::ImportantInstructionSuccessions.begin(),
 
-  static llvm::ManagedStatic<SortFeatureTuples> TupleSorter;
-
-  static bool ensureSortedTuples() { return TupleSorter->IsSorted; }
-};
-llvm::ManagedStatic<IRToNativeSizeLearning::SortFeatureTuples>
-    IRToNativeSizeLearning::TupleSorter;
-
 // This is a point in time - we determined including these pairs of
 // consecutive instructions (in the IR layout available at inline time) as
 // features improves the model performance. We want to move away from manual
 // feature selection.
-// The vector is given in opcode pairs rather than labels because 1) labels
-// weren't readily available, and 2) the successions were hand - extracted
-std::vector<std::pair<size_t, size_t>>
-    IRToNativeSizeLearning::FunctionFeatures::ImportantInstructionSuccessions =
-        {{1, 34},  {15, 27}, {53, 53}, {53, 34}, {1, 11},  {32, 2},  {2, 48},
-         {28, 48}, {1, 45},  {49, 32}, {57, 56}, {55, 53}, {1, 28},  {57, 34},
-         {1, 1},   {32, 28}, {32, 15}, {49, 28}, {53, 1},  {2, 53},  {48, 34},
-         {28, 53}, {2, 32},  {1, 40},  {32, 48}, {29, 56}, {56, 32}, {55, 56},
-         {48, 56}, {1, 31},  {33, 34}, {2, 28},  {1, 12},  {55, 1},  {31, 31},
-         {65, 1},  {33, 56}, {32, 32}, {13, 13}, {1, 26},  {13, 26}, {2, 1},
-         {1, 33},  {47, 49}, {64, 1},  {2, 38},  {34, 53}, {48, 2},  {55, 34},
-         {34, 32}, {1, 5},   {56, 13}, {2, 2},   {2, 49},  {33, 2},  {49, 39},
-         {56, 49}, {33, 49}, {32, 39}, {39, 57}, {29, 33}, {31, 34}, {32, 29},
-         {47, 15}, {13, 34}, {2, 33},  {32, 49}, {49, 34}, {56, 33}, {1, 30},
-         {33, 33}, {31, 33}, {2, 29},  {56, 7},  {32, 13}, {2, 55},  {56, 56},
-         {2, 34},  {1, 42},  {34, 49}, {1, 20},  {32, 33}, {1, 25},  {53, 28},
-         {1, 14},  {31, 49}, {28, 2},  {2, 13},  {2, 56},  {1, 32},  {56, 53},
-         {65, 65}, {33, 53}, {64, 64}, {13, 2},  {34, 33}, {1, 4},   {49, 2},
-         {1, 9},   {56, 1},  {33, 1},  {53, 57}, {32, 53}, {13, 56}, {32, 56},
-         {55, 55}, {1, 18},  {49, 56}, {34, 34}, {1, 7},   {56, 64}, {32, 1},
-         {13, 33}, {55, 28}, {49, 33}, {57, 57}, {56, 34}, {34, 56}, {33, 32},
-         {32, 40}, {1, 29},  {53, 2},  {34, 1},  {32, 34}, {49, 49}, {1, 24},
-         {40, 34}, {1, 13},  {38, 34}, {29, 2},  {34, 2},  {1, 39},  {1, 22},
-         {1, 27},  {49, 1},  {1, 8},   {56, 2}};
+// The array is given in opcode pairs rather than labels because 1) labels
+// weren't readily available, and 2) the successions were hand - extracted.
+//
+// This array must be sorted.
+const std::array<std::pair<size_t, size_t>, 137>
+    IRToNativeSizeLearning::FunctionFeatures::ImportantInstructionSuccessions{
+        {{1, 1},   {1, 4},   {1, 5},   {1, 7},   {1, 8},   {1, 9},   {1, 11},
+         {1, 12},  {1, 13},  {1, 14},  {1, 18},  {1, 20},  {1, 22},  {1, 24},
+         {1, 25},  {1, 26},  {1, 27},  {1, 28},  {1, 29},  {1, 30},  {1, 31},
+         {1, 32},  {1, 33},  {1, 34},  {1, 39},  {1, 40},  {1, 42},  {1, 45},
+         {2, 1},   {2, 2},   {2, 13},  {2, 28},  {2, 29},  {2, 32},  {2, 33},
+         {2, 34},  {2, 38},  {2, 48},  {2, 49},  {2, 53},  {2, 55},  {2, 56},
+         {13, 2},  {13, 13}, {13, 26}, {13, 33}, {13, 34}, {13, 56}, {15, 27},
+         {28, 2},  {28, 48}, {28, 53}, {29, 2},  {29, 33}, {29, 56}, {31, 31},
+         {31, 33}, {31, 34}, {31, 49}, {32, 1},  {32, 2},  {32, 13}, {32, 15},
+         {32, 28}, {32, 29}, {32, 32}, {32, 33}, {32, 34}, {32, 39}, {32, 40},
+         {32, 48}, {32, 49}, {32, 53}, {32, 56}, {33, 1},  {33, 2},  {33, 32},
+         {33, 33}, {33, 34}, {33, 49}, {33, 53}, {33, 56}, {34, 1},  {34, 2},
+         {34, 32}, {34, 33}, {34, 34}, {34, 49}, {34, 53}, {34, 56}, {38, 34},
+         {39, 57}, {40, 34}, {47, 15}, {47, 49}, {48, 2},  {48, 34}, {48, 56},
+         {49, 1},  {49, 2},  {49, 28}, {49, 32}, {49, 33}, {49, 34}, {49, 39},
+         {49, 49}, {49, 56}, {53, 1},  {53, 2},  {53, 28}, {53, 34}, {53, 53},
+         {53, 57}, {55, 1},  {55, 28}, {55, 34}, {55, 53}, {55, 55}, {55, 56},
+         {56, 1},  {56, 2},  {56, 7},  {56, 13}, {56, 32}, {56, 33}, {56, 34},
+         {56, 49}, {56, 53}, {56, 56}, {56, 64}, {57, 34}, {57, 56}, {57, 57},
+         {64, 1},  {64, 64}, {65, 1},  {65, 65}}};
 
 // We have: 9 calculated features (the features here); 1 feature for each
 // instruction opcode; and 1 feature for each manually-identified sequence.
 // For the latter 2, we build a histogram: we count the number of
 // occurrences of each instruction opcode or succession of instructions,
 // respectively.
 // Note that instruction opcodes start from 1. For convenience, we also have an
 // always 0 feature for the '0' opcode, hence the extra 1.
 const size_t IRToNativeSizeLearning::FunctionFeatures::FeatureCount =
     IRToNativeSizeLearning::FunctionFeatures::ImportantInstructionSuccessions
         .size() +
     getMaxInstructionID() + 1 + IRToNativeSizeLearning::NumNamedFeatures;
 
 size_t getSize(Function &F, TargetTransformInfo &TTI) {
   size_t Ret = 0;
   for (auto &BB : F)
     for (auto &I : BB)
       Ret += TTI.getInstructionCost(
           &I, TargetTransformInfo::TargetCostKind::TCK_CodeSize);
   return Ret;
 }
 
 size_t getSize(Function &F, FunctionAnalysisManager &FAM) {
   auto &TTI = FAM.getResult<TargetIRAnalysis>(F);
   return getSize(F, TTI);
 }
 
 unsigned getMaxDominatorTreeDepth(const Function &F,
                                   const DominatorTree &Tree) {
   unsigned Ret = 0;
   for (auto &BB : F)
     if (auto *TN = Tree.getNode(&BB))
       Ret = std::max(Ret, TN->getLevel());
   return Ret;
 }
 } // namespace
 
 IRToNativeSizeLearning::FunctionFeatures
 IRToNativeSizeLearning::getFunctionFeatures(Function &F,
                                             FunctionAnalysisManager &FAM) {
-  ensureSortedTuples();
+  assert(ensureSortedTuples() && "expected function features are sorted");
 
   auto &DomTree = FAM.getResult<DominatorTreeAnalysis>(F);
   FunctionFeatures FF;
   size_t InstrCount = getMaxInstructionID() + 1;
   FF.InstructionHistogram.resize(InstrCount);
 
   FF.InstructionPairHistogram.resize(
       FunctionFeatures::ImportantInstructionSuccessions.size());
 
   auto StartID = 0;
   auto LastID = StartID;
   auto getPairIndex = [](size_t a, size_t b) {
     auto I =
         std::find(FunctionFeatures::ImportantInstructionSuccessions.begin(),
                   FunctionFeatures::ImportantInstructionSuccessions.end(),
                   std::make_pair(a, b));
     if (I == FunctionFeatures::ImportantInstructionSuccessions.end())
       return -1;
     return static_cast<int>(std::distance(
         FunctionFeatures::ImportantInstructionSuccessions.begin(), I));
   };
 
   // We don't want debug calls, because they'd just add noise.
   for (auto &BB : F) {
     for (auto I = BB.instructionsWithoutDebug().begin(),
               E = BB.instructionsWithoutDebug().end();
          I != E; ++I) {
       auto ID = I->getOpcode();
 
       ++FF.InstructionHistogram[ID];
       int PairIndex = getPairIndex(LastID, ID);
       if (PairIndex >= 0)
         ++FF.InstructionPairHistogram[PairIndex];
       LastID = ID;
       if (isa<CallBase>(*I))

 InlineSizeEstimatorAnalysis::InlineSizeEstimatorAnalysis(
     InlineSizeEstimatorAnalysis &&Other)
     : Evaluator(std::move(Other.Evaluator)) {}
 
 #else
 namespace llvm {
 class TFModelEvaluator {};
 } // namespace llvm
 InlineSizeEstimatorAnalysis::InlineSizeEstimatorAnalysis() {}
 InlineSizeEstimatorAnalysis ::InlineSizeEstimatorAnalysis(
     InlineSizeEstimatorAnalysis &&) {}
 InlineSizeEstimatorAnalysis::~InlineSizeEstimatorAnalysis() {}
 InlineSizeEstimatorAnalysis::Result
 InlineSizeEstimatorAnalysis::run(const Function &F,
                                  FunctionAnalysisManager &FAM) {
   return None;
 }
 bool InlineSizeEstimatorAnalysis::isEvaluatorRequested() { return false; }
 #endif
 
 PreservedAnalyses
 InlineSizeEstimatorAnalysisPrinterPass::run(Function &F,
                                             FunctionAnalysisManager &AM) {
   OS << "[InlineSizeEstimatorAnalysis] size estimate for " << F.getName()
      << ": " << AM.getResult<InlineSizeEstimatorAnalysis>(F) << "\n";
   return PreservedAnalyses::all();
 }