[llvm-reduce] optionally keep running delta passes until they stop making the IR smaller

[regehr]

Summary

Currently, llvm-reduce runs each of its delta passes once, in a fixed order, and then exits. This is a reasonable default behavior since it allows llvm-reduce to run fairly quickly, but it fails to account for the case where a pass later in the phase ordering creates opportunities for a pass earlier in the phase ordering to make more progress.

This patch does not change the default behavior of llvm-reduce, but adds a command line parameter "max-pass-iterations" that specifies the largest number of times that the requested set of delta passes will be run. It also adds logic to bail out of the top-level reduction loop as soon as running the entire collection of passes fails to make the IR module smaller.

I have a small collection of test inputs to llvm-reduce, the average size before reduction is 15 KB. After reduction by the current llvm-reduce, the average IR file is 388 bytes. After reduction using the llvm-reduce with this proposed patch (and max-pass-iterations=10, but it always bails out earlier than that) the average reduced IR file is 250 bytes. This seems like a pretty decent win for a very simple patch, and furthermore since the default value for max-pass-iterations is 1, llvm-reduce will not be slowed down for anyone who doesn't use this new option.

I was not able to convince myself that a test for this patch would be worthwhile, instead of being fragile and silly, given the utter simplicity of the patch.

[aeubanks]

a good option I'll probably be using in the future

llvm/tools/llvm-reduce/DeltaManager.cpp

110

not the greatest metric, perhaps add a FIXME for a better metric?

[regehr]

llvm/tools/llvm-reduce/DeltaManager.cpp

110

thanks for the review!

I'll add this fixme. I really don't have a better idea here. size of the textual IR is definitely a bit weird, but it has the advantage of encompassing all parts of the serialized IR. simpler metricss like counting instructions would fail to account for removing globals, metadata, etc.

[regehr]

add FIXME suggested by @aeubanks

[regehr]

oof, sorry, I'm still figuring out the new interface, this is committed here:

https://reviews.llvm.org/rG4eec1710c51865b47480bc63a736a3719496679d

[reames]

Just wanted to say thanks for adding this, it does look quite useful.

llvm/tools/llvm-reduce/DeltaManager.h

 #ifndef LLVM_TOOLS_LLVM_REDUCE_DELTAMANAGER_H
 #define LLVM_TOOLS_LLVM_REDUCE_DELTAMANAGER_H
 
 namespace llvm {
 class raw_ostream;
 class TestRunner;
 
 void printDeltaPasses(raw_ostream &OS);
-void runDeltaPasses(TestRunner &Tester);
+void runDeltaPasses(TestRunner &Tester, int MaxPassIterations);
 } // namespace llvm
 
 #endif

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
 }
 
-void llvm::runDeltaPasses(TestRunner &Tester) {
+// 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);
+  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)
+      break;
+    OldSize = NewSize;
+  }
 }

llvm/tools/llvm-reduce/llvm-reduce.cpp

InputLanguage("x", cl::ValueOptional,
                   cl::values(clEnumValN(InputLanguages::IR, "ir", ""),
                              clEnumValN(InputLanguages::MIR, "mir", "")),
                   cl::cat(Options));
 
 static cl::opt<std::string> TargetTriple("mtriple",
                                          cl::desc("Set the target triple"),
                                          cl::cat(Options));
 
+static cl::opt<int>
+    MaxPassIterations("max-pass-iterations",
+                      cl::desc("Maximum number of times to run the full set "
+                               "of delta passes (default=1)"),
+                      cl::init(1), cl::cat(Options));
+
 static codegen::RegisterCodeGenFlags CGF;
 
 void writeOutput(ReducerWorkItem &M, StringRef Message) {
   if (ReplaceInput) // In-place
     OutputFilename = InputFilename.c_str();
   else if (OutputFilename.empty() || OutputFilename == "-")
     OutputFilename = M.isMIR() ? "reduced.mir" : "reduced.ll";
   std::error_code EC;
int main(int Argc, char **Argv) {
   if (!OriginalProgram) {
     return 1;
   }
 
   // Initialize test environment
   TestRunner Tester(TestFilename, TestArguments, std::move(OriginalProgram));
 
   // Try to reduce code
-  runDeltaPasses(Tester);
+  runDeltaPasses(Tester, MaxPassIterations);
 
   // Print reduced file to STDOUT
   if (OutputFilename == "-")
     Tester.getProgram().print(outs(), nullptr);
   else
     writeOutput(Tester.getProgram(), "\nDone reducing! Reduced testcase: ");
 
   return 0;
 }