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