Bug Summary

File:build/llvm-toolchain-snapshot-15~++20220406101104+1235aaefbd4f/llvm/tools/bugpoint/CrashDebugger.cpp
Warning:line 278, column 18
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name CrashDebugger.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220406101104+1235aaefbd4f/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-15/lib/clang/15.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I tools/bugpoint -I /build/llvm-toolchain-snapshot-15~++20220406101104+1235aaefbd4f/llvm/tools/bugpoint -I include -I /build/llvm-toolchain-snapshot-15~++20220406101104+1235aaefbd4f/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-15/lib/clang/15.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220406101104+1235aaefbd4f/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220406101104+1235aaefbd4f/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220406101104+1235aaefbd4f/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220406101104+1235aaefbd4f/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220406101104+1235aaefbd4f/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220406101104+1235aaefbd4f/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220406101104+1235aaefbd4f/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-04-07-032413-15978-1 -x c++ /build/llvm-toolchain-snapshot-15~++20220406101104+1235aaefbd4f/llvm/tools/bugpoint/CrashDebugger.cpp

/build/llvm-toolchain-snapshot-15~++20220406101104+1235aaefbd4f/llvm/tools/bugpoint/CrashDebugger.cpp

→
1//===- CrashDebugger.cpp - Debug compilation crashes ----------------------===//
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 defines the bugpoint internals that narrow down compilation crashes
10//
11//===----------------------------------------------------------------------===//
12
13#include "BugDriver.h"
14#include "ListReducer.h"
15#include "ToolRunner.h"
16#include "llvm/ADT/SmallPtrSet.h"
17#include "llvm/ADT/StringSet.h"
18#include "llvm/Analysis/TargetTransformInfo.h"
19#include "llvm/IR/CFG.h"
20#include "llvm/IR/Constants.h"
21#include "llvm/IR/DebugInfo.h"
22#include "llvm/IR/DerivedTypes.h"
23#include "llvm/IR/InstIterator.h"
24#include "llvm/IR/Instructions.h"
25#include "llvm/IR/LegacyPassManager.h"
26#include "llvm/IR/Module.h"
27#include "llvm/IR/ValueSymbolTable.h"
28#include "llvm/IR/Verifier.h"
29#include "llvm/Pass.h"
30#include "llvm/Support/CommandLine.h"
31#include "llvm/Support/FileUtilities.h"
32#include "llvm/Transforms/Scalar.h"
33#include "llvm/Transforms/Utils/BasicBlockUtils.h"
34#include "llvm/Transforms/Utils/Cloning.h"
35#include "llvm/Transforms/Utils/Local.h"
36#include <set>
37using namespace llvm;
38
39namespace {
40cl::opt<bool> KeepMain("keep-main",
41 cl::desc("Force function reduction to keep main"),
42 cl::init(false));
43cl::opt<bool> NoGlobalRM("disable-global-remove",
44 cl::desc("Do not remove global variables"),
45 cl::init(false));
46
47cl::opt<bool> NoAttributeRM("disable-attribute-remove",
48 cl::desc("Do not remove function attributes"),
49 cl::init(false));
50
51cl::opt<bool> ReplaceFuncsWithNull(
52 "replace-funcs-with-null",
53 cl::desc("When stubbing functions, replace all uses will null"),
54 cl::init(false));
55cl::opt<bool> DontReducePassList("disable-pass-list-reduction",
56 cl::desc("Skip pass list reduction steps"),
57 cl::init(false));
58
59cl::opt<bool> NoNamedMDRM("disable-namedmd-remove",
60 cl::desc("Do not remove global named metadata"),
61 cl::init(false));
62cl::opt<bool> NoStripDebugInfo("disable-strip-debuginfo",
63 cl::desc("Do not strip debug info metadata"),
64 cl::init(false));
65cl::opt<bool> NoStripDebugTypeInfo("disable-strip-debug-types",
66 cl::desc("Do not strip debug type info metadata"),
67 cl::init(false));
68cl::opt<bool> VerboseErrors("verbose-errors",
69 cl::desc("Print the output of crashing program"),
70 cl::init(false));
71}
72
73namespace llvm {
74class ReducePassList : public ListReducer<std::string> {
75 BugDriver &BD;
76
77public:
78 ReducePassList(BugDriver &bd) : BD(bd) {}
79
80 // Return true iff running the "removed" passes succeeds, and running the
81 // "Kept" passes fail when run on the output of the "removed" passes. If we
82 // return true, we update the current module of bugpoint.
83 Expected<TestResult> doTest(std::vector<std::string> &Removed,
84 std::vector<std::string> &Kept) override;
85};
86}
87
88Expected<ReducePassList::TestResult>
89ReducePassList::doTest(std::vector<std::string> &Prefix,
90 std::vector<std::string> &Suffix) {
91 std::string PrefixOutput;
92 std::unique_ptr<Module> OrigProgram;
93 if (!Prefix.empty()) {
94 outs() << "Checking to see if these passes crash: "
95 << getPassesString(Prefix) << ": ";
96 if (BD.runPasses(BD.getProgram(), Prefix, PrefixOutput))
97 return KeepPrefix;
98
99 OrigProgram = std::move(BD.Program);
100
101 BD.Program = parseInputFile(PrefixOutput, BD.getContext());
102 if (BD.Program == nullptr) {
103 errs() << BD.getToolName() << ": Error reading bitcode file '"
104 << PrefixOutput << "'!\n";
105 exit(1);
106 }
107 sys::fs::remove(PrefixOutput);
108 }
109
110 outs() << "Checking to see if these passes crash: " << getPassesString(Suffix)
111 << ": ";
112
113 if (BD.runPasses(BD.getProgram(), Suffix))
114 return KeepSuffix; // The suffix crashes alone...
115
116 // Nothing failed, restore state...
117 if (OrigProgram)
118 BD.Program = std::move(OrigProgram);
119 return NoFailure;
120}
121
122using BugTester = bool (*)(const BugDriver &, Module *);
123
124namespace {
125/// ReduceCrashingGlobalInitializers - This works by removing global variable
126/// initializers and seeing if the program still crashes. If it does, then we
127/// keep that program and try again.
128class ReduceCrashingGlobalInitializers : public ListReducer<GlobalVariable *> {
129 BugDriver &BD;
130 BugTester TestFn;
131
132public:
133 ReduceCrashingGlobalInitializers(BugDriver &bd, BugTester testFn)
134 : BD(bd), TestFn(testFn) {}
135
136 Expected<TestResult> doTest(std::vector<GlobalVariable *> &Prefix,
137 std::vector<GlobalVariable *> &Kept) override {
138 if (!Kept.empty() && TestGlobalVariables(Kept))
139 return KeepSuffix;
140 if (!Prefix.empty() && TestGlobalVariables(Prefix))
141 return KeepPrefix;
142 return NoFailure;
143 }
144
145 bool TestGlobalVariables(std::vector<GlobalVariable *> &GVs);
146};
147}
148
149bool ReduceCrashingGlobalInitializers::TestGlobalVariables(
150 std::vector<GlobalVariable *> &GVs) {
151 // Clone the program to try hacking it apart...
152 ValueToValueMapTy VMap;
153 std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
154
155 // Convert list to set for fast lookup...
156 std::set<GlobalVariable *> GVSet;
157
158 for (unsigned i = 0, e = GVs.size(); i != e; ++i) {
159 GlobalVariable *CMGV = cast<GlobalVariable>(VMap[GVs[i]]);
160 assert(CMGV && "Global Variable not in module?!")(static_cast <bool> (CMGV && "Global Variable not in module?!"
) ? void (0) : __assert_fail ("CMGV && \"Global Variable not in module?!\""
, "llvm/tools/bugpoint/CrashDebugger.cpp", 160, __extension__
__PRETTY_FUNCTION__));
161 GVSet.insert(CMGV);
162 }
163
164 outs() << "Checking for crash with only these global variables: ";
165 PrintGlobalVariableList(GVs);
166 outs() << ": ";
167
168 // Loop over and delete any global variables which we aren't supposed to be
169 // playing with...
170 for (GlobalVariable &I : M->globals())
171 if (I.hasInitializer() && !GVSet.count(&I)) {
172 DeleteGlobalInitializer(&I);
173 I.setLinkage(GlobalValue::ExternalLinkage);
174 I.setComdat(nullptr);
175 }
176
177 // Try running the hacked up program...
178 if (TestFn(BD, M.get())) {
179 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
180
181 // Make sure to use global variable pointers that point into the now-current
182 // module.
183 GVs.assign(GVSet.begin(), GVSet.end());
184 return true;
185 }
186
187 return false;
188}
189
190namespace {
191/// ReduceCrashingFunctions reducer - This works by removing functions and
192/// seeing if the program still crashes. If it does, then keep the newer,
193/// smaller program.
194///
195class ReduceCrashingFunctions : public ListReducer<Function *> {
196 BugDriver &BD;
197 BugTester TestFn;
198
199public:
200 ReduceCrashingFunctions(BugDriver &bd, BugTester testFn)
201 : BD(bd), TestFn(testFn) {}
202
203 Expected<TestResult> doTest(std::vector<Function *> &Prefix,
204 std::vector<Function *> &Kept) override {
205 if (!Kept.empty() && TestFuncs(Kept))
8
←
Assuming the condition is true
→
9
←
Calling 'ReduceCrashingFunctions::TestFuncs'
→
206 return KeepSuffix;
207 if (!Prefix.empty() && TestFuncs(Prefix))
208 return KeepPrefix;
209 return NoFailure;
210 }
211
212 bool TestFuncs(std::vector<Function *> &Prefix);
213};
214}
215
216static void RemoveFunctionReferences(Module *M, const char *Name) {
217 auto *UsedVar = M->getGlobalVariable(Name, true);
218 if (!UsedVar || !UsedVar->hasInitializer())
219 return;
220 if (isa<ConstantAggregateZero>(UsedVar->getInitializer())) {
221 assert(UsedVar->use_empty())(static_cast <bool> (UsedVar->use_empty()) ? void (0
) : __assert_fail ("UsedVar->use_empty()", "llvm/tools/bugpoint/CrashDebugger.cpp"
, 221, __extension__ __PRETTY_FUNCTION__));
222 UsedVar->eraseFromParent();
223 return;
224 }
225 auto *OldUsedVal = cast<ConstantArray>(UsedVar->getInitializer());
226 std::vector<Constant *> Used;
227 for (Value *V : OldUsedVal->operand_values()) {
228 Constant *Op = cast<Constant>(V->stripPointerCasts());
229 if (!Op->isNullValue()) {
230 Used.push_back(cast<Constant>(V));
231 }
232 }
233 auto *NewValElemTy = OldUsedVal->getType()->getElementType();
234 auto *NewValTy = ArrayType::get(NewValElemTy, Used.size());
235 auto *NewUsedVal = ConstantArray::get(NewValTy, Used);
236 UsedVar->mutateType(NewUsedVal->getType()->getPointerTo());
237 UsedVar->setInitializer(NewUsedVal);
238}
239
240bool ReduceCrashingFunctions::TestFuncs(std::vector<Function *> &Funcs) {
241 // If main isn't present, claim there is no problem.
242 if (KeepMain && !is_contained(Funcs, BD.getProgram().getFunction("main")))
10
←
Assuming the condition is false
→
11
←
Taking false branch
→
243 return false;
244
245 // Clone the program to try hacking it apart...
246 ValueToValueMapTy VMap;
247 std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
248
249 // Convert list to set for fast lookup...
250 std::set<Function *> Functions;
251 for (unsigned i = 0, e = Funcs.size(); i != e; ++i) {
12
←
Assuming 'i' is equal to 'e'
→
13
←
Loop condition is false. Execution continues on line 259
→
252 Function *CMF = cast<Function>(VMap[Funcs[i]]);
253 assert(CMF && "Function not in module?!")(static_cast <bool> (CMF && "Function not in module?!"
) ? void (0) : __assert_fail ("CMF && \"Function not in module?!\""
, "llvm/tools/bugpoint/CrashDebugger.cpp", 253, __extension__
__PRETTY_FUNCTION__));
254 assert(CMF->getFunctionType() == Funcs[i]->getFunctionType() && "wrong ty")(static_cast <bool> (CMF->getFunctionType() == Funcs
[i]->getFunctionType() && "wrong ty") ? void (0) :
__assert_fail ("CMF->getFunctionType() == Funcs[i]->getFunctionType() && \"wrong ty\""
, "llvm/tools/bugpoint/CrashDebugger.cpp", 254, __extension__
__PRETTY_FUNCTION__));
255 assert(CMF->getName() == Funcs[i]->getName() && "wrong name")(static_cast <bool> (CMF->getName() == Funcs[i]->
getName() && "wrong name") ? void (0) : __assert_fail
("CMF->getName() == Funcs[i]->getName() && \"wrong name\""
, "llvm/tools/bugpoint/CrashDebugger.cpp", 255, __extension__
__PRETTY_FUNCTION__));
256 Functions.insert(CMF);
257 }
258
259 outs() << "Checking for crash with only these functions: ";
260 PrintFunctionList(Funcs);
261 outs() << ": ";
262 if (!ReplaceFuncsWithNull) {
14
←
Assuming the condition is false
→
15
←
Taking false branch
→
263 // Loop over and delete any functions which we aren't supposed to be playing
264 // with...
265 for (Function &I : *M)
266 if (!I.isDeclaration() && !Functions.count(&I))
267 DeleteFunctionBody(&I);
268 } else {
269 std::vector<GlobalValue *> ToRemove;
270 // First, remove aliases to functions we're about to purge.
271 for (GlobalAlias &Alias : M->aliases()) {
272 GlobalObject *Root = Alias.getAliaseeObject();
16
←
'Root' initialized here
→
273 Function *F = dyn_cast_or_null<Function>(Root);
17
←
Assuming null pointer is passed into cast
→
18
←
Assuming pointer value is null
→
274 if (F
18.1
'F' is null
18.1
'F' is null
) {
19
←
Taking false branch
→
275 if (Functions.count(F))
276 // We're keeping this function.
277 continue;
278 } else if (Root->isNullValue()) {
20
←
Called C++ object pointer is null
279 // This referenced a globalalias that we've already replaced,
280 // so we still need to replace this alias.
281 } else if (!F) {
282 // Not a function, therefore not something we mess with.
283 continue;
284 }
285
286 PointerType *Ty = cast<PointerType>(Alias.getType());
287 Constant *Replacement = ConstantPointerNull::get(Ty);
288 Alias.replaceAllUsesWith(Replacement);
289 ToRemove.push_back(&Alias);
290 }
291
292 for (Function &I : *M) {
293 if (!I.isDeclaration() && !Functions.count(&I)) {
294 PointerType *Ty = cast<PointerType>(I.getType());
295 Constant *Replacement = ConstantPointerNull::get(Ty);
296 I.replaceAllUsesWith(Replacement);
297 ToRemove.push_back(&I);
298 }
299 }
300
301 for (auto *F : ToRemove) {
302 F->eraseFromParent();
303 }
304
305 // Finally, remove any null members from any global intrinsic.
306 RemoveFunctionReferences(M.get(), "llvm.used");
307 RemoveFunctionReferences(M.get(), "llvm.compiler.used");
308 }
309 // Try running the hacked up program...
310 if (TestFn(BD, M.get())) {
311 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
312
313 // Make sure to use function pointers that point into the now-current
314 // module.
315 Funcs.assign(Functions.begin(), Functions.end());
316 return true;
317 }
318 return false;
319}
320
321namespace {
322/// ReduceCrashingFunctionAttributes reducer - This works by removing
323/// attributes on a particular function and seeing if the program still crashes.
324/// If it does, then keep the newer, smaller program.
325///
326class ReduceCrashingFunctionAttributes : public ListReducer<Attribute> {
327 BugDriver &BD;
328 std::string FnName;
329 BugTester TestFn;
330
331public:
332 ReduceCrashingFunctionAttributes(BugDriver &bd, const std::string &FnName,
333 BugTester testFn)
334 : BD(bd), FnName(FnName), TestFn(testFn) {}
335
336 Expected<TestResult> doTest(std::vector<Attribute> &Prefix,
337 std::vector<Attribute> &Kept) override {
338 if (!Kept.empty() && TestFuncAttrs(Kept))
339 return KeepSuffix;
340 if (!Prefix.empty() && TestFuncAttrs(Prefix))
341 return KeepPrefix;
342 return NoFailure;
343 }
344
345 bool TestFuncAttrs(std::vector<Attribute> &Attrs);
346};
347}
348
349bool ReduceCrashingFunctionAttributes::TestFuncAttrs(
350 std::vector<Attribute> &Attrs) {
351 // Clone the program to try hacking it apart...
352 std::unique_ptr<Module> M = CloneModule(BD.getProgram());
353 Function *F = M->getFunction(FnName);
354
355 // Build up an AttributeList from the attributes we've been given by the
356 // reducer.
357 AttrBuilder AB(M->getContext());
358 for (auto A : Attrs)
359 AB.addAttribute(A);
360 AttributeList NewAttrs;
361 NewAttrs = NewAttrs.addFnAttributes(BD.getContext(), AB);
362
363 // Set this new list of attributes on the function.
364 F->setAttributes(NewAttrs);
365
366 // If the attribute list includes "optnone" we need to make sure it also
367 // includes "noinline" otherwise we will get a verifier failure.
368 if (F->hasFnAttribute(Attribute::OptimizeNone))
369 F->addFnAttr(Attribute::NoInline);
370
371 // Try running on the hacked up program...
372 if (TestFn(BD, M.get())) {
373 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
374
375 // Pass along the set of attributes that caused the crash.
376 Attrs.clear();
377 for (Attribute A : NewAttrs.getFnAttrs()) {
378 Attrs.push_back(A);
379 }
380 return true;
381 }
382 return false;
383}
384
385namespace {
386/// Simplify the CFG without completely destroying it.
387/// This is not well defined, but basically comes down to "try to eliminate
388/// unreachable blocks and constant fold terminators without deciding that
389/// certain undefined behavior cuts off the program at the legs".
390void simpleSimplifyCfg(Function &F, SmallVectorImpl<BasicBlock *> &BBs) {
391 if (F.empty())
392 return;
393
394 for (auto *BB : BBs) {
395 ConstantFoldTerminator(BB);
396 MergeBlockIntoPredecessor(BB);
397 }
398
399 // Remove unreachable blocks
400 // removeUnreachableBlocks can't be used here, it will turn various
401 // undefined behavior into unreachables, but bugpoint was the thing that
402 // generated the undefined behavior, and we don't want it to kill the entire
403 // program.
404 SmallPtrSet<BasicBlock *, 16> Visited;
405 for (auto *BB : depth_first(&F.getEntryBlock()))
406 Visited.insert(BB);
407
408 SmallVector<BasicBlock *, 16> Unreachable;
409 for (auto &BB : F)
410 if (!Visited.count(&BB))
411 Unreachable.push_back(&BB);
412
413 // The dead BB's may be in a dead cycle or otherwise have references to each
414 // other. Because of this, we have to drop all references first, then delete
415 // them all at once.
416 for (auto *BB : Unreachable) {
417 for (BasicBlock *Successor : successors(&*BB))
418 if (Visited.count(Successor))
419 Successor->removePredecessor(&*BB);
420 BB->dropAllReferences();
421 }
422 for (auto *BB : Unreachable)
423 BB->eraseFromParent();
424}
425/// ReduceCrashingBlocks reducer - This works by setting the terminators of
426/// all terminators except the specified basic blocks to a 'ret' instruction,
427/// then running the simplifycfg pass. This has the effect of chopping up
428/// the CFG really fast which can reduce large functions quickly.
429///
430class ReduceCrashingBlocks : public ListReducer<const BasicBlock *> {
431 BugDriver &BD;
432 BugTester TestFn;
433
434public:
435 ReduceCrashingBlocks(BugDriver &BD, BugTester testFn)
436 : BD(BD), TestFn(testFn) {}
437
438 Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
439 std::vector<const BasicBlock *> &Kept) override {
440 if (!Kept.empty() && TestBlocks(Kept))
441 return KeepSuffix;
442 if (!Prefix.empty() && TestBlocks(Prefix))
443 return KeepPrefix;
444 return NoFailure;
445 }
446
447 bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
448};
449}
450
451bool ReduceCrashingBlocks::TestBlocks(std::vector<const BasicBlock *> &BBs) {
452 // Clone the program to try hacking it apart...
453 ValueToValueMapTy VMap;
454 std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
455
456 // Convert list to set for fast lookup...
457 SmallPtrSet<BasicBlock *, 8> Blocks;
458 for (unsigned i = 0, e = BBs.size(); i != e; ++i)
459 Blocks.insert(cast<BasicBlock>(VMap[BBs[i]]));
460
461 outs() << "Checking for crash with only these blocks:";
462 unsigned NumPrint = Blocks.size();
463 if (NumPrint > 10)
464 NumPrint = 10;
465 for (unsigned i = 0, e = NumPrint; i != e; ++i)
466 outs() << " " << BBs[i]->getName();
467 if (NumPrint < Blocks.size())
468 outs() << "... <" << Blocks.size() << " total>";
469 outs() << ": ";
470
471 // Loop over and delete any hack up any blocks that are not listed...
472 for (Function &F : M->functions()) {
473 for (BasicBlock &BB : F) {
474 if (!Blocks.count(&BB) && BB.getTerminator()->getNumSuccessors()) {
475 // Loop over all of the successors of this block, deleting any PHI nodes
476 // that might include it.
477 for (BasicBlock *Succ : successors(&BB))
478 Succ->removePredecessor(&BB);
479
480 Instruction *BBTerm = BB.getTerminator();
481 if (BBTerm->isEHPad() || BBTerm->getType()->isTokenTy())
482 continue;
483 if (!BBTerm->getType()->isVoidTy())
484 BBTerm->replaceAllUsesWith(Constant::getNullValue(BBTerm->getType()));
485
486 // Replace the old terminator instruction.
487 BB.getInstList().pop_back();
488 new UnreachableInst(BB.getContext(), &BB);
489 }
490 }
491 }
492
493 // The CFG Simplifier pass may delete one of the basic blocks we are
494 // interested in. If it does we need to take the block out of the list. Make
495 // a "persistent mapping" by turning basic blocks into <function, name> pairs.
496 // This won't work well if blocks are unnamed, but that is just the risk we
497 // have to take. FIXME: Can we just name the blocks?
498 std::vector<std::pair<std::string, std::string>> BlockInfo;
499
500 for (BasicBlock *BB : Blocks)
501 BlockInfo.emplace_back(std::string(BB->getParent()->getName()),
502 std::string(BB->getName()));
503
504 SmallVector<BasicBlock *, 16> ToProcess;
505 for (auto &F : *M) {
506 for (auto &BB : F)
507 if (!Blocks.count(&BB))
508 ToProcess.push_back(&BB);
509 simpleSimplifyCfg(F, ToProcess);
510 ToProcess.clear();
511 }
512 // Verify we didn't break anything
513 std::vector<std::string> Passes;
514 Passes.push_back("verify");
515 std::unique_ptr<Module> New = BD.runPassesOn(M.get(), Passes);
516 if (!New) {
517 errs() << "verify failed!\n";
518 exit(1);
519 }
520 M = std::move(New);
521
522 // Try running on the hacked up program...
523 if (TestFn(BD, M.get())) {
524 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
525
526 // Make sure to use basic block pointers that point into the now-current
527 // module, and that they don't include any deleted blocks.
528 BBs.clear();
529 const ValueSymbolTable &GST = BD.getProgram().getValueSymbolTable();
530 for (const auto &BI : BlockInfo) {
531 Function *F = cast<Function>(GST.lookup(BI.first));
532 Value *V = F->getValueSymbolTable()->lookup(BI.second);
533 if (V && V->getType() == Type::getLabelTy(V->getContext()))
534 BBs.push_back(cast<BasicBlock>(V));
535 }
536 return true;
537 }
538 // It didn't crash, try something else.
539 return false;
540}
541
542namespace {
543/// ReduceCrashingConditionals reducer - This works by changing
544/// conditional branches to unconditional ones, then simplifying the CFG
545/// This has the effect of chopping up the CFG really fast which can reduce
546/// large functions quickly.
547///
548class ReduceCrashingConditionals : public ListReducer<const BasicBlock *> {
549 BugDriver &BD;
550 BugTester TestFn;
551 bool Direction;
552
553public:
554 ReduceCrashingConditionals(BugDriver &bd, BugTester testFn, bool Direction)
555 : BD(bd), TestFn(testFn), Direction(Direction) {}
556
557 Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
558 std::vector<const BasicBlock *> &Kept) override {
559 if (!Kept.empty() && TestBlocks(Kept))
560 return KeepSuffix;
561 if (!Prefix.empty() && TestBlocks(Prefix))
562 return KeepPrefix;
563 return NoFailure;
564 }
565
566 bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
567};
568}
569
570bool ReduceCrashingConditionals::TestBlocks(
571 std::vector<const BasicBlock *> &BBs) {
572 // Clone the program to try hacking it apart...
573 ValueToValueMapTy VMap;
574 std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
575
576 // Convert list to set for fast lookup...
577 SmallPtrSet<const BasicBlock *, 8> Blocks;
578 for (const auto *BB : BBs)
579 Blocks.insert(cast<BasicBlock>(VMap[BB]));
580
581 outs() << "Checking for crash with changing conditionals to always jump to "
582 << (Direction ? "true" : "false") << ":";
583 unsigned NumPrint = Blocks.size();
584 if (NumPrint > 10)
585 NumPrint = 10;
586 for (unsigned i = 0, e = NumPrint; i != e; ++i)
587 outs() << " " << BBs[i]->getName();
588 if (NumPrint < Blocks.size())
589 outs() << "... <" << Blocks.size() << " total>";
590 outs() << ": ";
591
592 // Loop over and delete any hack up any blocks that are not listed...
593 for (auto &F : *M)
594 for (auto &BB : F)
595 if (!Blocks.count(&BB)) {
596 auto *BR = dyn_cast<BranchInst>(BB.getTerminator());
597 if (!BR || !BR->isConditional())
598 continue;
599 if (Direction)
600 BR->setCondition(ConstantInt::getTrue(BR->getContext()));
601 else
602 BR->setCondition(ConstantInt::getFalse(BR->getContext()));
603 }
604
605 // The following may destroy some blocks, so we save them first
606 std::vector<std::pair<std::string, std::string>> BlockInfo;
607
608 for (const BasicBlock *BB : Blocks)
609 BlockInfo.emplace_back(std::string(BB->getParent()->getName()),
610 std::string(BB->getName()));
611
612 SmallVector<BasicBlock *, 16> ToProcess;
613 for (auto &F : *M) {
614 for (auto &BB : F)
615 if (!Blocks.count(&BB))
616 ToProcess.push_back(&BB);
617 simpleSimplifyCfg(F, ToProcess);
618 ToProcess.clear();
619 }
620 // Verify we didn't break anything
621 std::vector<std::string> Passes;
622 Passes.push_back("verify");
623 std::unique_ptr<Module> New = BD.runPassesOn(M.get(), Passes);
624 if (!New) {
625 errs() << "verify failed!\n";
626 exit(1);
627 }
628 M = std::move(New);
629
630 // Try running on the hacked up program...
631 if (TestFn(BD, M.get())) {
632 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
633
634 // Make sure to use basic block pointers that point into the now-current
635 // module, and that they don't include any deleted blocks.
636 BBs.clear();
637 const ValueSymbolTable &GST = BD.getProgram().getValueSymbolTable();
638 for (auto &BI : BlockInfo) {
639 auto *F = cast<Function>(GST.lookup(BI.first));
640 Value *V = F->getValueSymbolTable()->lookup(BI.second);
641 if (V && V->getType() == Type::getLabelTy(V->getContext()))
642 BBs.push_back(cast<BasicBlock>(V));
643 }
644 return true;
645 }
646 // It didn't crash, try something else.
647 return false;
648}
649
650namespace {
651/// SimplifyCFG reducer - This works by calling SimplifyCFG on each basic block
652/// in the program.
653
654class ReduceSimplifyCFG : public ListReducer<const BasicBlock *> {
655 BugDriver &BD;
656 BugTester TestFn;
657 TargetTransformInfo TTI;
658
659public:
660 ReduceSimplifyCFG(BugDriver &bd, BugTester testFn)
661 : BD(bd), TestFn(testFn), TTI(bd.getProgram().getDataLayout()) {}
662
663 Expected<TestResult> doTest(std::vector<const BasicBlock *> &Prefix,
664 std::vector<const BasicBlock *> &Kept) override {
665 if (!Kept.empty() && TestBlocks(Kept))
666 return KeepSuffix;
667 if (!Prefix.empty() && TestBlocks(Prefix))
668 return KeepPrefix;
669 return NoFailure;
670 }
671
672 bool TestBlocks(std::vector<const BasicBlock *> &Prefix);
673};
674}
675
676bool ReduceSimplifyCFG::TestBlocks(std::vector<const BasicBlock *> &BBs) {
677 // Clone the program to try hacking it apart...
678 ValueToValueMapTy VMap;
679 std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
680
681 // Convert list to set for fast lookup...
682 SmallPtrSet<const BasicBlock *, 8> Blocks;
683 for (const auto *BB : BBs)
684 Blocks.insert(cast<BasicBlock>(VMap[BB]));
685
686 outs() << "Checking for crash with CFG simplifying:";
687 unsigned NumPrint = Blocks.size();
688 if (NumPrint > 10)
689 NumPrint = 10;
690 for (unsigned i = 0, e = NumPrint; i != e; ++i)
691 outs() << " " << BBs[i]->getName();
692 if (NumPrint < Blocks.size())
693 outs() << "... <" << Blocks.size() << " total>";
694 outs() << ": ";
695
696 // The following may destroy some blocks, so we save them first
697 std::vector<std::pair<std::string, std::string>> BlockInfo;
698
699 for (const BasicBlock *BB : Blocks)
700 BlockInfo.emplace_back(std::string(BB->getParent()->getName()),
701 std::string(BB->getName()));
702
703 // Loop over and delete any hack up any blocks that are not listed...
704 for (auto &F : *M)
705 // Loop over all of the basic blocks and remove them if they are unneeded.
706 for (Function::iterator BBIt = F.begin(); BBIt != F.end();) {
707 if (!Blocks.count(&*BBIt)) {
708 ++BBIt;
709 continue;
710 }
711 simplifyCFG(&*BBIt++, TTI);
712 }
713 // Verify we didn't break anything
714 std::vector<std::string> Passes;
715 Passes.push_back("verify");
716 std::unique_ptr<Module> New = BD.runPassesOn(M.get(), Passes);
717 if (!New) {
718 errs() << "verify failed!\n";
719 exit(1);
720 }
721 M = std::move(New);
722
723 // Try running on the hacked up program...
724 if (TestFn(BD, M.get())) {
725 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
726
727 // Make sure to use basic block pointers that point into the now-current
728 // module, and that they don't include any deleted blocks.
729 BBs.clear();
730 const ValueSymbolTable &GST = BD.getProgram().getValueSymbolTable();
731 for (auto &BI : BlockInfo) {
732 auto *F = cast<Function>(GST.lookup(BI.first));
733 Value *V = F->getValueSymbolTable()->lookup(BI.second);
734 if (V && V->getType() == Type::getLabelTy(V->getContext()))
735 BBs.push_back(cast<BasicBlock>(V));
736 }
737 return true;
738 }
739 // It didn't crash, try something else.
740 return false;
741}
742
743namespace {
744/// ReduceCrashingInstructions reducer - This works by removing the specified
745/// non-terminator instructions and replacing them with undef.
746///
747class ReduceCrashingInstructions : public ListReducer<const Instruction *> {
748 BugDriver &BD;
749 BugTester TestFn;
750
751public:
752 ReduceCrashingInstructions(BugDriver &bd, BugTester testFn)
753 : BD(bd), TestFn(testFn) {}
754
755 Expected<TestResult> doTest(std::vector<const Instruction *> &Prefix,
756 std::vector<const Instruction *> &Kept) override {
757 if (!Kept.empty() && TestInsts(Kept))
758 return KeepSuffix;
759 if (!Prefix.empty() && TestInsts(Prefix))
760 return KeepPrefix;
761 return NoFailure;
762 }
763
764 bool TestInsts(std::vector<const Instruction *> &Prefix);
765};
766}
767
768bool ReduceCrashingInstructions::TestInsts(
769 std::vector<const Instruction *> &Insts) {
770 // Clone the program to try hacking it apart...
771 ValueToValueMapTy VMap;
772 std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
773
774 // Convert list to set for fast lookup...
775 SmallPtrSet<Instruction *, 32> Instructions;
776 for (unsigned i = 0, e = Insts.size(); i != e; ++i) {
777 assert(!Insts[i]->isTerminator())(static_cast <bool> (!Insts[i]->isTerminator()) ? void
(0) : __assert_fail ("!Insts[i]->isTerminator()", "llvm/tools/bugpoint/CrashDebugger.cpp"
, 777, __extension__ __PRETTY_FUNCTION__));
778 Instructions.insert(cast<Instruction>(VMap[Insts[i]]));
779 }
780
781 outs() << "Checking for crash with only " << Instructions.size();
782 if (Instructions.size() == 1)
783 outs() << " instruction: ";
784 else
785 outs() << " instructions: ";
786
787 for (Module::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI)
788 for (Function::iterator FI = MI->begin(), FE = MI->end(); FI != FE; ++FI)
789 for (Instruction &Inst : llvm::make_early_inc_range(*FI)) {
790 if (!Instructions.count(&Inst) && !Inst.isTerminator() &&
791 !Inst.isEHPad() && !Inst.getType()->isTokenTy() &&
792 !Inst.isSwiftError()) {
793 if (!Inst.getType()->isVoidTy())
794 Inst.replaceAllUsesWith(UndefValue::get(Inst.getType()));
795 Inst.eraseFromParent();
796 }
797 }
798
799 // Verify that this is still valid.
800 legacy::PassManager Passes;
801 Passes.add(createVerifierPass(/*FatalErrors=*/false));
802 Passes.run(*M);
803
804 // Try running on the hacked up program...
805 if (TestFn(BD, M.get())) {
806 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
807
808 // Make sure to use instruction pointers that point into the now-current
809 // module, and that they don't include any deleted blocks.
810 Insts.clear();
811 for (Instruction *Inst : Instructions)
812 Insts.push_back(Inst);
813 return true;
814 }
815 // It didn't crash, try something else.
816 return false;
817}
818
819namespace {
820/// ReduceCrashingMetadata reducer - This works by removing all metadata from
821/// the specified instructions.
822///
823class ReduceCrashingMetadata : public ListReducer<Instruction *> {
824 BugDriver &BD;
825 BugTester TestFn;
826
827public:
828 ReduceCrashingMetadata(BugDriver &bd, BugTester testFn)
829 : BD(bd), TestFn(testFn) {}
830
831 Expected<TestResult> doTest(std::vector<Instruction *> &Prefix,
832 std::vector<Instruction *> &Kept) override {
833 if (!Kept.empty() && TestInsts(Kept))
834 return KeepSuffix;
835 if (!Prefix.empty() && TestInsts(Prefix))
836 return KeepPrefix;
837 return NoFailure;
838 }
839
840 bool TestInsts(std::vector<Instruction *> &Prefix);
841};
842} // namespace
843
844bool ReduceCrashingMetadata::TestInsts(std::vector<Instruction *> &Insts) {
845 // Clone the program to try hacking it apart...
846 ValueToValueMapTy VMap;
847 std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
848
849 // Convert list to set for fast lookup...
850 SmallPtrSet<Instruction *, 32> Instructions;
851 for (Instruction *I : Insts)
852 Instructions.insert(cast<Instruction>(VMap[I]));
853
854 outs() << "Checking for crash with metadata retained from "
855 << Instructions.size();
856 if (Instructions.size() == 1)
857 outs() << " instruction: ";
858 else
859 outs() << " instructions: ";
860
861 // Try to drop instruction metadata from all instructions, except the ones
862 // selected in Instructions.
863 for (Function &F : *M)
864 for (Instruction &Inst : instructions(F)) {
865 if (!Instructions.count(&Inst)) {
866 Inst.dropUnknownNonDebugMetadata();
867 Inst.setDebugLoc({});
868 }
869 }
870
871 // Verify that this is still valid.
872 legacy::PassManager Passes;
873 Passes.add(createVerifierPass(/*FatalErrors=*/false));
874 Passes.run(*M);
875
876 // Try running on the hacked up program...
877 if (TestFn(BD, M.get())) {
878 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
879
880 // Make sure to use instruction pointers that point into the now-current
881 // module, and that they don't include any deleted blocks.
882 Insts.clear();
883 for (Instruction *I : Instructions)
884 Insts.push_back(I);
885 return true;
886 }
887 // It didn't crash, try something else.
888 return false;
889}
890
891namespace {
892// Reduce the list of Named Metadata nodes. We keep this as a list of
893// names to avoid having to convert back and forth every time.
894class ReduceCrashingNamedMD : public ListReducer<std::string> {
895 BugDriver &BD;
896 BugTester TestFn;
897
898public:
899 ReduceCrashingNamedMD(BugDriver &bd, BugTester testFn)
900 : BD(bd), TestFn(testFn) {}
901
902 Expected<TestResult> doTest(std::vector<std::string> &Prefix,
903 std::vector<std::string> &Kept) override {
904 if (!Kept.empty() && TestNamedMDs(Kept))
905 return KeepSuffix;
906 if (!Prefix.empty() && TestNamedMDs(Prefix))
907 return KeepPrefix;
908 return NoFailure;
909 }
910
911 bool TestNamedMDs(std::vector<std::string> &NamedMDs);
912};
913}
914
915bool ReduceCrashingNamedMD::TestNamedMDs(std::vector<std::string> &NamedMDs) {
916
917 ValueToValueMapTy VMap;
918 std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
919
920 outs() << "Checking for crash with only these named metadata nodes:";
921 unsigned NumPrint = std::min<size_t>(NamedMDs.size(), 10);
922 for (unsigned i = 0, e = NumPrint; i != e; ++i)
923 outs() << " " << NamedMDs[i];
924 if (NumPrint < NamedMDs.size())
925 outs() << "... <" << NamedMDs.size() << " total>";
926 outs() << ": ";
927
928 // Make a StringMap for faster lookup
929 StringSet<> Names;
930 for (const std::string &Name : NamedMDs)
931 Names.insert(Name);
932
933 // First collect all the metadata to delete in a vector, then
934 // delete them all at once to avoid invalidating the iterator
935 std::vector<NamedMDNode *> ToDelete;
936 ToDelete.reserve(M->named_metadata_size() - Names.size());
937 for (auto &NamedMD : M->named_metadata())
938 // Always keep a nonempty llvm.dbg.cu because the Verifier would complain.
939 if (!Names.count(NamedMD.getName()) &&
940 (!(NamedMD.getName() == "llvm.dbg.cu" && NamedMD.getNumOperands() > 0)))
941 ToDelete.push_back(&NamedMD);
942
943 for (auto *NamedMD : ToDelete)
944 NamedMD->eraseFromParent();
945
946 // Verify that this is still valid.
947 legacy::PassManager Passes;
948 Passes.add(createVerifierPass(/*FatalErrors=*/false));
949 Passes.run(*M);
950
951 // Try running on the hacked up program...
952 if (TestFn(BD, M.get())) {
953 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
954 return true;
955 }
956 return false;
957}
958
959namespace {
960// Reduce the list of operands to named metadata nodes
961class ReduceCrashingNamedMDOps : public ListReducer<const MDNode *> {
962 BugDriver &BD;
963 BugTester TestFn;
964
965public:
966 ReduceCrashingNamedMDOps(BugDriver &bd, BugTester testFn)
967 : BD(bd), TestFn(testFn) {}
968
969 Expected<TestResult> doTest(std::vector<const MDNode *> &Prefix,
970 std::vector<const MDNode *> &Kept) override {
971 if (!Kept.empty() && TestNamedMDOps(Kept))
972 return KeepSuffix;
973 if (!Prefix.empty() && TestNamedMDOps(Prefix))
974 return KeepPrefix;
975 return NoFailure;
976 }
977
978 bool TestNamedMDOps(std::vector<const MDNode *> &NamedMDOps);
979};
980}
981
982bool ReduceCrashingNamedMDOps::TestNamedMDOps(
983 std::vector<const MDNode *> &NamedMDOps) {
984 // Convert list to set for fast lookup...
985 SmallPtrSet<const MDNode *, 32> OldMDNodeOps;
986 for (unsigned i = 0, e = NamedMDOps.size(); i != e; ++i) {
987 OldMDNodeOps.insert(NamedMDOps[i]);
988 }
989
990 outs() << "Checking for crash with only " << OldMDNodeOps.size();
991 if (OldMDNodeOps.size() == 1)
992 outs() << " named metadata operand: ";
993 else
994 outs() << " named metadata operands: ";
995
996 ValueToValueMapTy VMap;
997 std::unique_ptr<Module> M = CloneModule(BD.getProgram(), VMap);
998
999 // This is a little wasteful. In the future it might be good if we could have
1000 // these dropped during cloning.
1001 for (auto &NamedMD : BD.getProgram().named_metadata()) {
1002 // Drop the old one and create a new one
1003 M->eraseNamedMetadata(M->getNamedMetadata(NamedMD.getName()));
1004 NamedMDNode *NewNamedMDNode =
1005 M->getOrInsertNamedMetadata(NamedMD.getName());
1006 for (MDNode *op : NamedMD.operands())
1007 if (OldMDNodeOps.count(op))
1008 NewNamedMDNode->addOperand(cast<MDNode>(MapMetadata(op, VMap)));
1009 }
1010
1011 // Verify that this is still valid.
1012 legacy::PassManager Passes;
1013 Passes.add(createVerifierPass(/*FatalErrors=*/false));
1014 Passes.run(*M);
1015
1016 // Try running on the hacked up program...
1017 if (TestFn(BD, M.get())) {
1018 // Make sure to use instruction pointers that point into the now-current
1019 // module, and that they don't include any deleted blocks.
1020 NamedMDOps.clear();
1021 for (const MDNode *Node : OldMDNodeOps)
1022 NamedMDOps.push_back(cast<MDNode>(*VMap.getMappedMD(Node)));
1023
1024 BD.setNewProgram(std::move(M)); // It crashed, keep the trimmed version...
1025 return true;
1026 }
1027 // It didn't crash, try something else.
1028 return false;
1029}
1030
1031/// Attempt to eliminate as many global initializers as possible.
1032static Error ReduceGlobalInitializers(BugDriver &BD, BugTester TestFn) {
1033 Module &OrigM = BD.getProgram();
1034 if (OrigM.global_empty())
1035 return Error::success();
1036
1037 // Now try to reduce the number of global variable initializers in the
1038 // module to something small.
1039 std::unique_ptr<Module> M = CloneModule(OrigM);
1040 bool DeletedInit = false;
1041
1042 for (GlobalVariable &GV : M->globals()) {
1043 if (GV.hasInitializer()) {
1044 DeleteGlobalInitializer(&GV);
1045 GV.setLinkage(GlobalValue::ExternalLinkage);
1046 GV.setComdat(nullptr);
1047 DeletedInit = true;
1048 }
1049 }
1050
1051 if (!DeletedInit)
1052 return Error::success();
1053
1054 // See if the program still causes a crash...
1055 outs() << "\nChecking to see if we can delete global inits: ";
1056
1057 if (TestFn(BD, M.get())) { // Still crashes?
1058 BD.setNewProgram(std::move(M));
1059 outs() << "\n*** Able to remove all global initializers!\n";
1060 return Error::success();
1061 }
1062
1063 // No longer crashes.
1064 outs() << " - Removing all global inits hides problem!\n";
1065
1066 std::vector<GlobalVariable *> GVs;
1067 for (GlobalVariable &GV : OrigM.globals())
1068 if (GV.hasInitializer())
1069 GVs.push_back(&GV);
1070
1071 if (GVs.size() > 1 && !BugpointIsInterrupted) {
1072 outs() << "\n*** Attempting to reduce the number of global initializers "
1073 << "in the testcase\n";
1074
1075 unsigned OldSize = GVs.size();
1076 Expected<bool> Result =
1077 ReduceCrashingGlobalInitializers(BD, TestFn).reduceList(GVs);
1078 if (Error E = Result.takeError())
1079 return E;
1080
1081 if (GVs.size() < OldSize)
1082 BD.EmitProgressBitcode(BD.getProgram(), "reduced-global-variables");
1083 }
1084 return Error::success();
1085}
1086
1087static Error ReduceInsts(BugDriver &BD, BugTester TestFn) {
1088 // Attempt to delete instructions using bisection. This should help out nasty
1089 // cases with large basic blocks where the problem is at one end.
1090 if (!BugpointIsInterrupted) {
1091 std::vector<const Instruction *> Insts;
1092 for (const Function &F : BD.getProgram())
1093 for (const BasicBlock &BB : F)
1094 for (const Instruction &I : BB)
1095 if (!I.isTerminator())
1096 Insts.push_back(&I);
1097
1098 Expected<bool> Result =
1099 ReduceCrashingInstructions(BD, TestFn).reduceList(Insts);
1100 if (Error E = Result.takeError())
1101 return E;
1102 }
1103
1104 unsigned Simplification = 2;
1105 do {
1106 if (BugpointIsInterrupted)
1107 // TODO: Should we distinguish this with an "interrupted error"?
1108 return Error::success();
1109 --Simplification;
1110 outs() << "\n*** Attempting to reduce testcase by deleting instruc"
1111 << "tions: Simplification Level #" << Simplification << '\n';
1112
1113 // Now that we have deleted the functions that are unnecessary for the
1114 // program, try to remove instructions that are not necessary to cause the
1115 // crash. To do this, we loop through all of the instructions in the
1116 // remaining functions, deleting them (replacing any values produced with
1117 // nulls), and then running ADCE and SimplifyCFG. If the transformed input
1118 // still triggers failure, keep deleting until we cannot trigger failure
1119 // anymore.
1120 //
1121 unsigned InstructionsToSkipBeforeDeleting = 0;
1122 TryAgain:
1123
1124 // Loop over all of the (non-terminator) instructions remaining in the
1125 // function, attempting to delete them.
1126 unsigned CurInstructionNum = 0;
1127 for (Module::const_iterator FI = BD.getProgram().begin(),
1128 E = BD.getProgram().end();
1129 FI != E; ++FI)
1130 if (!FI->isDeclaration())
1131 for (Function::const_iterator BI = FI->begin(), E = FI->end(); BI != E;
1132 ++BI)
1133 for (BasicBlock::const_iterator I = BI->begin(), E = --BI->end();
1134 I != E; ++I, ++CurInstructionNum) {
1135 if (InstructionsToSkipBeforeDeleting) {
1136 --InstructionsToSkipBeforeDeleting;
1137 } else {
1138 if (BugpointIsInterrupted)
1139 // TODO: Should this be some kind of interrupted error?
1140 return Error::success();
1141
1142 if (I->isEHPad() || I->getType()->isTokenTy() ||
1143 I->isSwiftError())
1144 continue;
1145
1146 outs() << "Checking instruction: " << *I;
1147 std::unique_ptr<Module> M =
1148 BD.deleteInstructionFromProgram(&*I, Simplification);
1149
1150 // Find out if the pass still crashes on this pass...
1151 if (TestFn(BD, M.get())) {
1152 // Yup, it does, we delete the old module, and continue trying
1153 // to reduce the testcase...
1154 BD.setNewProgram(std::move(M));
1155 InstructionsToSkipBeforeDeleting = CurInstructionNum;
1156 goto TryAgain; // I wish I had a multi-level break here!
1157 }
1158 }
1159 }
1160
1161 if (InstructionsToSkipBeforeDeleting) {
1162 InstructionsToSkipBeforeDeleting = 0;
1163 goto TryAgain;
1164 }
1165
1166 } while (Simplification);
1167
1168 // Attempt to drop metadata from instructions that does not contribute to the
1169 // crash.
1170 if (!BugpointIsInterrupted) {
1171 std::vector<Instruction *> Insts;
1172 for (Function &F : BD.getProgram())
1173 for (Instruction &I : instructions(F))
1174 Insts.push_back(&I);
1175
1176 Expected<bool> Result =
1177 ReduceCrashingMetadata(BD, TestFn).reduceList(Insts);
1178 if (Error E = Result.takeError())
1179 return E;
1180 }
1181
1182 BD.EmitProgressBitcode(BD.getProgram(), "reduced-instructions");
1183 return Error::success();
1184}
1185
1186/// DebugACrash - Given a predicate that determines whether a component crashes
1187/// on a program, try to destructively reduce the program while still keeping
1188/// the predicate true.
1189static Error DebugACrash(BugDriver &BD, BugTester TestFn) {
1190 // See if we can get away with nuking some of the global variable initializers
1191 // in the program...
1192 if (!NoGlobalRM)
1
Assuming the condition is false
→
2
←
Taking false branch
→
1193 if (Error E = ReduceGlobalInitializers(BD, TestFn))
1194 return E;
1195
1196 // Now try to reduce the number of functions in the module to something small.
1197 std::vector<Function *> Functions;
1198 for (Function &F : BD.getProgram())
1199 if (!F.isDeclaration())
1200 Functions.push_back(&F);
1201
1202 if (Functions.size() > 1 && !BugpointIsInterrupted) {
3
←
Assuming the condition is true
→
4
←
Assuming 'BugpointIsInterrupted' is false
→
5
←
Taking true branch
→
1203 outs() << "\n*** Attempting to reduce the number of functions "
1204 "in the testcase\n";
1205
1206 unsigned OldSize = Functions.size();
1207 Expected<bool> Result =
1208 ReduceCrashingFunctions(BD, TestFn).reduceList(Functions);
6
←
Calling 'ListReducer::reduceList'
→
1209 if (Error E = Result.takeError())
1210 return E;
1211
1212 if (Functions.size() < OldSize)
1213 BD.EmitProgressBitcode(BD.getProgram(), "reduced-function");
1214 }
1215
1216 if (!NoAttributeRM) {
1217 // For each remaining function, try to reduce that function's attributes.
1218 std::vector<std::string> FunctionNames;
1219 for (Function &F : BD.getProgram())
1220 FunctionNames.push_back(std::string(F.getName()));
1221
1222 if (!FunctionNames.empty() && !BugpointIsInterrupted) {
1223 outs() << "\n*** Attempting to reduce the number of function attributes"
1224 " in the testcase\n";
1225
1226 unsigned OldSize = 0;
1227 unsigned NewSize = 0;
1228 for (std::string &Name : FunctionNames) {
1229 Function *Fn = BD.getProgram().getFunction(Name);
1230 assert(Fn && "Could not find function?")(static_cast <bool> (Fn && "Could not find function?"
) ? void (0) : __assert_fail ("Fn && \"Could not find function?\""
, "llvm/tools/bugpoint/CrashDebugger.cpp", 1230, __extension__
__PRETTY_FUNCTION__));
1231
1232 std::vector<Attribute> Attrs;
1233 for (Attribute A : Fn->getAttributes().getFnAttrs())
1234 Attrs.push_back(A);
1235
1236 OldSize += Attrs.size();
1237 Expected<bool> Result =
1238 ReduceCrashingFunctionAttributes(BD, Name, TestFn).reduceList(Attrs);
1239 if (Error E = Result.takeError())
1240 return E;
1241
1242 NewSize += Attrs.size();
1243 }
1244
1245 if (OldSize < NewSize)
1246 BD.EmitProgressBitcode(BD.getProgram(), "reduced-function-attributes");
1247 }
1248 }
1249
1250 // Attempt to change conditional branches into unconditional branches to
1251 // eliminate blocks.
1252 if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
1253 std::vector<const BasicBlock *> Blocks;
1254 for (Function &F : BD.getProgram())
1255 for (BasicBlock &BB : F)
1256 Blocks.push_back(&BB);
1257 unsigned OldSize = Blocks.size();
1258 Expected<bool> Result =
1259 ReduceCrashingConditionals(BD, TestFn, true).reduceList(Blocks);
1260 if (Error E = Result.takeError())
1261 return E;
1262 Result = ReduceCrashingConditionals(BD, TestFn, false).reduceList(Blocks);
1263 if (Error E = Result.takeError())
1264 return E;
1265 if (Blocks.size() < OldSize)
1266 BD.EmitProgressBitcode(BD.getProgram(), "reduced-conditionals");
1267 }
1268
1269 // Attempt to delete entire basic blocks at a time to speed up
1270 // convergence... this actually works by setting the terminator of the blocks
1271 // to a return instruction then running simplifycfg, which can potentially
1272 // shrinks the code dramatically quickly
1273 //
1274 if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
1275 std::vector<const BasicBlock *> Blocks;
1276 for (Function &F : BD.getProgram())
1277 for (BasicBlock &BB : F)
1278 Blocks.push_back(&BB);
1279 unsigned OldSize = Blocks.size();
1280 Expected<bool> Result = ReduceCrashingBlocks(BD, TestFn).reduceList(Blocks);
1281 if (Error E = Result.takeError())
1282 return E;
1283 if (Blocks.size() < OldSize)
1284 BD.EmitProgressBitcode(BD.getProgram(), "reduced-blocks");
1285 }
1286
1287 if (!DisableSimplifyCFG && !BugpointIsInterrupted) {
1288 std::vector<const BasicBlock *> Blocks;
1289 for (Function &F : BD.getProgram())
1290 for (BasicBlock &BB : F)
1291 Blocks.push_back(&BB);
1292 unsigned OldSize = Blocks.size();
1293 Expected<bool> Result = ReduceSimplifyCFG(BD, TestFn).reduceList(Blocks);
1294 if (Error E = Result.takeError())
1295 return E;
1296 if (Blocks.size() < OldSize)
1297 BD.EmitProgressBitcode(BD.getProgram(), "reduced-simplifycfg");
1298 }
1299
1300 // Attempt to delete instructions using bisection. This should help out nasty
1301 // cases with large basic blocks where the problem is at one end.
1302 if (!BugpointIsInterrupted)
1303 if (Error E = ReduceInsts(BD, TestFn))
1304 return E;
1305
1306 // Attempt to strip debug info metadata.
1307 auto stripMetadata = [&](std::function<bool(Module &)> strip) {
1308 std::unique_ptr<Module> M = CloneModule(BD.getProgram());
1309 strip(*M);
1310 if (TestFn(BD, M.get()))
1311 BD.setNewProgram(std::move(M));
1312 };
1313 if (!NoStripDebugInfo && !BugpointIsInterrupted) {
1314 outs() << "\n*** Attempting to strip the debug info: ";
1315 stripMetadata(StripDebugInfo);
1316 }
1317 if (!NoStripDebugTypeInfo && !BugpointIsInterrupted) {
1318 outs() << "\n*** Attempting to strip the debug type info: ";
1319 stripMetadata(stripNonLineTableDebugInfo);
1320 }
1321
1322 if (!NoNamedMDRM) {
1323 if (!BugpointIsInterrupted) {
1324 // Try to reduce the amount of global metadata (particularly debug info),
1325 // by dropping global named metadata that anchors them
1326 outs() << "\n*** Attempting to remove named metadata: ";
1327 std::vector<std::string> NamedMDNames;
1328 for (auto &NamedMD : BD.getProgram().named_metadata())
1329 NamedMDNames.push_back(NamedMD.getName().str());
1330 Expected<bool> Result =
1331 ReduceCrashingNamedMD(BD, TestFn).reduceList(NamedMDNames);
1332 if (Error E = Result.takeError())
1333 return E;
1334 }
1335
1336 if (!BugpointIsInterrupted) {
1337 // Now that we quickly dropped all the named metadata that doesn't
1338 // contribute to the crash, bisect the operands of the remaining ones
1339 std::vector<const MDNode *> NamedMDOps;
1340 for (auto &NamedMD : BD.getProgram().named_metadata())
1341 for (auto op : NamedMD.operands())
1342 NamedMDOps.push_back(op);
1343 Expected<bool> Result =
1344 ReduceCrashingNamedMDOps(BD, TestFn).reduceList(NamedMDOps);
1345 if (Error E = Result.takeError())
1346 return E;
1347 }
1348 BD.EmitProgressBitcode(BD.getProgram(), "reduced-named-md");
1349 }
1350
1351 // Try to clean up the testcase by running funcresolve and globaldce...
1352 if (!BugpointIsInterrupted) {
1353 outs() << "\n*** Attempting to perform final cleanups: ";
1354 std::unique_ptr<Module> M = CloneModule(BD.getProgram());
1355 M = BD.performFinalCleanups(std::move(M), true);
1356
1357 // Find out if the pass still crashes on the cleaned up program...
1358 if (M && TestFn(BD, M.get()))
1359 BD.setNewProgram(
1360 std::move(M)); // Yup, it does, keep the reduced version...
1361 }
1362
1363 BD.EmitProgressBitcode(BD.getProgram(), "reduced-simplified");
1364
1365 return Error::success();
1366}
1367
1368static bool TestForOptimizerCrash(const BugDriver &BD, Module *M) {
1369 return BD.runPasses(*M, BD.getPassesToRun());
1370}
1371
1372/// debugOptimizerCrash - This method is called when some pass crashes on input.
1373/// It attempts to prune down the testcase to something reasonable, and figure
1374/// out exactly which pass is crashing.
1375///
1376Error BugDriver::debugOptimizerCrash(const std::string &ID) {
1377 outs() << "\n*** Debugging optimizer crash!\n";
1378
1379 // Reduce the list of passes which causes the optimizer to crash...
1380 if (!BugpointIsInterrupted && !DontReducePassList) {
1381 Expected<bool> Result = ReducePassList(*this).reduceList(PassesToRun);
1382 if (Error E = Result.takeError())
1383 return E;
1384 }
1385
1386 outs() << "\n*** Found crashing pass"
1387 << (PassesToRun.size() == 1 ? ": " : "es: ")
1388 << getPassesString(PassesToRun) << '\n';
1389
1390 EmitProgressBitcode(*Program, ID);
1391
1392 auto Res = DebugACrash(*this, TestForOptimizerCrash);
1393 if (Res || DontReducePassList)
1394 return Res;
1395 // Try to reduce the pass list again. This covers additional cases
1396 // we failed to reduce earlier, because of more complex pass dependencies
1397 // triggering the crash.
1398 auto SecondRes = ReducePassList(*this).reduceList(PassesToRun);
1399 if (Error E = SecondRes.takeError())
1400 return E;
1401 outs() << "\n*** Found crashing pass"
1402 << (PassesToRun.size() == 1 ? ": " : "es: ")
1403 << getPassesString(PassesToRun) << '\n';
1404
1405 EmitProgressBitcode(getProgram(), "reduced-simplified");
1406 return Res;
1407}
1408
1409static bool TestForCodeGenCrash(const BugDriver &BD, Module *M) {
1410 if (Error E = BD.compileProgram(*M)) {
1411 if (VerboseErrors)
1412 errs() << toString(std::move(E)) << "\n";
1413 else {
1414 consumeError(std::move(E));
1415 errs() << "<crash>\n";
1416 }
1417 return true; // Tool is still crashing.
1418 }
1419 errs() << '\n';
1420 return false;
1421}
1422
1423/// debugCodeGeneratorCrash - This method is called when the code generator
1424/// crashes on an input. It attempts to reduce the input as much as possible
1425/// while still causing the code generator to crash.
1426Error BugDriver::debugCodeGeneratorCrash() {
1427 errs() << "*** Debugging code generator crash!\n";
1428
1429 return DebugACrash(*this, TestForCodeGenCrash);
1430}
←

/build/llvm-toolchain-snapshot-15~++20220406101104+1235aaefbd4f/llvm/tools/bugpoint/ListReducer.h

1//===- ListReducer.h - Trim down list while retaining property --*- C++ -*-===//
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 class is to be used as a base class for operations that want to zero in
10// on a subset of the input which still causes the bug we are tracking.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_TOOLS_BUGPOINT_LISTREDUCER_H
15#define LLVM_TOOLS_BUGPOINT_LISTREDUCER_H
16
17#include "llvm/Support/Error.h"
18#include "llvm/Support/raw_ostream.h"
19#include <algorithm>
20#include <cstdlib>
21#include <random>
22#include <vector>
23
24namespace llvm {
25
26extern bool BugpointIsInterrupted;
27
28template <typename ElTy> struct ListReducer {
29 enum TestResult {
30 NoFailure, // No failure of the predicate was detected
31 KeepSuffix, // The suffix alone satisfies the predicate
32 KeepPrefix // The prefix alone satisfies the predicate
33 };
34
35 virtual ~ListReducer() {}
36
37 /// This virtual function should be overriden by subclasses to implement the
38 /// test desired. The testcase is only required to test to see if the Kept
39 /// list still satisfies the property, but if it is going to check the prefix
40 /// anyway, it can.
41 virtual Expected<TestResult> doTest(std::vector<ElTy> &Prefix,
42 std::vector<ElTy> &Kept) = 0;
43
44 /// This function attempts to reduce the length of the specified list while
45 /// still maintaining the "test" property. This is the core of the "work"
46 /// that bugpoint does.
47 Expected<bool> reduceList(std::vector<ElTy> &TheList) {
48 std::vector<ElTy> empty;
49 std::mt19937 randomness(0x6e5ea738); // Seed the random number generator
50 Expected<TestResult> Result = doTest(TheList, empty);
7
←
Calling 'ReduceCrashingFunctions::doTest'
→
51 if (Error E = Result.takeError())
52 return std::move(E);
53 switch (*Result) {
54 case KeepPrefix:
55 if (TheList.size() == 1) // we are done, it's the base case and it fails
56 return true;
57 else
58 break; // there's definitely an error, but we need to narrow it down
59
60 case KeepSuffix:
61 // cannot be reached!
62 llvm_unreachable("bugpoint ListReducer internal error: "::llvm::llvm_unreachable_internal("bugpoint ListReducer internal error: "
"selected empty set.", "llvm/tools/bugpoint/ListReducer.h", 63
)
63 "selected empty set.")::llvm::llvm_unreachable_internal("bugpoint ListReducer internal error: "
"selected empty set.", "llvm/tools/bugpoint/ListReducer.h", 63
);
64
65 case NoFailure:
66 return false; // there is no failure with the full set of passes/funcs!
67 }
68
69 // Maximal number of allowed splitting iterations,
70 // before the elements are randomly shuffled.
71 const unsigned MaxIterationsWithoutProgress = 3;
72
73 // Maximal number of allowed single-element trim iterations. We add a
74 // threshold here as single-element reductions may otherwise take a
75 // very long time to complete.
76 const unsigned MaxTrimIterationsWithoutBackJump = 3;
77 bool ShufflingEnabled = true;
78
79 Backjump:
80 unsigned MidTop = TheList.size();
81 unsigned MaxIterations = MaxIterationsWithoutProgress;
82 unsigned NumOfIterationsWithoutProgress = 0;
83 while (MidTop > 1) { // Binary split reduction loop
84 // Halt if the user presses ctrl-c.
85 if (BugpointIsInterrupted) {
86 errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
87 return true;
88 }
89
90 // If the loop doesn't make satisfying progress, try shuffling.
91 // The purpose of shuffling is to avoid the heavy tails of the
92 // distribution (improving the speed of convergence).
93 if (ShufflingEnabled && NumOfIterationsWithoutProgress > MaxIterations) {
94 std::vector<ElTy> ShuffledList(TheList);
95 llvm::shuffle(ShuffledList.begin(), ShuffledList.end(), randomness);
96 errs() << "\n\n*** Testing shuffled set...\n\n";
97 // Check that random shuffle doesn't lose the bug
98 Expected<TestResult> Result = doTest(ShuffledList, empty);
99 // TODO: Previously, this error was ignored and we treated it as if
100 // shuffling hid the bug. This should really either be consumeError if
101 // that behaviour was sensible, or we should propagate the error.
102 assert(!Result.takeError() && "Shuffling caused internal error?")(static_cast <bool> (!Result.takeError() && "Shuffling caused internal error?"
) ? void (0) : __assert_fail ("!Result.takeError() && \"Shuffling caused internal error?\""
, "llvm/tools/bugpoint/ListReducer.h", 102, __extension__ __PRETTY_FUNCTION__
));
103
104 if (*Result == KeepPrefix) {
105 // If the bug is still here, use the shuffled list.
106 TheList.swap(ShuffledList);
107 MidTop = TheList.size();
108 // Must increase the shuffling treshold to avoid the small
109 // probability of infinite looping without making progress.
110 MaxIterations += 2;
111 errs() << "\n\n*** Shuffling does not hide the bug...\n\n";
112 } else {
113 ShufflingEnabled = false; // Disable shuffling further on
114 errs() << "\n\n*** Shuffling hides the bug...\n\n";
115 }
116 NumOfIterationsWithoutProgress = 0;
117 }
118
119 unsigned Mid = MidTop / 2;
120 std::vector<ElTy> Prefix(TheList.begin(), TheList.begin() + Mid);
121 std::vector<ElTy> Suffix(TheList.begin() + Mid, TheList.end());
122
123 Expected<TestResult> Result = doTest(Prefix, Suffix);
124 if (Error E = Result.takeError())
125 return std::move(E);
126 switch (*Result) {
127 case KeepSuffix:
128 // The property still holds. We can just drop the prefix elements, and
129 // shorten the list to the "kept" elements.
130 TheList.swap(Suffix);
131 MidTop = TheList.size();
132 // Reset progress treshold and progress counter
133 MaxIterations = MaxIterationsWithoutProgress;
134 NumOfIterationsWithoutProgress = 0;
135 break;
136 case KeepPrefix:
137 // The predicate still holds, shorten the list to the prefix elements.
138 TheList.swap(Prefix);
139 MidTop = TheList.size();
140 // Reset progress treshold and progress counter
141 MaxIterations = MaxIterationsWithoutProgress;
142 NumOfIterationsWithoutProgress = 0;
143 break;
144 case NoFailure:
145 // Otherwise the property doesn't hold. Some of the elements we removed
146 // must be necessary to maintain the property.
147 MidTop = Mid;
148 NumOfIterationsWithoutProgress++;
149 break;
150 }
151 }
152
153 // Probability of backjumping from the trimming loop back to the binary
154 // split reduction loop.
155 const int BackjumpProbability = 10;
156
157 // Okay, we trimmed as much off the top and the bottom of the list as we
158 // could. If there is more than two elements in the list, try deleting
159 // interior elements and testing that.
160 //
161 if (TheList.size() > 2) {
162 bool Changed = true;
163 std::vector<ElTy> EmptyList;
164 unsigned TrimIterations = 0;
165 while (Changed) { // Trimming loop.
166 Changed = false;
167
168 // If the binary split reduction loop made an unfortunate sequence of
169 // splits, the trimming loop might be left off with a huge number of
170 // remaining elements (large search space). Backjumping out of that
171 // search space and attempting a different split can significantly
172 // improve the convergence speed.
173 if (std::rand() % 100 < BackjumpProbability)
174 goto Backjump;
175
176 for (unsigned i = 1; i < TheList.size() - 1; ++i) {
177 // Check interior elts
178 if (BugpointIsInterrupted) {
179 errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
180 return true;
181 }
182
183 std::vector<ElTy> TestList(TheList);
184 TestList.erase(TestList.begin() + i);
185
186 Expected<TestResult> Result = doTest(EmptyList, TestList);
187 if (Error E = Result.takeError())
188 return std::move(E);
189 if (*Result == KeepSuffix) {
190 // We can trim down the list!
191 TheList.swap(TestList);
192 --i; // Don't skip an element of the list
193 Changed = true;
194 }
195 }
196 if (TrimIterations >= MaxTrimIterationsWithoutBackJump)
197 break;
198 TrimIterations++;
199 }
200 }
201
202 return true; // there are some failure and we've narrowed them down
203 }
204};
205
206} // End llvm namespace
207
208#endif