llvm-reduce: Try to kill parallel workitems once we have a result.

[arsenm]

Summary

The current reduction logic tries to reproduce what a serial reduction
would produce, and just takes the first one that is still
interesting. We still have to wait for all others to complete though,
which at that point is just a waste.

This helps speed things up with long running reducers, which I
frequently have. e.g. for the added sleep test on my system, it took
about 8 seconds before this change and about 4 after.

[regehr]

just fyi, the experience with this from C-Reduce is that first, killed compilers will tend to leave crap in /tmp or similar, and this builds up over time, but usually not that quickly.

and second, this only worked robustly when I made a new process group to put the interestingness test into and then killed the entire group.

[arsenm]

Rebase on optional change

[arsenm]

In D138953#3958442, @regehr wrote:

just fyi, the experience with this from C-Reduce is that first, killed compilers will tend to leave crap in /tmp or similar, and this builds up over time, but usually not that quickly.

opt and llc don't do this, so I'm not too worried about this. Not sure what I would try to do about this anyway since tools tend to make up their own random unique filenames.

and second, this only worked robustly when I made a new process group to put the interestingness test into and then killed the entire group.

Do you expect that in this patch? I don't see an existing abstraction for this

[regehr]

In D138953#3965051, @arsenm wrote:

In D138953#3958442, @regehr wrote:

just fyi, the experience with this from C-Reduce is that first, killed compilers will tend to leave crap in /tmp or similar, and this builds up over time, but usually not that quickly.

opt and llc don't do this, so I'm not too worried about this. Not sure what I would try to do about this anyway since tools tend to make up their own random unique filenames.

probably the best option (only supported by some tools) is to tell the tool what tmp directory it should use, and then arrange for this to be removed when the reducer terminates.

and second, this only worked robustly when I made a new process group to put the interestingness test into and then killed the entire group.

Do you expect that in this patch? I don't see an existing abstraction for this

fine to defer this (and the thing above) until needed, but please add a TODO sorta thing reminding us that we might want to do this later

also when testing/using this functionality, definitely keep an eye out for things that keep running past when you try to kill them, because you didn't actually kill them but only killed some other process

[arsenm]

Rebase

[arsenm]

In D138953#3965112, @regehr wrote:

In D138953#3965051, @arsenm wrote:

In D138953#3958442, @regehr wrote:

just fyi, the experience with this from C-Reduce is that first, killed compilers will tend to leave crap in /tmp or similar, and this builds up over time, but usually not that quickly.

opt and llc don't do this, so I'm not too worried about this. Not sure what I would try to do about this anyway since tools tend to make up their own random unique filenames.

probably the best option (only supported by some tools) is to tell the tool what tmp directory it should use, and then arrange for this to be removed when the reducer terminates.

and second, this only worked robustly when I made a new process group to put the interestingness test into and then killed the entire group.

Do you expect that in this patch? I don't see an existing abstraction for this

fine to defer this (and the thing above) until needed, but please add a TODO sorta thing reminding us that we might want to do this later

also when testing/using this functionality, definitely keep an eye out for things that keep running past when you try to kill them, because you didn't actually kill them but only killed some other process

Core files are now turned off by default as of 95abdeba6152c3fa15e96b4bababe6311bc9c118

[arsenm]

ping

[arsenm]

Rebase

[arsenm]

ping

[aeubanks]

sorry, just got back from vacation, will try to look at this (and all your other patches) sometime this week

[fhahn]

LGTM, thanks! Might be good to wait with landing until tomorrow in case @aeubanks or anybody else has additional comments.

llvm/tools/llvm-reduce/ReducerWorkItem.h

19

is this include need here? Seems like nothing from <atomic> is used here.

llvm/tools/llvm-reduce/TestRunner.cpp

79

nit: might be good to use early exit to reduce indent?

[arsenm]

llvm/tools/llvm-reduce/TestRunner.cpp

79

Switched to while loop to reduce indent

84–86

I also fixed this problem, so I've switched this to a 0 second timeout. sys::Wait now uses optional, and distinguishes nullopt=wait infinity and 0 is expect immediate exit

[arsenm]

4f575620d51032cf98424c9defafe4dfc8d66f45

[arsenm]

New test, make test work. Test takes way longer than I would like now for some reason

llvm/test/tools/llvm-reduce/Inputs/sleep.py

+#!/bin/python
+
+import time
+import sys
+
+sleep_seconds = int(sys.argv[1])
+time.sleep(sleep_seconds)
+

llvm/test/tools/llvm-reduce/parallel-workitem-kill.ll

+; REQUIRES: thread_support
+; RUN: llvm-reduce --process-poll-interval=1 -j 4 %s -o %t --delta-passes=instructions --test %python --test-arg %S/Inputs/sleep.py --test-arg 2
+; RUN: FileCheck %s < %t
+
+; CHECK: define void @foo
+; CHECK-NEXT: ret void
+
+define void @foo(ptr %ptr) {
+  store i32 0, ptr %ptr
+  store i32 1, ptr %ptr
+  store i32 2, ptr %ptr
+  store i32 3, ptr %ptr
+  store i32 4, ptr %ptr
+  store i32 5, ptr %ptr
+  store i32 6, ptr %ptr
+  store i32 7, ptr %ptr
+  store i32 8, ptr %ptr
+  store i32 9, ptr %ptr
+  store i32 10, ptr %ptr
+  store i32 11, ptr %ptr
+  store i32 12, ptr %ptr
+  store i32 13, ptr %ptr
+  store i32 14, ptr %ptr
+  store i32 15, ptr %ptr
+  store i32 16, ptr %ptr
+  store i32 17, ptr %ptr
+  store i32 18, ptr %ptr
+  store i32 19, ptr %ptr
+  store i32 20, ptr %ptr
+  store i32 21, ptr %ptr
+  store i32 22, ptr %ptr
+  store i32 23, ptr %ptr
+  store i32 24, ptr %ptr
+  store i32 25, ptr %ptr
+  store i32 26, ptr %ptr
+  store i32 27, ptr %ptr
+  store i32 28, ptr %ptr
+  store i32 29, ptr %ptr
+  store i32 30, ptr %ptr
+  store i32 31, ptr %ptr
+  store i32 32, ptr %ptr
+  store i32 33, ptr %ptr
+  store i32 34, ptr %ptr
+  store i32 35, ptr %ptr
+  store i32 36, ptr %ptr
+  store i32 37, ptr %ptr
+  store i32 38, ptr %ptr
+  store i32 39, ptr %ptr
+  store i32 40, ptr %ptr
+  ret void
+}
+

llvm/tools/llvm-reduce/ReducerWorkItem.h

 
 #include "llvm/Bitcode/BitcodeReader.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/ModuleSummaryIndex.h"
 #include "llvm/Target/TargetMachine.h"
 
+#include <atomic>
+
 using namespace llvm;
 
 class ReducerWorkItem {
 public:
   std::shared_ptr<Module> M;
   std::unique_ptr<BitcodeLTOInfo> LTOInfo;
   std::unique_ptr<MachineModuleInfo> MMI;
 

llvm/tools/llvm-reduce/TestRunner.h

 public:
   TestRunner(StringRef TestName, const std::vector<std::string> &TestArgs,
              std::unique_ptr<ReducerWorkItem> Program,
              std::unique_ptr<TargetMachine> TM, StringRef ToolName,
              StringRef OutputFilename, bool InputIsBitcode, bool OutputBitcode);
 
   /// Runs the interesting-ness test for the specified file
   /// @returns 0 if test was successful, 1 if otherwise
-  int run(StringRef Filename) const;
+  int run(StringRef Filename, const std::atomic<bool> &Killed) const;
 
   /// Returns the most reduced version of the original testcase
   ReducerWorkItem &getProgram() const { return *Program; }
 
   void setProgram(std::unique_ptr<ReducerWorkItem> P);
 
   const TargetMachine *getTargetMachine() const { return TM.get(); }
 

llvm/tools/llvm-reduce/TestRunner.cpp

 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Bitcode/BitcodeReader.h"
 #include "llvm/Bitcode/BitcodeWriter.h"
 #include "llvm/Passes/PassBuilder.h"
 #include "llvm/Transforms/IPO/ThinLTOBitcodeWriter.h"
 
 using namespace llvm;
 
+extern cl::OptionCategory LLVMReduceOptions;
+static cl::opt<unsigned> PollInterval("process-poll-interval",
+                                      cl::desc("child process wait polling"),
+                                      cl::init(5), cl::Hidden,
+                                      cl::cat(LLVMReduceOptions));
+
 TestRunner::TestRunner(StringRef TestName,
                        const std::vector<std::string> &TestArgs,
                        std::unique_ptr<ReducerWorkItem> Program,
                        std::unique_ptr<TargetMachine> TM, StringRef ToolName,
                        StringRef OutputName, bool InputIsBitcode,
                        bool OutputBitcode)
     : TestName(TestName), ToolName(ToolName), TestArgs(TestArgs),
       Program(std::move(Program)), TM(std::move(TM)),
       OutputFilename(OutputName), InputIsBitcode(InputIsBitcode),
       EmitBitcode(OutputBitcode) {
   assert(this->Program && "Initialized with null program?");
 }
 
 static constexpr std::array<std::optional<StringRef>, 3> DefaultRedirects = {
     StringRef()};
 static constexpr std::array<std::optional<StringRef>, 3> NullRedirects;
 
 /// Runs the interestingness test, passes file to be tested as first argument
 /// and other specified test arguments after that.
-int TestRunner::run(StringRef Filename) const {
+int TestRunner::run(StringRef Filename, const std::atomic<bool> &Killed) const {
   std::vector<StringRef> ProgramArgs;
   ProgramArgs.push_back(TestName);
 
   for (const auto &Arg : TestArgs)
     ProgramArgs.push_back(Arg);
 
   ProgramArgs.push_back(Filename);
 
   std::string ErrMsg;
-
-  int Result =
-      sys::ExecuteAndWait(TestName, ProgramArgs, /*Env=*/std::nullopt,
-                          Verbose ? DefaultRedirects : NullRedirects,
-                          /*SecondsToWait=*/0, /*MemoryLimit=*/0, &ErrMsg);
+  bool ExecutionFailed;
+  sys::ProcessInfo PI =
+      sys::ExecuteNoWait(TestName, ProgramArgs, /*Env=*/std::nullopt,
+                         /*MemoryLimit=*/0, &ErrMsg, &ExecutionFailed);
 
-  if (Result < 0) {
+  if (ExecutionFailed) {
     Error E = make_error<StringError>("Error running interesting-ness test: " +
                                           ErrMsg,
                                       inconvertibleErrorCode());
     errs() << toString(std::move(E)) << '\n';
     exit(1);
   }
 
-  return !Result;
+  // Poll every few seconds, taking a break to check if we should try to kill
+  // the process. We're trying to early exit on long running parallel reductions
+  // once we know they don't matter.
+  std::optional<unsigned> SecondsToWait(PollInterval);
+  bool Polling = true;
+  sys::ProcessInfo WaitPI;
+
+  do {
+    WaitPI = sys::Wait(PI, SecondsToWait, &ErrMsg, nullptr, Polling);
+    if (WaitPI.Pid == 0) {
+      // Process has not changed state.
+
+      // TODO: This should probably be std::atomic_flag
+      if (Killed) {
+        // The current Program API does not have a way to directly kill, so
+        // we're stuck using a 1 second timeout.
+        SecondsToWait = 1;
+        Polling = false;
+      }
+    }
+  } while (WaitPI.Pid == 0);
+
+  return !WaitPI.ReturnCode;
 }
 
 void TestRunner::setProgram(std::unique_ptr<ReducerWorkItem> P) {
   assert(P && "Setting null program?");
   Program = std::move(P);
 }
 
 void writeBitcode(ReducerWorkItem &M, raw_ostream &OutStream) {

llvm/tools/llvm-reduce/deltas/Delta.cpp

 unsigned NumJobs = 1;
 #endif
 
 void writeBitcode(ReducerWorkItem &M, raw_ostream &OutStream);
 
 void readBitcode(ReducerWorkItem &M, MemoryBufferRef Data, LLVMContext &Ctx,
                  StringRef ToolName);
 
-bool isReduced(ReducerWorkItem &M, const TestRunner &Test) {
+bool isReduced(ReducerWorkItem &M, const TestRunner &Test,
+               const std::atomic<bool> &Killed) {
   const bool UseBitcode = Test.inputIsBitcode() || TmpFilesAsBitcode;
 
   SmallString<128> CurrentFilepath;
 
   // Write ReducerWorkItem to tmp file
   int FD;
   std::error_code EC = sys::fs::createTemporaryFile(
       "llvm-reduce", M.isMIR() ? "mir" : (UseBitcode ? "bc" : "ll"), FD,
bool isReduced(ReducerWorkItem &M, const TestRunner &Test,
   Out.os().close();
   if (Out.os().has_error()) {
     errs() << "Error emitting bitcode to file '" << CurrentFilepath
            << "': " << Out.os().error().message();
     exit(1);
   }
 
   // Current Chunks aren't interesting
-  return Test.run(CurrentFilepath);
+  return Test.run(CurrentFilepath, Killed);
 }
 
 /// Splits Chunks in half and prints them.
 /// If unable to split (when chunk size is 1) returns false.
 static bool increaseGranularity(std::vector<Chunk> &Chunks) {
   if (Verbose)
     errs() << "Increasing granularity...";
   std::vector<Chunk> NewChunks;

 
 // Check if \p ChunkToCheckForUninterestingness is interesting. Returns the
 // modified module if the chunk resulted in a reduction.
 static std::unique_ptr<ReducerWorkItem>
 CheckChunk(const Chunk &ChunkToCheckForUninterestingness,
            std::unique_ptr<ReducerWorkItem> Clone, const TestRunner &Test,
            ReductionFunc ExtractChunksFromModule,
            const DenseSet<Chunk> &UninterestingChunks,
-           const std::vector<Chunk> &ChunksStillConsideredInteresting) {
+           const std::vector<Chunk> &ChunksStillConsideredInteresting,
+           const std::atomic<bool> &Killed) {
   // Take all of ChunksStillConsideredInteresting chunks, except those we've
   // already deemed uninteresting (UninterestingChunks) but didn't remove
   // from ChunksStillConsideredInteresting yet, and additionally ignore
   // ChunkToCheckForUninterestingness chunk.
   std::vector<Chunk> CurrentChunks;
   CurrentChunks.reserve(ChunksStillConsideredInteresting.size() -
                         UninterestingChunks.size() - 1);
   copy_if(ChunksStillConsideredInteresting, std::back_inserter(CurrentChunks),
CheckChunk(const Chunk &ChunkToCheckForUninterestingness,
   if (Verbose) {
     errs() << "Ignoring: ";
     ChunkToCheckForUninterestingness.print();
     for (const Chunk &C : UninterestingChunks)
       C.print();
     errs() << "\n";
   }
 
-  if (!isReduced(*Clone, Test)) {
+  if (!isReduced(*Clone, Test, Killed)) {
     // Program became non-reduced, so this chunk appears to be interesting.
     if (Verbose)
       errs() << "\n";
     return nullptr;
   }
   return Clone;
 }
 
 static SmallString<0> ProcessChunkFromSerializedBitcode(
     Chunk &ChunkToCheckForUninterestingness, TestRunner &Test,
     ReductionFunc ExtractChunksFromModule, DenseSet<Chunk> &UninterestingChunks,
     std::vector<Chunk> &ChunksStillConsideredInteresting,
-    SmallString<0> &OriginalBC, std::atomic<bool> &AnyReduced) {
+    SmallString<0> &OriginalBC, std::atomic<bool> &AnyReduced,
+    const std::atomic<bool> &Killed) {
   LLVMContext Ctx;
   auto CloneMMM = std::make_unique<ReducerWorkItem>();
   MemoryBufferRef Data(StringRef(OriginalBC), "<bc file>");
   readBitcode(*CloneMMM, Data, Ctx, Test.getToolName());
 
   SmallString<0> Result;
   if (std::unique_ptr<ReducerWorkItem> ChunkResult =
           CheckChunk(ChunkToCheckForUninterestingness, std::move(CloneMMM),
                      Test, ExtractChunksFromModule, UninterestingChunks,
-                     ChunksStillConsideredInteresting)) {
+                     ChunksStillConsideredInteresting, Killed)) {
     raw_svector_ostream BCOS(Result);
     writeBitcode(*ChunkResult, BCOS);
     // Communicate that the task reduced a chunk.
     AnyReduced = true;
   }
   return Result;
 }
 
int Targets;
     // made.
     std::vector<Chunk> AllChunks = {{0, INT_MAX}};
     Oracle Counter(AllChunks);
     ExtractChunksFromModule(Counter, Test.getProgram());
     Targets = Counter.count();
 
     assert(!verifyReducerWorkItem(Test.getProgram(), &errs()) &&
            "input module is broken after counting chunks");
-    assert(isReduced(Test.getProgram(), Test) &&
+    assert(isReduced(Test.getProgram(), Test, std::atomic<bool>()) &&
            "input module no longer interesting after counting chunks");
 
 #ifndef NDEBUG
     // Make sure that the number of chunks does not change as we reduce.
     std::vector<Chunk> NoChunks = {{0, INT_MAX}};
     Oracle NoChunksCounter(NoChunks);
     std::unique_ptr<ReducerWorkItem> Clone =
         cloneReducerWorkItem(Test.getProgram(), Test.getTargetMachine());
do {
     // When running with more than one thread, serialize the original bitcode
     // to OriginalBC.
     SmallString<0> OriginalBC;
     if (NumJobs > 1) {
       raw_svector_ostream BCOS(OriginalBC);
       writeBitcode(Test.getProgram(), BCOS);
     }
 
+    // If doing parallel reduction, signal to running workitem threads that we
+    // no longer care about their results. They should try to kill the reducer
+    // workitem process and exit.
+    std::atomic<bool> Killed = false;
+
     SharedTaskQueue TaskQueue;
     for (auto I = ChunksStillConsideredInteresting.rbegin(),
               E = ChunksStillConsideredInteresting.rend();
          I != E; ++I) {
       std::unique_ptr<ReducerWorkItem> Result = nullptr;
       unsigned WorkLeft = std::distance(I, E);
 
       // Run in parallel mode, if the user requested more than one thread and
for (auto I = ChunksStillConsideredInteresting.rbegin(),
         // ChunkThreadPool. When the tasks are added to the pool, parse the
         // original module from OriginalBC with a fresh LLVMContext object. This
         // ensures that the cloned module of each task uses an independent
         // LLVMContext object. If a task reduces the input, serialize the result
         // back in the corresponding Result element.
         for (unsigned J = 0; J < NumInitialTasks; ++J) {
           TaskQueue.emplace_back(ChunkThreadPool.async(
               [J, I, &Test, &ExtractChunksFromModule, &UninterestingChunks,
-               &ChunksStillConsideredInteresting, &OriginalBC, &AnyReduced]() {
+               &ChunksStillConsideredInteresting, &OriginalBC, &AnyReduced,
+               &Killed]() {
                 return ProcessChunkFromSerializedBitcode(
                     *(I + J), Test, ExtractChunksFromModule,
                     UninterestingChunks, ChunksStillConsideredInteresting,
-                    OriginalBC, AnyReduced);
+                    OriginalBC, AnyReduced, Killed);
               }));
         }
 
         // Start processing results of the queued tasks. We wait for the first
         // task in the queue to finish. If it reduced a chunk, we parse the
         // result and exit the loop.
         //  Otherwise we will try to schedule a new task, if
         //  * no other pending job reduced a chunk and
         //  * we have not reached the end of the chunk.
         while (!TaskQueue.empty()) {
           auto &Future = TaskQueue.front();
           Future.wait();
 
           NumChunksProcessed++;
           SmallString<0> Res = Future.get();
           TaskQueue.pop_front();
           if (Res.empty()) {
             unsigned NumScheduledTasks = NumChunksProcessed + TaskQueue.size();
             if (!AnyReduced && I + NumScheduledTasks != E) {
               Chunk &ChunkToCheck = *(I + NumScheduledTasks);
               TaskQueue.emplace_back(ChunkThreadPool.async(
                   [&Test, &ExtractChunksFromModule, &UninterestingChunks,
                    &ChunksStillConsideredInteresting, &OriginalBC,
-                   &ChunkToCheck, &AnyReduced]() {
+                   &ChunkToCheck, &AnyReduced, &Killed]() {
                     return ProcessChunkFromSerializedBitcode(
                         ChunkToCheck, Test, ExtractChunksFromModule,
                         UninterestingChunks, ChunksStillConsideredInteresting,
-                        OriginalBC, AnyReduced);
+                        OriginalBC, AnyReduced, Killed);
                   }));
             }
             continue;
           }
 
           Result = std::make_unique<ReducerWorkItem>();
           MemoryBufferRef Data(StringRef(Res), "<bc file>");
           readBitcode(*Result, Data, Test.getProgram().M->getContext(),
                       Test.getToolName());
           break;
         }
 
+        Killed = true;
+
         // If we broke out of the loop, we still need to wait for everything to
         // avoid race access to the chunk set.
         //
         // TODO: Create a way to kill remaining items we're ignoring; they could
         // take a long time.
         waitAndDiscardResultsBarrier(TaskQueue);
 
         // Forward I to the last chunk processed in parallel.
         I += NumChunksProcessed - 1;
       } else {
         Result = CheckChunk(
             *I,
             cloneReducerWorkItem(Test.getProgram(), Test.getTargetMachine()),
             Test, ExtractChunksFromModule, UninterestingChunks,
-            ChunksStillConsideredInteresting);
+            ChunksStillConsideredInteresting, Killed);
       }
 
       if (!Result)
         continue;
 
       Chunk &ChunkToCheckForUninterestingness = *I;
       FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = true;
       UninterestingChunks.insert(ChunkToCheckForUninterestingness);

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

 static cl::opt<int>
     MaxPassIterations("max-pass-iterations",
                       cl::desc("Maximum number of times to run the full set "
                                "of delta passes (default=5)"),
                       cl::init(5), cl::cat(LLVMReduceOptions));
 
 static codegen::RegisterCodeGenFlags CGF;
 
-bool isReduced(ReducerWorkItem &M, const TestRunner &Test);
+bool isReduced(ReducerWorkItem &M, const TestRunner &Test,
+               const std::atomic<bool> &Killed);
 
 /// Turn off crash debugging features
 ///
 /// Crash is expected, so disable crash reports and symbolization to reduce
 /// output clutter and avoid potentially slow symbolization.
 static void disableEnvironmentDebugFeatures() {
   sys::Process::PreventCoreFiles();
 
int main(int Argc, char **Argv) {
   TestRunner Tester(TestFilename, TestArguments, std::move(OriginalProgram),
                     std::move(TM), ToolName, OutputFilename, InputIsBitcode,
                     OutputBitcode);
 
   // This parses and writes out the testcase into a temporary file copy for the
   // test, rather than evaluating the source IR directly. This is for the
   // convenience of lit tests; the stripped out comments may have broken the
   // interestingness checks.
-  if (!isReduced(Tester.getProgram(), Tester)) {
+  if (!isReduced(Tester.getProgram(), Tester, std::atomic<bool>())) {
     errs() << "\nInput isn't interesting! Verify interesting-ness test\n";
     return 1;
   }
 
   // Try to reduce code
   runDeltaPasses(Tester, MaxPassIterations);
 
   // Print reduced file to STDOUT
   if (OutputFilename == "-")
     Tester.getProgram().print(outs(), nullptr);
   else
     Tester.writeOutput("Done reducing! Reduced testcase: ");
 
   return 0;
 }