1 //===- CrashDebugger.cpp - Debug compilation crashes ----------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines the bugpoint internals that narrow down compilation crashes 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "BugDriver.h" 15 #include "ListReducer.h" 16 #include "ToolRunner.h" 17 #include "llvm/ADT/SmallPtrSet.h" 18 #include "llvm/ADT/StringSet.h" 19 #include "llvm/IR/CFG.h" 20 #include "llvm/IR/Constants.h" 21 #include "llvm/IR/DerivedTypes.h" 22 #include "llvm/IR/Instructions.h" 23 #include "llvm/IR/LegacyPassManager.h" 24 #include "llvm/IR/Module.h" 25 #include "llvm/IR/ValueSymbolTable.h" 26 #include "llvm/IR/Verifier.h" 27 #include "llvm/Pass.h" 28 #include "llvm/Support/CommandLine.h" 29 #include "llvm/Support/FileUtilities.h" 30 #include "llvm/Transforms/Scalar.h" 31 #include "llvm/Transforms/Utils/Cloning.h" 32 #include <set> 33 using namespace llvm; 34 35 namespace { 36 cl::opt<bool> 37 KeepMain("keep-main", 38 cl::desc("Force function reduction to keep main"), 39 cl::init(false)); 40 cl::opt<bool> 41 NoGlobalRM ("disable-global-remove", 42 cl::desc("Do not remove global variables"), 43 cl::init(false)); 44 45 cl::opt<bool> 46 ReplaceFuncsWithNull("replace-funcs-with-null", 47 cl::desc("When stubbing functions, replace all uses will null"), 48 cl::init(false)); 49 cl::opt<bool> 50 DontReducePassList("disable-pass-list-reduction", 51 cl::desc("Skip pass list reduction steps"), 52 cl::init(false)); 53 54 cl::opt<bool> NoNamedMDRM("disable-namedmd-remove", 55 cl::desc("Do not remove global named metadata"), 56 cl::init(false)); 57 } 58 59 namespace llvm { 60 class ReducePassList : public ListReducer<std::string> { 61 BugDriver &BD; 62 public: 63 ReducePassList(BugDriver &bd) : BD(bd) {} 64 65 // doTest - Return true iff running the "removed" passes succeeds, and 66 // running the "Kept" passes fail when run on the output of the "removed" 67 // passes. If we return true, we update the current module of bugpoint. 68 // 69 TestResult doTest(std::vector<std::string> &Removed, 70 std::vector<std::string> &Kept, 71 std::string &Error) override; 72 }; 73 } 74 75 ReducePassList::TestResult 76 ReducePassList::doTest(std::vector<std::string> &Prefix, 77 std::vector<std::string> &Suffix, 78 std::string &Error) { 79 std::string PrefixOutput; 80 Module *OrigProgram = nullptr; 81 if (!Prefix.empty()) { 82 outs() << "Checking to see if these passes crash: " 83 << getPassesString(Prefix) << ": "; 84 if (BD.runPasses(BD.getProgram(), Prefix, PrefixOutput)) 85 return KeepPrefix; 86 87 OrigProgram = BD.Program; 88 89 BD.Program = parseInputFile(PrefixOutput, BD.getContext()).release(); 90 if (BD.Program == nullptr) { 91 errs() << BD.getToolName() << ": Error reading bitcode file '" 92 << PrefixOutput << "'!\n"; 93 exit(1); 94 } 95 sys::fs::remove(PrefixOutput); 96 } 97 98 outs() << "Checking to see if these passes crash: " 99 << getPassesString(Suffix) << ": "; 100 101 if (BD.runPasses(BD.getProgram(), Suffix)) { 102 delete OrigProgram; // The suffix crashes alone... 103 return KeepSuffix; 104 } 105 106 // Nothing failed, restore state... 107 if (OrigProgram) { 108 delete BD.Program; 109 BD.Program = OrigProgram; 110 } 111 return NoFailure; 112 } 113 114 namespace { 115 /// ReduceCrashingGlobalVariables - This works by removing the global 116 /// variable's initializer and seeing if the program still crashes. If it 117 /// does, then we keep that program and try again. 118 /// 119 class ReduceCrashingGlobalVariables : public ListReducer<GlobalVariable*> { 120 BugDriver &BD; 121 bool (*TestFn)(const BugDriver &, Module *); 122 public: 123 ReduceCrashingGlobalVariables(BugDriver &bd, 124 bool (*testFn)(const BugDriver &, Module *)) 125 : BD(bd), TestFn(testFn) {} 126 127 TestResult doTest(std::vector<GlobalVariable*> &Prefix, 128 std::vector<GlobalVariable*> &Kept, 129 std::string &Error) override { 130 if (!Kept.empty() && TestGlobalVariables(Kept)) 131 return KeepSuffix; 132 if (!Prefix.empty() && TestGlobalVariables(Prefix)) 133 return KeepPrefix; 134 return NoFailure; 135 } 136 137 bool TestGlobalVariables(std::vector<GlobalVariable*> &GVs); 138 }; 139 } 140 141 bool 142 ReduceCrashingGlobalVariables::TestGlobalVariables( 143 std::vector<GlobalVariable*> &GVs) { 144 // Clone the program to try hacking it apart... 145 ValueToValueMapTy VMap; 146 Module *M = CloneModule(BD.getProgram(), VMap).release(); 147 148 // Convert list to set for fast lookup... 149 std::set<GlobalVariable*> GVSet; 150 151 for (unsigned i = 0, e = GVs.size(); i != e; ++i) { 152 GlobalVariable* CMGV = cast<GlobalVariable>(VMap[GVs[i]]); 153 assert(CMGV && "Global Variable not in module?!"); 154 GVSet.insert(CMGV); 155 } 156 157 outs() << "Checking for crash with only these global variables: "; 158 PrintGlobalVariableList(GVs); 159 outs() << ": "; 160 161 // Loop over and delete any global variables which we aren't supposed to be 162 // playing with... 163 for (GlobalVariable &I : M->globals()) 164 if (I.hasInitializer() && !GVSet.count(&I)) { 165 DeleteGlobalInitializer(&I); 166 I.setLinkage(GlobalValue::ExternalLinkage); 167 I.setComdat(nullptr); 168 } 169 170 // Try running the hacked up program... 171 if (TestFn(BD, M)) { 172 BD.setNewProgram(M); // It crashed, keep the trimmed version... 173 174 // Make sure to use global variable pointers that point into the now-current 175 // module. 176 GVs.assign(GVSet.begin(), GVSet.end()); 177 return true; 178 } 179 180 delete M; 181 return false; 182 } 183 184 namespace { 185 /// ReduceCrashingFunctions reducer - This works by removing functions and 186 /// seeing if the program still crashes. If it does, then keep the newer, 187 /// smaller program. 188 /// 189 class ReduceCrashingFunctions : public ListReducer<Function*> { 190 BugDriver &BD; 191 bool (*TestFn)(const BugDriver &, Module *); 192 public: 193 ReduceCrashingFunctions(BugDriver &bd, 194 bool (*testFn)(const BugDriver &, Module *)) 195 : BD(bd), TestFn(testFn) {} 196 197 TestResult doTest(std::vector<Function*> &Prefix, 198 std::vector<Function*> &Kept, 199 std::string &Error) override { 200 if (!Kept.empty() && TestFuncs(Kept)) 201 return KeepSuffix; 202 if (!Prefix.empty() && TestFuncs(Prefix)) 203 return KeepPrefix; 204 return NoFailure; 205 } 206 207 bool TestFuncs(std::vector<Function*> &Prefix); 208 }; 209 } 210 211 static void RemoveFunctionReferences(Module *M, const char* Name) { 212 auto *UsedVar = M->getGlobalVariable(Name, true); 213 if (!UsedVar || !UsedVar->hasInitializer()) return; 214 if (isa<ConstantAggregateZero>(UsedVar->getInitializer())) { 215 assert(UsedVar->use_empty()); 216 UsedVar->eraseFromParent(); 217 return; 218 } 219 auto *OldUsedVal = cast<ConstantArray>(UsedVar->getInitializer()); 220 std::vector<Constant*> Used; 221 for(Value *V : OldUsedVal->operand_values()) { 222 Constant *Op = cast<Constant>(V->stripPointerCasts()); 223 if(!Op->isNullValue()) { 224 Used.push_back(cast<Constant>(V)); 225 } 226 } 227 auto *NewValElemTy = OldUsedVal->getType()->getElementType(); 228 auto *NewValTy = ArrayType::get(NewValElemTy, Used.size()); 229 auto *NewUsedVal = ConstantArray::get(NewValTy, Used); 230 UsedVar->mutateType(NewUsedVal->getType()->getPointerTo()); 231 UsedVar->setInitializer(NewUsedVal); 232 } 233 234 bool ReduceCrashingFunctions::TestFuncs(std::vector<Function*> &Funcs) { 235 // If main isn't present, claim there is no problem. 236 if (KeepMain && std::find(Funcs.begin(), Funcs.end(), 237 BD.getProgram()->getFunction("main")) == 238 Funcs.end()) 239 return false; 240 241 // Clone the program to try hacking it apart... 242 ValueToValueMapTy VMap; 243 Module *M = CloneModule(BD.getProgram(), VMap).release(); 244 245 // Convert list to set for fast lookup... 246 std::set<Function*> Functions; 247 for (unsigned i = 0, e = Funcs.size(); i != e; ++i) { 248 Function *CMF = cast<Function>(VMap[Funcs[i]]); 249 assert(CMF && "Function not in module?!"); 250 assert(CMF->getFunctionType() == Funcs[i]->getFunctionType() && "wrong ty"); 251 assert(CMF->getName() == Funcs[i]->getName() && "wrong name"); 252 Functions.insert(CMF); 253 } 254 255 outs() << "Checking for crash with only these functions: "; 256 PrintFunctionList(Funcs); 257 outs() << ": "; 258 if (!ReplaceFuncsWithNull) { 259 // Loop over and delete any functions which we aren't supposed to be playing 260 // with... 261 for (Function &I : *M) 262 if (!I.isDeclaration() && !Functions.count(&I)) 263 DeleteFunctionBody(&I); 264 } else { 265 std::vector<GlobalValue*> ToRemove; 266 // First, remove aliases to functions we're about to purge. 267 for (GlobalAlias &Alias : M->aliases()) { 268 GlobalObject *Root = Alias.getBaseObject(); 269 Function *F = dyn_cast_or_null<Function>(Root); 270 if (F) { 271 if (Functions.count(F)) 272 // We're keeping this function. 273 continue; 274 } else if (Root->isNullValue()) { 275 // This referenced a globalalias that we've already replaced, 276 // so we still need to replace this alias. 277 } else if (!F) { 278 // Not a function, therefore not something we mess with. 279 continue; 280 } 281 282 PointerType *Ty = cast<PointerType>(Alias.getType()); 283 Constant *Replacement = ConstantPointerNull::get(Ty); 284 Alias.replaceAllUsesWith(Replacement); 285 ToRemove.push_back(&Alias); 286 } 287 288 for (Function &I : *M) { 289 if (!I.isDeclaration() && !Functions.count(&I)) { 290 PointerType *Ty = cast<PointerType>(I.getType()); 291 Constant *Replacement = ConstantPointerNull::get(Ty); 292 I.replaceAllUsesWith(Replacement); 293 ToRemove.push_back(&I); 294 } 295 } 296 297 for (auto *F : ToRemove) { 298 F->eraseFromParent(); 299 } 300 301 // Finally, remove any null members from any global intrinsic. 302 RemoveFunctionReferences(M, "llvm.used"); 303 RemoveFunctionReferences(M, "llvm.compiler.used"); 304 } 305 // Try running the hacked up program... 306 if (TestFn(BD, M)) { 307 BD.setNewProgram(M); // It crashed, keep the trimmed version... 308 309 // Make sure to use function pointers that point into the now-current 310 // module. 311 Funcs.assign(Functions.begin(), Functions.end()); 312 return true; 313 } 314 delete M; 315 return false; 316 } 317 318 319 namespace { 320 /// ReduceCrashingBlocks reducer - This works by setting the terminators of 321 /// all terminators except the specified basic blocks to a 'ret' instruction, 322 /// then running the simplify-cfg pass. This has the effect of chopping up 323 /// the CFG really fast which can reduce large functions quickly. 324 /// 325 class ReduceCrashingBlocks : public ListReducer<const BasicBlock*> { 326 BugDriver &BD; 327 bool (*TestFn)(const BugDriver &, Module *); 328 public: 329 ReduceCrashingBlocks(BugDriver &bd, 330 bool (*testFn)(const BugDriver &, Module *)) 331 : BD(bd), TestFn(testFn) {} 332 333 TestResult doTest(std::vector<const BasicBlock*> &Prefix, 334 std::vector<const BasicBlock*> &Kept, 335 std::string &Error) override { 336 if (!Kept.empty() && TestBlocks(Kept)) 337 return KeepSuffix; 338 if (!Prefix.empty() && TestBlocks(Prefix)) 339 return KeepPrefix; 340 return NoFailure; 341 } 342 343 bool TestBlocks(std::vector<const BasicBlock*> &Prefix); 344 }; 345 } 346 347 bool ReduceCrashingBlocks::TestBlocks(std::vector<const BasicBlock*> &BBs) { 348 // Clone the program to try hacking it apart... 349 ValueToValueMapTy VMap; 350 Module *M = CloneModule(BD.getProgram(), VMap).release(); 351 352 // Convert list to set for fast lookup... 353 SmallPtrSet<BasicBlock*, 8> Blocks; 354 for (unsigned i = 0, e = BBs.size(); i != e; ++i) 355 Blocks.insert(cast<BasicBlock>(VMap[BBs[i]])); 356 357 outs() << "Checking for crash with only these blocks:"; 358 unsigned NumPrint = Blocks.size(); 359 if (NumPrint > 10) NumPrint = 10; 360 for (unsigned i = 0, e = NumPrint; i != e; ++i) 361 outs() << " " << BBs[i]->getName(); 362 if (NumPrint < Blocks.size()) 363 outs() << "... <" << Blocks.size() << " total>"; 364 outs() << ": "; 365 366 // Loop over and delete any hack up any blocks that are not listed... 367 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 368 for (Function::iterator BB = I->begin(), E = I->end(); BB != E; ++BB) 369 if (!Blocks.count(&*BB) && BB->getTerminator()->getNumSuccessors()) { 370 // Loop over all of the successors of this block, deleting any PHI nodes 371 // that might include it. 372 for (succ_iterator SI = succ_begin(&*BB), E = succ_end(&*BB); SI != E; 373 ++SI) 374 (*SI)->removePredecessor(&*BB); 375 376 TerminatorInst *BBTerm = BB->getTerminator(); 377 if (BBTerm->isEHPad() || BBTerm->getType()->isTokenTy()) 378 continue; 379 if (!BBTerm->getType()->isVoidTy()) 380 BBTerm->replaceAllUsesWith(Constant::getNullValue(BBTerm->getType())); 381 382 // Replace the old terminator instruction. 383 BB->getInstList().pop_back(); 384 new UnreachableInst(BB->getContext(), &*BB); 385 } 386 387 // The CFG Simplifier pass may delete one of the basic blocks we are 388 // interested in. If it does we need to take the block out of the list. Make 389 // a "persistent mapping" by turning basic blocks into <function, name> pairs. 390 // This won't work well if blocks are unnamed, but that is just the risk we 391 // have to take. 392 std::vector<std::pair<std::string, std::string> > BlockInfo; 393 394 for (BasicBlock *BB : Blocks) 395 BlockInfo.emplace_back(BB->getParent()->getName(), BB->getName()); 396 397 // Now run the CFG simplify pass on the function... 398 std::vector<std::string> Passes; 399 Passes.push_back("simplifycfg"); 400 Passes.push_back("verify"); 401 std::unique_ptr<Module> New = BD.runPassesOn(M, Passes); 402 delete M; 403 if (!New) { 404 errs() << "simplifycfg failed!\n"; 405 exit(1); 406 } 407 M = New.release(); 408 409 // Try running on the hacked up program... 410 if (TestFn(BD, M)) { 411 BD.setNewProgram(M); // It crashed, keep the trimmed version... 412 413 // Make sure to use basic block pointers that point into the now-current 414 // module, and that they don't include any deleted blocks. 415 BBs.clear(); 416 const ValueSymbolTable &GST = M->getValueSymbolTable(); 417 for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) { 418 Function *F = cast<Function>(GST.lookup(BlockInfo[i].first)); 419 ValueSymbolTable &ST = F->getValueSymbolTable(); 420 Value* V = ST.lookup(BlockInfo[i].second); 421 if (V && V->getType() == Type::getLabelTy(V->getContext())) 422 BBs.push_back(cast<BasicBlock>(V)); 423 } 424 return true; 425 } 426 delete M; // It didn't crash, try something else. 427 return false; 428 } 429 430 namespace { 431 /// ReduceCrashingInstructions reducer - This works by removing the specified 432 /// non-terminator instructions and replacing them with undef. 433 /// 434 class ReduceCrashingInstructions : public ListReducer<const Instruction*> { 435 BugDriver &BD; 436 bool (*TestFn)(const BugDriver &, Module *); 437 public: 438 ReduceCrashingInstructions(BugDriver &bd, 439 bool (*testFn)(const BugDriver &, Module *)) 440 : BD(bd), TestFn(testFn) {} 441 442 TestResult doTest(std::vector<const Instruction*> &Prefix, 443 std::vector<const Instruction*> &Kept, 444 std::string &Error) override { 445 if (!Kept.empty() && TestInsts(Kept)) 446 return KeepSuffix; 447 if (!Prefix.empty() && TestInsts(Prefix)) 448 return KeepPrefix; 449 return NoFailure; 450 } 451 452 bool TestInsts(std::vector<const Instruction*> &Prefix); 453 }; 454 } 455 456 bool ReduceCrashingInstructions::TestInsts(std::vector<const Instruction*> 457 &Insts) { 458 // Clone the program to try hacking it apart... 459 ValueToValueMapTy VMap; 460 Module *M = CloneModule(BD.getProgram(), VMap).release(); 461 462 // Convert list to set for fast lookup... 463 SmallPtrSet<Instruction*, 32> Instructions; 464 for (unsigned i = 0, e = Insts.size(); i != e; ++i) { 465 assert(!isa<TerminatorInst>(Insts[i])); 466 Instructions.insert(cast<Instruction>(VMap[Insts[i]])); 467 } 468 469 outs() << "Checking for crash with only " << Instructions.size(); 470 if (Instructions.size() == 1) 471 outs() << " instruction: "; 472 else 473 outs() << " instructions: "; 474 475 for (Module::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI) 476 for (Function::iterator FI = MI->begin(), FE = MI->end(); FI != FE; ++FI) 477 for (BasicBlock::iterator I = FI->begin(), E = FI->end(); I != E;) { 478 Instruction *Inst = &*I++; 479 if (!Instructions.count(Inst) && !isa<TerminatorInst>(Inst) && 480 !Inst->isEHPad() && !Inst->getType()->isTokenTy()) { 481 if (!Inst->getType()->isVoidTy()) 482 Inst->replaceAllUsesWith(UndefValue::get(Inst->getType())); 483 Inst->eraseFromParent(); 484 } 485 } 486 487 // Verify that this is still valid. 488 legacy::PassManager Passes; 489 Passes.add(createVerifierPass()); 490 Passes.run(*M); 491 492 // Try running on the hacked up program... 493 if (TestFn(BD, M)) { 494 BD.setNewProgram(M); // It crashed, keep the trimmed version... 495 496 // Make sure to use instruction pointers that point into the now-current 497 // module, and that they don't include any deleted blocks. 498 Insts.clear(); 499 for (Instruction *Inst : Instructions) 500 Insts.push_back(Inst); 501 return true; 502 } 503 delete M; // It didn't crash, try something else. 504 return false; 505 } 506 507 namespace { 508 // Reduce the list of Named Metadata nodes. We keep this as a list of 509 // names to avoid having to convert back and forth every time. 510 class ReduceCrashingNamedMD : public ListReducer<std::string> { 511 BugDriver &BD; 512 bool (*TestFn)(const BugDriver &, Module *); 513 514 public: 515 ReduceCrashingNamedMD(BugDriver &bd, 516 bool (*testFn)(const BugDriver &, Module *)) 517 : BD(bd), TestFn(testFn) {} 518 519 TestResult doTest(std::vector<std::string> &Prefix, 520 std::vector<std::string> &Kept, 521 std::string &Error) override { 522 if (!Kept.empty() && TestNamedMDs(Kept)) 523 return KeepSuffix; 524 if (!Prefix.empty() && TestNamedMDs(Prefix)) 525 return KeepPrefix; 526 return NoFailure; 527 } 528 529 bool TestNamedMDs(std::vector<std::string> &NamedMDs); 530 }; 531 } 532 533 bool ReduceCrashingNamedMD::TestNamedMDs(std::vector<std::string> &NamedMDs) { 534 535 ValueToValueMapTy VMap; 536 Module *M = CloneModule(BD.getProgram(), VMap).release(); 537 538 outs() << "Checking for crash with only these named metadata nodes:"; 539 unsigned NumPrint = std::min<size_t>(NamedMDs.size(), 10); 540 for (unsigned i = 0, e = NumPrint; i != e; ++i) 541 outs() << " " << NamedMDs[i]; 542 if (NumPrint < NamedMDs.size()) 543 outs() << "... <" << NamedMDs.size() << " total>"; 544 outs() << ": "; 545 546 // Make a StringMap for faster lookup 547 StringSet<> Names; 548 for (const std::string &Name : NamedMDs) 549 Names.insert(Name); 550 551 // First collect all the metadata to delete in a vector, then 552 // delete them all at once to avoid invalidating the iterator 553 std::vector<NamedMDNode *> ToDelete; 554 ToDelete.reserve(M->named_metadata_size() - Names.size()); 555 for (auto &NamedMD : M->named_metadata()) 556 // Always keep a nonempty llvm.dbg.cu because the Verifier would complain. 557 if (!Names.count(NamedMD.getName()) && 558 (!(NamedMD.getName() == "llvm.dbg.cu" && NamedMD.getNumOperands() > 0))) 559 ToDelete.push_back(&NamedMD); 560 561 for (auto *NamedMD : ToDelete) 562 NamedMD->eraseFromParent(); 563 564 // Verify that this is still valid. 565 legacy::PassManager Passes; 566 Passes.add(createVerifierPass()); 567 Passes.run(*M); 568 569 // Try running on the hacked up program... 570 if (TestFn(BD, M)) { 571 BD.setNewProgram(M); // It crashed, keep the trimmed version... 572 return true; 573 } 574 delete M; // It didn't crash, try something else. 575 return false; 576 } 577 578 namespace { 579 // Reduce the list of operands to named metadata nodes 580 class ReduceCrashingNamedMDOps : public ListReducer<const MDNode *> { 581 BugDriver &BD; 582 bool (*TestFn)(const BugDriver &, Module *); 583 584 public: 585 ReduceCrashingNamedMDOps(BugDriver &bd, 586 bool (*testFn)(const BugDriver &, Module *)) 587 : BD(bd), TestFn(testFn) {} 588 589 TestResult doTest(std::vector<const MDNode *> &Prefix, 590 std::vector<const MDNode *> &Kept, 591 std::string &Error) override { 592 if (!Kept.empty() && TestNamedMDOps(Kept)) 593 return KeepSuffix; 594 if (!Prefix.empty() && TestNamedMDOps(Prefix)) 595 return KeepPrefix; 596 return NoFailure; 597 } 598 599 bool TestNamedMDOps(std::vector<const MDNode *> &NamedMDOps); 600 }; 601 } 602 603 bool ReduceCrashingNamedMDOps::TestNamedMDOps( 604 std::vector<const MDNode *> &NamedMDOps) { 605 // Convert list to set for fast lookup... 606 SmallPtrSet<const MDNode *, 32> OldMDNodeOps; 607 for (unsigned i = 0, e = NamedMDOps.size(); i != e; ++i) { 608 OldMDNodeOps.insert(NamedMDOps[i]); 609 } 610 611 outs() << "Checking for crash with only " << OldMDNodeOps.size(); 612 if (OldMDNodeOps.size() == 1) 613 outs() << " named metadata operand: "; 614 else 615 outs() << " named metadata operands: "; 616 617 ValueToValueMapTy VMap; 618 Module *M = CloneModule(BD.getProgram(), VMap).release(); 619 620 // This is a little wasteful. In the future it might be good if we could have 621 // these dropped during cloning. 622 for (auto &NamedMD : BD.getProgram()->named_metadata()) { 623 // Drop the old one and create a new one 624 M->eraseNamedMetadata(M->getNamedMetadata(NamedMD.getName())); 625 NamedMDNode *NewNamedMDNode = 626 M->getOrInsertNamedMetadata(NamedMD.getName()); 627 for (MDNode *op : NamedMD.operands()) 628 if (OldMDNodeOps.count(op)) 629 NewNamedMDNode->addOperand(cast<MDNode>(MapMetadata(op, VMap))); 630 } 631 632 // Verify that this is still valid. 633 legacy::PassManager Passes; 634 Passes.add(createVerifierPass()); 635 Passes.run(*M); 636 637 // Try running on the hacked up program... 638 if (TestFn(BD, M)) { 639 // Make sure to use instruction pointers that point into the now-current 640 // module, and that they don't include any deleted blocks. 641 NamedMDOps.clear(); 642 for (const MDNode *Node : OldMDNodeOps) 643 NamedMDOps.push_back(cast<MDNode>(*VMap.getMappedMD(Node))); 644 645 BD.setNewProgram(M); // It crashed, keep the trimmed version... 646 return true; 647 } 648 delete M; // It didn't crash, try something else. 649 return false; 650 } 651 652 static void ReduceGlobalInitializers(BugDriver &BD, 653 bool (*TestFn)(const BugDriver &, Module *), 654 std::string &Error) { 655 if (BD.getProgram()->global_begin() != BD.getProgram()->global_end()) { 656 // Now try to reduce the number of global variable initializers in the 657 // module to something small. 658 Module *M = CloneModule(BD.getProgram()).release(); 659 bool DeletedInit = false; 660 661 for (Module::global_iterator I = M->global_begin(), E = M->global_end(); 662 I != E; ++I) 663 if (I->hasInitializer()) { 664 DeleteGlobalInitializer(&*I); 665 I->setLinkage(GlobalValue::ExternalLinkage); 666 I->setComdat(nullptr); 667 DeletedInit = true; 668 } 669 670 if (!DeletedInit) { 671 delete M; // No change made... 672 } else { 673 // See if the program still causes a crash... 674 outs() << "\nChecking to see if we can delete global inits: "; 675 676 if (TestFn(BD, M)) { // Still crashes? 677 BD.setNewProgram(M); 678 outs() << "\n*** Able to remove all global initializers!\n"; 679 } else { // No longer crashes? 680 outs() << " - Removing all global inits hides problem!\n"; 681 delete M; 682 683 std::vector<GlobalVariable*> GVs; 684 685 for (Module::global_iterator I = BD.getProgram()->global_begin(), 686 E = BD.getProgram()->global_end(); I != E; ++I) 687 if (I->hasInitializer()) 688 GVs.push_back(&*I); 689 690 if (GVs.size() > 1 && !BugpointIsInterrupted) { 691 outs() << "\n*** Attempting to reduce the number of global " 692 << "variables in the testcase\n"; 693 694 unsigned OldSize = GVs.size(); 695 ReduceCrashingGlobalVariables(BD, TestFn).reduceList(GVs, Error); 696 assert(!Error.empty()); 697 698 if (GVs.size() < OldSize) 699 BD.EmitProgressBitcode(BD.getProgram(), "reduced-global-variables"); 700 } 701 } 702 } 703 } 704 } 705 706 static void ReduceInsts(BugDriver &BD, 707 bool (*TestFn)(const BugDriver &, Module *), 708 std::string &Error) { 709 // Attempt to delete instructions using bisection. This should help out nasty 710 // cases with large basic blocks where the problem is at one end. 711 if (!BugpointIsInterrupted) { 712 std::vector<const Instruction*> Insts; 713 for (const Function &F : *BD.getProgram()) 714 for (const BasicBlock &BB : F) 715 for (const Instruction &I : BB) 716 if (!isa<TerminatorInst>(&I)) 717 Insts.push_back(&I); 718 719 ReduceCrashingInstructions(BD, TestFn).reduceList(Insts, Error); 720 } 721 722 unsigned Simplification = 2; 723 do { 724 if (BugpointIsInterrupted) 725 return; 726 --Simplification; 727 outs() << "\n*** Attempting to reduce testcase by deleting instruc" 728 << "tions: Simplification Level #" << Simplification << '\n'; 729 730 // Now that we have deleted the functions that are unnecessary for the 731 // program, try to remove instructions that are not necessary to cause the 732 // crash. To do this, we loop through all of the instructions in the 733 // remaining functions, deleting them (replacing any values produced with 734 // nulls), and then running ADCE and SimplifyCFG. If the transformed input 735 // still triggers failure, keep deleting until we cannot trigger failure 736 // anymore. 737 // 738 unsigned InstructionsToSkipBeforeDeleting = 0; 739 TryAgain: 740 741 // Loop over all of the (non-terminator) instructions remaining in the 742 // function, attempting to delete them. 743 unsigned CurInstructionNum = 0; 744 for (Module::const_iterator FI = BD.getProgram()->begin(), 745 E = BD.getProgram()->end(); FI != E; ++FI) 746 if (!FI->isDeclaration()) 747 for (Function::const_iterator BI = FI->begin(), E = FI->end(); BI != E; 748 ++BI) 749 for (BasicBlock::const_iterator I = BI->begin(), E = --BI->end(); 750 I != E; ++I, ++CurInstructionNum) { 751 if (InstructionsToSkipBeforeDeleting) { 752 --InstructionsToSkipBeforeDeleting; 753 } else { 754 if (BugpointIsInterrupted) 755 return; 756 757 if (I->isEHPad() || I->getType()->isTokenTy()) 758 continue; 759 760 outs() << "Checking instruction: " << *I; 761 std::unique_ptr<Module> M = 762 BD.deleteInstructionFromProgram(&*I, Simplification); 763 764 // Find out if the pass still crashes on this pass... 765 if (TestFn(BD, M.get())) { 766 // Yup, it does, we delete the old module, and continue trying 767 // to reduce the testcase... 768 BD.setNewProgram(M.release()); 769 InstructionsToSkipBeforeDeleting = CurInstructionNum; 770 goto TryAgain; // I wish I had a multi-level break here! 771 } 772 } 773 } 774 775 if (InstructionsToSkipBeforeDeleting) { 776 InstructionsToSkipBeforeDeleting = 0; 777 goto TryAgain; 778 } 779 780 } while (Simplification); 781 BD.EmitProgressBitcode(BD.getProgram(), "reduced-instructions"); 782 } 783 784 785 /// DebugACrash - Given a predicate that determines whether a component crashes 786 /// on a program, try to destructively reduce the program while still keeping 787 /// the predicate true. 788 static bool DebugACrash(BugDriver &BD, 789 bool (*TestFn)(const BugDriver &, Module *), 790 std::string &Error) { 791 // See if we can get away with nuking some of the global variable initializers 792 // in the program... 793 if (!NoGlobalRM) 794 ReduceGlobalInitializers(BD, TestFn, Error); 795 796 // Now try to reduce the number of functions in the module to something small. 797 std::vector<Function*> Functions; 798 for (Function &F : *BD.getProgram()) 799 if (!F.isDeclaration()) 800 Functions.push_back(&F); 801 802 if (Functions.size() > 1 && !BugpointIsInterrupted) { 803 outs() << "\n*** Attempting to reduce the number of functions " 804 "in the testcase\n"; 805 806 unsigned OldSize = Functions.size(); 807 ReduceCrashingFunctions(BD, TestFn).reduceList(Functions, Error); 808 809 if (Functions.size() < OldSize) 810 BD.EmitProgressBitcode(BD.getProgram(), "reduced-function"); 811 } 812 813 // Attempt to delete entire basic blocks at a time to speed up 814 // convergence... this actually works by setting the terminator of the blocks 815 // to a return instruction then running simplifycfg, which can potentially 816 // shrinks the code dramatically quickly 817 // 818 if (!DisableSimplifyCFG && !BugpointIsInterrupted) { 819 std::vector<const BasicBlock*> Blocks; 820 for (Function &F : *BD.getProgram()) 821 for (BasicBlock &BB : F) 822 Blocks.push_back(&BB); 823 unsigned OldSize = Blocks.size(); 824 ReduceCrashingBlocks(BD, TestFn).reduceList(Blocks, Error); 825 if (Blocks.size() < OldSize) 826 BD.EmitProgressBitcode(BD.getProgram(), "reduced-blocks"); 827 } 828 829 // Attempt to delete instructions using bisection. This should help out nasty 830 // cases with large basic blocks where the problem is at one end. 831 if (!BugpointIsInterrupted) 832 ReduceInsts(BD, TestFn, Error); 833 834 if (!NoNamedMDRM) { 835 if (!BugpointIsInterrupted) { 836 // Try to reduce the amount of global metadata (particularly debug info), 837 // by dropping global named metadata that anchors them 838 outs() << "\n*** Attempting to remove named metadata: "; 839 std::vector<std::string> NamedMDNames; 840 for (auto &NamedMD : BD.getProgram()->named_metadata()) 841 NamedMDNames.push_back(NamedMD.getName().str()); 842 ReduceCrashingNamedMD(BD, TestFn).reduceList(NamedMDNames, Error); 843 } 844 845 if (!BugpointIsInterrupted) { 846 // Now that we quickly dropped all the named metadata that doesn't 847 // contribute to the crash, bisect the operands of the remaining ones 848 std::vector<const MDNode *> NamedMDOps; 849 for (auto &NamedMD : BD.getProgram()->named_metadata()) 850 for (auto op : NamedMD.operands()) 851 NamedMDOps.push_back(op); 852 ReduceCrashingNamedMDOps(BD, TestFn).reduceList(NamedMDOps, Error); 853 } 854 BD.EmitProgressBitcode(BD.getProgram(), "reduced-named-md"); 855 } 856 857 // Try to clean up the testcase by running funcresolve and globaldce... 858 if (!BugpointIsInterrupted) { 859 outs() << "\n*** Attempting to perform final cleanups: "; 860 Module *M = CloneModule(BD.getProgram()).release(); 861 M = BD.performFinalCleanups(M, true).release(); 862 863 // Find out if the pass still crashes on the cleaned up program... 864 if (TestFn(BD, M)) { 865 BD.setNewProgram(M); // Yup, it does, keep the reduced version... 866 } else { 867 delete M; 868 } 869 } 870 871 BD.EmitProgressBitcode(BD.getProgram(), "reduced-simplified"); 872 873 return false; 874 } 875 876 static bool TestForOptimizerCrash(const BugDriver &BD, Module *M) { 877 return BD.runPasses(M, BD.getPassesToRun()); 878 } 879 880 /// debugOptimizerCrash - This method is called when some pass crashes on input. 881 /// It attempts to prune down the testcase to something reasonable, and figure 882 /// out exactly which pass is crashing. 883 /// 884 bool BugDriver::debugOptimizerCrash(const std::string &ID) { 885 outs() << "\n*** Debugging optimizer crash!\n"; 886 887 std::string Error; 888 // Reduce the list of passes which causes the optimizer to crash... 889 if (!BugpointIsInterrupted && !DontReducePassList) 890 ReducePassList(*this).reduceList(PassesToRun, Error); 891 assert(Error.empty()); 892 893 outs() << "\n*** Found crashing pass" 894 << (PassesToRun.size() == 1 ? ": " : "es: ") 895 << getPassesString(PassesToRun) << '\n'; 896 897 EmitProgressBitcode(Program, ID); 898 899 bool Success = DebugACrash(*this, TestForOptimizerCrash, Error); 900 assert(Error.empty()); 901 return Success; 902 } 903 904 static bool TestForCodeGenCrash(const BugDriver &BD, Module *M) { 905 std::string Error; 906 BD.compileProgram(M, &Error); 907 if (!Error.empty()) { 908 errs() << "<crash>\n"; 909 return true; // Tool is still crashing. 910 } 911 errs() << '\n'; 912 return false; 913 } 914 915 /// debugCodeGeneratorCrash - This method is called when the code generator 916 /// crashes on an input. It attempts to reduce the input as much as possible 917 /// while still causing the code generator to crash. 918 bool BugDriver::debugCodeGeneratorCrash(std::string &Error) { 919 errs() << "*** Debugging code generator crash!\n"; 920 921 return DebugACrash(*this, TestForCodeGenCrash, Error); 922 } 923