llvm-reduce: Introduce new scoring mechanism for MIR reductions

[arsenm]

Summary

Many MIR reductions benefit from or require increasing the instruction
count. For example, unlike in the IR, you may need to insert a new
instruction to represent an undef. The current instruction reduction
pass works around this by sticking implicit defs on whatever
instruction happens to be first in the entry block block.

Other strategies I've applied manually include breaking instructions
with multiple defs into separate instructions, or breaking large register defs
into multiple subregister defs.

Make up a simple scoring system based on what I generally try to get
rid of first when manually reducing. Counts implicit defs as free
since reduction passes will be introducing them, although they
probably should count for something. It also might make more sense to
have a comparison the two functions, rather than having to compute a
contextless number. This isn't particularly well tested since overall
the MIR support isn't in a place where it is useful on the kinds of testcases
I want to throw at it

[arsenm]

Fix missing squash

[markus]

Right, so with MIR reductions we totally forgot about this an relied on the IR serialization size which is obviously wrong. This looks like an improvement to me. Of course the details of the metric can always be discussed but this should be better than nothing. Especially if we start inserting IMPLICIT_DEF instructions during reduction.

[arsenm]

35264e7179693da9b1cc55c38370e9e894b1c456

llvm/tools/llvm-reduce/DeltaManager.cpp

 #define DELTA_PASS(NAME, FUNC) OS << "  " << NAME << "\n";
   OS << " IR:\n";
   DELTA_PASSES
   OS << " MIR:\n";
   DELTA_PASSES_MIR
 #undef DELTA_PASS
 }
 
-// FIXME: We might want to use a different metric than "number of
-// bytes in serialized IR" to detect non-progress of the main delta
-// loop
-static int getIRSize(TestRunner &Tester) {
-  std::string Str;
-  raw_string_ostream SS(Str);
-  Tester.getProgram().print(SS, /*AnnotationWriter=*/nullptr);
-  return Str.length();
-}
-
 void llvm::runDeltaPasses(TestRunner &Tester, int MaxPassIterations) {
-  int OldSize = getIRSize(Tester);
+  uint64_t OldComplexity = Tester.getProgram().getComplexityScore();
   for (int Iter = 0; Iter < MaxPassIterations; ++Iter) {
     if (DeltaPasses.empty()) {
       runAllDeltaPasses(Tester);
     } else {
       StringRef Passes = DeltaPasses;
       while (!Passes.empty()) {
         auto Split = Passes.split(",");
         runDeltaPassName(Tester, Split.first);
         Passes = Split.second;
       }
     }
-    int NewSize = getIRSize(Tester);
-    if (NewSize >= OldSize)
+    uint64_t NewComplexity = Tester.getProgram().getComplexityScore();
+    if (NewComplexity >= OldComplexity)
       break;
-    OldSize = NewSize;
+    OldComplexity = NewComplexity;
   }
 }

llvm/tools/llvm-reduce/ReducerWorkItem.h

public:
   std::unique_ptr<MachineModuleInfo> MMI;
 
   bool isMIR() const { return MMI != nullptr; }
 
   const Module &getModule() const { return *M; }
 
   void print(raw_ostream &ROS, void *p = nullptr) const;
   operator Module &() const { return *M; }
+
+  /// Return a number to indicate whether there was any reduction progress.
+  uint64_t getComplexityScore() const {
+    return isMIR() ? computeMIRComplexityScore() : getIRSize();
+  }
+
+private:
+  uint64_t computeMIRComplexityScore() const;
+  uint64_t getIRSize() const;
 };
 
 std::unique_ptr<ReducerWorkItem>
 parseReducerWorkItem(const char *ToolName, StringRef Filename,
                      LLVMContext &Ctxt, std::unique_ptr<TargetMachine> &TM,
                      bool IsMIR);
 
 std::unique_ptr<ReducerWorkItem>
 cloneReducerWorkItem(const ReducerWorkItem &MMM, const TargetMachine *TM);
 
 bool verifyReducerWorkItem(const ReducerWorkItem &MMM, raw_fd_ostream *OS);
 
 #endif

llvm/tools/llvm-reduce/ReducerWorkItem.cpp

for (Function &F : *M) {
       if (auto *MF = MMI->getMachineFunction(F))
         printMIR(ROS, *MF);
     }
   } else {
     M->print(ROS, /*AssemblyAnnotationWriter=*/nullptr,
              /*ShouldPreserveUseListOrder=*/true);
   }
 }
+
+// FIXME: We might want to use a different metric than "number of
+// bytes in serialized IR" to detect non-progress of the main delta
+// loop
+uint64_t ReducerWorkItem::getIRSize() const {
+  std::string Str;
+  raw_string_ostream SS(Str);
+  print(SS, /*AnnotationWriter=*/nullptr);
+  return Str.length();
+}
+
+/// Try to produce some number that indicates a function is getting smaller /
+/// simpler.
+static uint64_t computeMIRComplexityScoreImpl(const MachineFunction &MF) {
+  uint64_t Score = 0;
+  const MachineFrameInfo &MFI = MF.getFrameInfo();
+
+  // Add for stack objects
+  Score += MFI.getNumObjects();
+
+  // Add in the block count.
+  Score += 2 * MF.size();
+
+  for (const MachineBasicBlock &MBB : MF) {
+    for (const MachineInstr &MI : MBB) {
+      const unsigned Opc = MI.getOpcode();
+
+      // Reductions may want or need to introduce implicit_defs, so don't count
+      // them.
+      // TODO: These probably should count in some way.
+      if (Opc == TargetOpcode::IMPLICIT_DEF ||
+          Opc == TargetOpcode::G_IMPLICIT_DEF)
+        continue;
+
+      // Each instruction adds to the score
+      Score += 4;
+
+      if (Opc == TargetOpcode::PHI || Opc == TargetOpcode::G_PHI ||
+          Opc == TargetOpcode::INLINEASM || Opc == TargetOpcode::INLINEASM_BR)
+        ++Score;
+
+      if (MI.getFlags() != 0)
+        ++Score;
+
+      // Increase weight for more operands.
+      for (const MachineOperand &MO : MI.operands()) {
+        ++Score;
+
+        // Treat registers as more complex.
+        if (MO.isReg()) {
+          ++Score;
+
+          // And subregisters as even more complex.
+          if (MO.getSubReg()) {
+            ++Score;
+            if (MO.isDef())
+              ++Score;
+          }
+        } else if (MO.isRegMask())
+          ++Score;
+      }
+    }
+  }
+
+  return Score;
+}
+
+uint64_t ReducerWorkItem::computeMIRComplexityScore() const {
+  uint64_t Score = 0;
+
+  for (const Function &F : getModule()) {
+    if (auto *MF = MMI->getMachineFunction(F))
+      Score += computeMIRComplexityScoreImpl(*MF);
+  }
+
+  return Score;
+}