llvm/unittests/CodeGen/MLRegAllocDevelopmentFeatures.cpp

   1 //===- MLRegAllocDevelopmentFeatures.cpp - test dev MLRegAlloc features ---===//
   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 #include "../../lib/CodeGen/MLRegAllocEvictAdvisor.h"
  10 #include "llvm/Analysis/NoInferenceModelRunner.h"
  11 #include "llvm/CodeGen/MachineBasicBlock.h"
  12 #include "llvm/CodeGen/MachineFunction.h"
  13 #include "llvm/CodeGen/MachineModuleInfo.h"
  14 #include "llvm/CodeGen/SlotIndexes.h"
  15 #include "llvm/CodeGen/TargetFrameLowering.h"
  16 #include "llvm/CodeGen/TargetInstrInfo.h"
  17 #include "llvm/CodeGen/TargetLowering.h"
  18 #include "llvm/IR/LLVMContext.h"
  19 #include "llvm/MC/TargetRegistry.h"
  20 #include "llvm/Support/Allocator.h"
  21 #include "llvm/Support/CodeGen.h"
  22 #include "llvm/Support/TargetSelect.h"
  23 #include "llvm/Target/TargetMachine.h"
  24 #include "llvm/Target/TargetOptions.h"
  25 #include "llvm/TargetParser/Triple.h"
  26 #include "gmock/gmock.h"
  27 #include "gtest/gtest.h"
  28
  29 #include <string>
  30 #include <vector>
  31
  32 using testing::ContainerEq;
  33 using testing::Test;
  34
  35 namespace {
  36
  37 #include "MFCommon.inc"
  38
  39 struct LRPosInfoIndexes {
  40   size_t StartIndex;
  41   size_t EndIndex;
  42   size_t PhysReg;
  43 };
  44
  45 class RegAllocDevelopmentFeaturesTest : public ::Test {
  46 protected:
  47   SmallVector<LRStartEndInfo>
  48   setupOverlapProblem(const SmallVectorImpl<LRPosInfoIndexes> &Segments,
  49                       ilist<IndexListEntry> &IndexList) {
  50     SmallVector<LRStartEndInfo> PositionsToReturn;
  51     PositionsToReturn.reserve(Segments.size());
  52     for (auto CurrentPosIndexInfo : Segments) {
  53       LRStartEndInfo CurrentPosInfo = {};
  54       CurrentPosInfo.Pos = CurrentPosIndexInfo.PhysReg;
  55       PositionsToReturn.push_back(CurrentPosInfo);
  56     }
  57     size_t CurrentSegmentIndex = 0;
  58     size_t CurrentIndex = 0;
  59     while (CurrentSegmentIndex < Segments.size()) {
  60       auto *CurrentLEMem = static_cast<IndexListEntry *>(
  61           Allocator.Allocate(sizeof(IndexListEntry), alignof(IndexListEntry)));
  62       auto *CurrentListEntry =
  63           new (CurrentLEMem) IndexListEntry(nullptr, CurrentIndex);
  64       IndexList.push_back(CurrentListEntry);
  65       for (size_t CurrentPosInfoIndex = 0;
  66            CurrentPosInfoIndex < Segments.size(); ++CurrentPosInfoIndex) {
  67         if ((CurrentIndex / SlotIndex::InstrDist) ==
  68             Segments[CurrentPosInfoIndex].StartIndex) {
  69           PositionsToReturn[CurrentPosInfoIndex].Begin =
  70               SlotIndex(CurrentListEntry, 0);
  71         } else if ((CurrentIndex / SlotIndex::InstrDist) ==
  72                    Segments[CurrentPosInfoIndex].EndIndex) {
  73           PositionsToReturn[CurrentPosInfoIndex].End =
  74               SlotIndex(CurrentListEntry, 0);
  75           ++CurrentSegmentIndex;
  76         }
  77       }
  78       CurrentIndex += SlotIndex::InstrDist;
  79     }
  80     return PositionsToReturn;
  81   }
  82
  83   NoInferenceModelRunner setupModelRunner() {
  84     const std::vector<TensorSpec> Inputs{
  85         TensorSpec::createSpec<int64_t>("instructions", InstructionsShape),
  86         TensorSpec::createSpec<int64_t>("instructions_mapping",
  87                                         InstructionsMappingShape),
  88         TensorSpec::createSpec<float>("mbb_frequencies", MBBFrequencyShape),
  89         TensorSpec::createSpec<int64_t>("mbb_mapping", InstructionsShape)};
  90     LLVMContext Ctx;
  91     return NoInferenceModelRunner(Ctx, Inputs);
  92   }
  93
  94   std::vector<int64_t>
  95   getExpectedMappingMatrix(SmallVectorImpl<LRPosInfoIndexes> &OverlapSetup) {
  96     std::vector<int64_t> ExpectedMappingMatrix(
  97         NumberOfInterferences * ModelMaxSupportedInstructionCount, 0);
  98     for (auto NewSegment : OverlapSetup) {
  99       for (size_t CurrentIndex = NewSegment.StartIndex;
 100            CurrentIndex <= NewSegment.EndIndex; ++CurrentIndex) {
 101         ExpectedMappingMatrix[NewSegment.PhysReg *
 102                                   ModelMaxSupportedInstructionCount +
 103                               CurrentIndex] = 1;
 104       }
 105     }
 106     return ExpectedMappingMatrix;
 107   }
 108
 109   void runOverlapTest(SmallVectorImpl<LRPosInfoIndexes> &OverlapSetup) {
 110     ilist<IndexListEntry> IndexList;
 111     auto OverlapProblem = setupOverlapProblem(OverlapSetup, IndexList);
 112     NoInferenceModelRunner ModelRunner = setupModelRunner();
 113     size_t MaxIndex = 0;
 114     for (size_t CurrentOverlap = 0; CurrentOverlap < OverlapSetup.size();
 115          ++CurrentOverlap) {
 116       if (OverlapSetup[CurrentOverlap].EndIndex >
 117           OverlapSetup[MaxIndex].EndIndex) {
 118         MaxIndex = CurrentOverlap;
 119       }
 120     }
 121     SlotIndex LastIndex = OverlapProblem[MaxIndex].End;
 122     extractInstructionFeatures(
 123         OverlapProblem, &ModelRunner,
 124         [](SlotIndex InputSlot) -> int { return 0; },
 125         [](SlotIndex InputSlot) -> float { return 0.0f; },
 126         [](SlotIndex InputSlot) -> MachineBasicBlock * { return nullptr; }, 0,
 127         1, 2, 3, LastIndex);
 128     std::vector<int64_t> MappingMatrix(
 129         ModelRunner.getTensor<int64_t>(1),
 130         ModelRunner.getTensor<int64_t>(1) +
 131             NumberOfInterferences * ModelMaxSupportedInstructionCount);
 132     ASSERT_THAT(MappingMatrix,
 133                 ContainerEq(getExpectedMappingMatrix(OverlapSetup)));
 134     IndexList.clearAndLeakNodesUnsafely();
 135   }
 136
 137   BumpPtrAllocator Allocator;
 138 };
 139
 140 // meta tests to ensure that test setup works correctly
 141
 142 TEST_F(RegAllocDevelopmentFeaturesTest,
 143        MetaOverlapInstructionDistancesAreCorrect) {
 144   SmallVector<LRPosInfoIndexes, 2> OverlapSetup;
 145   OverlapSetup.push_back({0, 5, 0});
 146   OverlapSetup.push_back({5, 10, 0});
 147   ilist<IndexListEntry> IndexList;
 148   auto OverlapProblem = setupOverlapProblem(OverlapSetup, IndexList);
 149   ASSERT_EQ(OverlapProblem[0].End.distance(OverlapProblem[1].End),
 150             5 * SlotIndex::InstrDist);
 151   ASSERT_EQ(OverlapProblem[0].End.distance(OverlapProblem[1].Begin), 0);
 152 }
 153
 154 TEST_F(RegAllocDevelopmentFeaturesTest, MetaSlotIndicesAreValid) {
 155   SmallVector<LRPosInfoIndexes, 1> OverlapSetup;
 156   OverlapSetup.push_back({0, 10, 0});
 157   ilist<IndexListEntry> IndexList;
 158   auto OverlapProblem = setupOverlapProblem(OverlapSetup, IndexList);
 159   ASSERT_TRUE(OverlapProblem[0].Begin.isValid());
 160   ASSERT_TRUE(OverlapProblem[0].End.isValid());
 161 }
 162
 163 // Testing of feature extraction for per-instruction features
 164
 165 TEST_F(RegAllocDevelopmentFeaturesTest, InstructionOpcodesAreCorrect) {
 166   SmallVector<LRPosInfoIndexes, 1> OverlapSetup;
 167   OverlapSetup.push_back({0, ModelMaxSupportedInstructionCount - 1, 0});
 168   ilist<IndexListEntry> IndexList;
 169   auto OverlapProblem = setupOverlapProblem(OverlapSetup, IndexList);
 170   NoInferenceModelRunner ModelRunner = setupModelRunner();
 171   SlotIndex LastIndex = OverlapProblem[0].End;
 172   SlotIndex FirstIndex = OverlapProblem[0].Begin;
 173   extractInstructionFeatures(
 174       OverlapProblem, &ModelRunner,
 175       [FirstIndex](SlotIndex InputSlot) -> int {
 176         return FirstIndex.distance(InputSlot) / SlotIndex::InstrDist;
 177       },
 178       [](SlotIndex InputSlot) -> float { return 0.0f; },
 179       [](SlotIndex InputSlot) -> MachineBasicBlock * { return nullptr; }, 0, 1,
 180       2, 3, LastIndex);
 181   for (size_t CurrentInstructionIndex = 0;
 182        CurrentInstructionIndex < ModelMaxSupportedInstructionCount;
 183        ++CurrentInstructionIndex) {
 184     ASSERT_EQ(
 185         (size_t)ModelRunner.getTensor<int64_t>(0)[CurrentInstructionIndex],
 186         CurrentInstructionIndex);
 187   }
 188 }
 189
 190 TEST_F(RegAllocDevelopmentFeaturesTest, FullOverlap) {
 191   SmallVector<LRPosInfoIndexes, 2> OverlapSetup;
 192   OverlapSetup.push_back({0, ModelMaxSupportedInstructionCount - 1, 0});
 193   OverlapSetup.push_back({0, ModelMaxSupportedInstructionCount - 1, 1});
 194   runOverlapTest(OverlapSetup);
 195 }
 196
 197 TEST_F(RegAllocDevelopmentFeaturesTest, PartialOverlap) {
 198   SmallVector<LRPosInfoIndexes, 2> OverlapSetup;
 199   OverlapSetup.push_back({0, 20, 0});
 200   OverlapSetup.push_back({15, 30, 1});
 201   runOverlapTest(OverlapSetup);
 202 }
 203
 204 TEST_F(RegAllocDevelopmentFeaturesTest, PartialOverlapOpposite) {
 205   SmallVector<LRPosInfoIndexes, 2> OverlapSetup;
 206   OverlapSetup.push_back({15, 30, 1});
 207   OverlapSetup.push_back({0, 20, 0});
 208   runOverlapTest(OverlapSetup);
 209 }
 210
 211 TEST_F(RegAllocDevelopmentFeaturesTest, InternalOverlap) {
 212   SmallVector<LRPosInfoIndexes, 2> OverlapSetup;
 213   OverlapSetup.push_back({0, 30, 0});
 214   OverlapSetup.push_back({10, 20, 1});
 215   runOverlapTest(OverlapSetup);
 216 }
 217
 218 TEST_F(RegAllocDevelopmentFeaturesTest, TripleInternalOverlap) {
 219   SmallVector<LRPosInfoIndexes, 3> OverlapSetup;
 220   OverlapSetup.push_back({0, 30, 0});
 221   OverlapSetup.push_back({10, 25, 1});
 222   OverlapSetup.push_back({15, 20, 2});
 223   runOverlapTest(OverlapSetup);
 224 }
 225
 226 TEST_F(RegAllocDevelopmentFeaturesTest, InternalMultiOverlap) {
 227   SmallVector<LRPosInfoIndexes, 3> OverlapSetup;
 228   OverlapSetup.push_back({0, 45, 0});
 229   OverlapSetup.push_back({30, 40, 1});
 230   OverlapSetup.push_back({35, 60, 2});
 231   runOverlapTest(OverlapSetup);
 232 }
 233
 234 TEST_F(RegAllocDevelopmentFeaturesTest, SingleMBBTest) {
 235   NoInferenceModelRunner ModelRunner = setupModelRunner();
 236   SlotIndex CurrentIndex;
 237   // set index to 1 so we can ensure that the mapping actually get set
 238   std::map<MachineBasicBlock *, size_t> VisitedMBBs = {{nullptr, 1}};
 239   extractMBBFrequency(
 240       CurrentIndex, 0, VisitedMBBs,
 241       [](SlotIndex InputSlot) -> float { return 1.0f; }, nullptr, &ModelRunner,
 242       2, 3);
 243   ASSERT_FLOAT_EQ(ModelRunner.getTensor<float>(2)[1], 1.0f);
 244   ASSERT_EQ(ModelRunner.getTensor<int64_t>(3)[0], 1);
 245 }
 246
 247 TEST_F(RegAllocDevelopmentFeaturesTest, MBBFullTruncated) {
 248   SmallVector<LRPosInfoIndexes, 1> OverlapSetup;
 249   OverlapSetup.push_back({0, ModelMaxSupportedInstructionCount - 1, 0});
 250   ilist<IndexListEntry> IndexList;
 251   auto OverlapProblem = setupOverlapProblem(OverlapSetup, IndexList);
 252   NoInferenceModelRunner ModelRunner = setupModelRunner();
 253   SlotIndex LastIndex = OverlapProblem[0].End;
 254   SlotIndex FirstIndex = OverlapProblem[0].Begin;
 255
 256   LLVMContext Ctx;
 257   Module Mod("Module", Ctx);
 258   auto MF = createMachineFunction(Ctx, Mod);
 259   std::array<MachineBasicBlock *, ModelMaxSupportedInstructionCount>
 260       MBBsForTest;
 261   for (size_t I = 0; I < ModelMaxSupportedInstructionCount; ++I) {
 262     MBBsForTest[I] = MF->CreateMachineBasicBlock();
 263   }
 264
 265   extractInstructionFeatures(
 266       OverlapProblem, &ModelRunner,
 267       [](SlotIndex InputSlot) -> int { return 0; },
 268       [FirstIndex](SlotIndex InputSlot) -> float {
 269         return static_cast<float>(FirstIndex.distance(InputSlot) /
 270                                   SlotIndex::InstrDist);
 271       },
 272       [FirstIndex, MBBsForTest](SlotIndex InputSlot) -> MachineBasicBlock * {
 273         return MBBsForTest[FirstIndex.distance(InputSlot) /
 274                            SlotIndex::InstrDist];
 275       },
 276       0, 1, 2, 3, LastIndex);
 277   for (size_t MBBIndex = 0; MBBIndex < ModelMaxSupportedMBBCount; ++MBBIndex) {
 278     ASSERT_FLOAT_EQ(ModelRunner.getTensor<float>(2)[MBBIndex],
 279                     static_cast<float>(MBBIndex));
 280     ASSERT_EQ(ModelRunner.getTensor<int64_t>(3)[MBBIndex],
 281               static_cast<int64_t>(MBBIndex));
 282   }
 283   // the rest of the mapping values should be zero (truncated to 100 MBBs)
 284   for (size_t MBBIndex = ModelMaxSupportedMBBCount;
 285        MBBIndex < ModelMaxSupportedInstructionCount; ++MBBIndex) {
 286     ASSERT_EQ(ModelRunner.getTensor<int64_t>(3)[MBBIndex],
 287               static_cast<int64_t>(0));
 288   }
 289 }
 290
 291 } // end namespace