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

   1 //===- Delta.h - Delta Debugging Algorithm Implementation -----------------===//
   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 // This file contains the implementation for the Delta Debugging Algorithm:
  10 // it splits a given set of Targets (i.e. Functions, Instructions, BBs, etc.)
  11 // into chunks and tries to reduce the number chunks that are interesting.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_TOOLS_LLVM_REDUCE_DELTAS_DELTA_H
  16 #define LLVM_TOOLS_LLVM_REDUCE_DELTAS_DELTA_H
  17
  18 #include "TestRunner.h"
  19 #include "llvm/ADT/ScopeExit.h"
  20 #include <functional>
  21 #include <utility>
  22 #include <vector>
  23
  24 namespace llvm {
  25
  26 struct Chunk {
  27   int Begin;
  28   int End;
  29
  30   /// Helper function to verify if a given Target-index is inside the Chunk
  31   bool contains(int Index) const { return Index >= Begin && Index <= End; }
  32
  33   void print() const {
  34     errs() << "[" << Begin;
  35     if (End - Begin != 0)
  36       errs() << "," << End;
  37     errs() << "]";
  38   }
  39
  40   /// Operator when populating CurrentChunks in Generic Delta Pass
  41   friend bool operator!=(const Chunk &C1, const Chunk &C2) {
  42     return C1.Begin != C2.Begin || C1.End != C2.End;
  43   }
  44
  45   /// Operator used for sets
  46   friend bool operator<(const Chunk &C1, const Chunk &C2) {
  47     return std::tie(C1.Begin, C1.End) < std::tie(C2.Begin, C2.End);
  48   }
  49 };
  50
  51 /// Provides opaque interface for querying into ChunksToKeep without having to
  52 /// actually understand what is going on.
  53 class Oracle {
  54   /// Out of all the features that we promised to be,
  55   /// how many have we already processed?
  56   int Index = 0;
  57
  58   /// The actual workhorse, contains the knowledge whether or not
  59   /// some particular feature should be preserved this time.
  60   ArrayRef<Chunk> ChunksToKeep;
  61
  62 public:
  63   explicit Oracle(ArrayRef<Chunk> ChunksToKeep) : ChunksToKeep(ChunksToKeep) {}
  64
  65   /// Should be called for each feature on which we are operating.
  66   /// Name is self-explanatory - if returns true, then it should be preserved.
  67   bool shouldKeep() {
  68     if (ChunksToKeep.empty()) {
  69       ++Index;
  70       return false; // All further features are to be discarded.
  71     }
  72
  73     // Does the current (front) chunk contain such a feature?
  74     bool ShouldKeep = ChunksToKeep.front().contains(Index);
  75
  76     // Is this the last feature in the chunk?
  77     if (ChunksToKeep.front().End == Index)
  78       ChunksToKeep = ChunksToKeep.drop_front(); // Onto next chunk.
  79
  80     ++Index;
  81
  82     return ShouldKeep;
  83   }
  84
  85   int count() { return Index; }
  86 };
  87
  88 /// This function implements the Delta Debugging algorithm, it receives a
  89 /// number of Targets (e.g. Functions, Instructions, Basic Blocks, etc.) and
  90 /// splits them in half; these chunks of targets are then tested while ignoring
  91 /// one chunk, if a chunk is proven to be uninteresting (i.e. fails the test)
  92 /// it is removed from consideration. The algorithm will attempt to split the
  93 /// Chunks in half and start the process again until it can't split chunks
  94 /// anymore.
  95 ///
  96 /// This function is intended to be called by each specialized delta pass (e.g.
  97 /// RemoveFunctions) and receives three key parameters:
  98 /// * Test: The main TestRunner instance which is used to run the provided
  99 /// interesting-ness test, as well as to store and access the reduced Program.
 100 /// * ExtractChunksFromModule: A function used to tailor the main program so it
 101 /// only contains Targets that are inside Chunks of the given iteration.
 102 /// Note: This function is implemented by each specialized Delta pass
 103 ///
 104 /// Other implementations of the Delta Debugging algorithm can also be found in
 105 /// the CReduce, Delta, and Lithium projects.
 106 void runDeltaPass(
 107     TestRunner &Test,
 108     function_ref<void(Oracle &, Module &)> ExtractChunksFromModule);
 109 void runDeltaPass(
 110     TestRunner &Test,
 111     function_ref<void(Oracle &, MachineFunction &)> ExtractChunksFromModule);
 112 } // namespace llvm
 113
 114 #endif