1//===-- reduce-chunk-list.cpp - Reduce a chunks list to its minimal size --===//
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// See the llvm-project/llvm/docs/ProgrammersManual.rst to see how to use this
10// tool
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/ADT/DenseSet.h"
15#include "llvm/Support/CommandLine.h"
16#include "llvm/Support/DebugCounter.h"
17#include "llvm/Support/Program.h"
18
19using namespace llvm;
20
21static cl::opt<std::string> ReproductionCmd(cl::Positional, cl::Required);
22
23static cl::opt<std::string> StartChunks(cl::Positional, cl::Required);
24
25static cl::opt<bool> Pessimist("pessimist", cl::init(Val: false));
26
27using Chunk = DebugCounter::Chunk;
28
29namespace {
30
31SmallVector<Chunk> simplifyChunksList(ArrayRef<Chunk> Chunks) {
32 SmallVector<Chunk> Res;
33 Res.push_back(Elt: Chunks.front());
34 for (unsigned Idx = 1; Idx < Chunks.size(); Idx++) {
35 if (Chunks[Idx].Begin == Res.back().End + 1)
36 Res.back().End = Chunks[Idx].End;
37 else
38 Res.push_back(Elt: Chunks[Idx]);
39 }
40 return Res;
41}
42
43bool isStillInteresting(ArrayRef<Chunk> Chunks) {
44 SmallVector<Chunk> SimpleChunks = simplifyChunksList(Chunks);
45
46 std::string ChunkStr;
47 {
48 raw_string_ostream OS(ChunkStr);
49 DebugCounter::printChunks(OS, SimpleChunks);
50 }
51
52 errs() << "Checking with: " << ChunkStr << "\n";
53
54 std::vector<StringRef> Argv;
55 Argv.push_back(x: ReproductionCmd);
56 Argv.push_back(x: ChunkStr);
57
58 std::string ErrMsg;
59 bool ExecutionFailed;
60 int Result = sys::ExecuteAndWait(Program: Argv[0], Args: Argv, Env: std::nullopt, Redirects: {}, SecondsToWait: 0, MemoryLimit: 0,
61 ErrMsg: &ErrMsg, ExecutionFailed: &ExecutionFailed);
62 if (ExecutionFailed) {
63 errs() << "failed to execute : " << Argv[0] << " : " << ErrMsg << "\n";
64 exit(status: 1);
65 }
66
67 bool Res = Result != 0;
68 if (Res) {
69 errs() << "SUCCESS : Still Interesting\n";
70 } else {
71 errs() << "FAILURE : Not Interesting\n";
72 }
73 return Res;
74}
75
76bool increaseGranularity(SmallVector<Chunk> &Chunks) {
77 errs() << "Increasing granularity\n";
78 SmallVector<Chunk> NewChunks;
79 bool SplitOne = false;
80
81 for (auto &C : Chunks) {
82 if (C.Begin == C.End) {
83 NewChunks.push_back(Elt: C);
84 } else {
85 int Half = (C.Begin + C.End) / 2;
86 NewChunks.push_back(Elt: {.Begin: C.Begin, .End: Half});
87 NewChunks.push_back(Elt: {.Begin: Half + 1, .End: C.End});
88 SplitOne = true;
89 }
90 }
91 if (SplitOne) {
92 Chunks = std::move(NewChunks);
93 }
94 return SplitOne;
95}
96
97} // namespace
98
99int main(int argc, char **argv) {
100 cl::ParseCommandLineOptions(argc, argv);
101
102 SmallVector<Chunk> CurrChunks;
103 if (DebugCounter::parseChunks(Str: StartChunks, Res&: CurrChunks)) {
104 return 1;
105 }
106
107 auto Program = sys::findProgramByName(Name: ReproductionCmd);
108 if (!Program) {
109 errs() << "failed to find command : " << ReproductionCmd << "\n";
110 return 1;
111 }
112 ReproductionCmd.setValue(V: Program.get());
113
114 errs() << "Input Checking:\n";
115 if (!isStillInteresting(Chunks: CurrChunks)) {
116 errs() << "starting chunks are not interesting\n";
117 return 1;
118 }
119 if (CurrChunks.size() == 1)
120 increaseGranularity(Chunks&: CurrChunks);
121 if (Pessimist)
122 while (increaseGranularity(Chunks&: CurrChunks))
123 /* empty body */;
124 while (1) {
125 for (int Idx = (CurrChunks.size() - 1); Idx >= 0; Idx--) {
126 if (CurrChunks.size() == 1)
127 break;
128
129 Chunk Testing = CurrChunks[Idx];
130 errs() << "Trying to remove : ";
131 Testing.print(OS&: errs());
132 errs() << "\n";
133
134 CurrChunks.erase(CI: CurrChunks.begin() + Idx);
135
136 if (!isStillInteresting(Chunks: CurrChunks))
137 CurrChunks.insert(I: CurrChunks.begin() + Idx, Elt: Testing);
138 }
139 bool HasSplit = increaseGranularity(Chunks&: CurrChunks);
140 if (!HasSplit)
141 break;
142 }
143
144 errs() << "Minimal Chunks = ";
145 DebugCounter::printChunks(OS&: llvm::errs(), simplifyChunksList(Chunks: CurrChunks));
146 errs() << "\n";
147}
148