Index: include/llvm/Transforms/Utils/Cloning.h =================================================================== --- include/llvm/Transforms/Utils/Cloning.h +++ include/llvm/Transforms/Utils/Cloning.h @@ -59,7 +59,8 @@ /// in place of the global definition. std::unique_ptr CloneModule(const Module *M, ValueToValueMapTy &VMap, - std::function ShouldCloneDefinition); + std::function ShouldCloneDefinition, + RemapFlags ExtraFlags = RF_None); /// ClonedCodeInfo - This struct can be used to capture information about code /// being cloned, while it is being cloned. @@ -136,12 +137,12 @@ /// fills in a list of return instructions, and can optionally remap types /// and/or append the specified suffix to all values cloned. /// -/// If ModuleLevelChanges is false, VMap contains no non-identity GlobalValue -/// mappings. +/// If Flags contains RF_NoModuleLevelChanges, VMap contains no non-identity +/// GlobalValue mappings. /// void CloneFunctionInto(Function *NewFunc, const Function *OldFunc, - ValueToValueMapTy &VMap, bool ModuleLevelChanges, - SmallVectorImpl &Returns, + ValueToValueMapTy &VMap, RemapFlags Flags, + SmallVectorImpl &Returns, const char *NameSuffix = "", ClonedCodeInfo *CodeInfo = nullptr, ValueMapTypeRemapper *TypeMapper = nullptr, Index: lib/ExecutionEngine/Orc/IndirectionUtils.cpp =================================================================== --- lib/ExecutionEngine/Orc/IndirectionUtils.cpp +++ lib/ExecutionEngine/Orc/IndirectionUtils.cpp @@ -145,8 +145,8 @@ "modules."); SmallVector Returns; // Ignore returns cloned. - CloneFunctionInto(NewF, &OrigF, VMap, /*ModuleLevelChanges=*/true, Returns, - "", nullptr, nullptr, Materializer); + CloneFunctionInto(NewF, &OrigF, VMap, RF_None, Returns, "", nullptr, nullptr, + Materializer); OrigF.deleteBody(); } Index: lib/IR/Metadata.cpp =================================================================== --- lib/IR/Metadata.cpp +++ lib/IR/Metadata.cpp @@ -575,7 +575,7 @@ assert(!N->isTemporary() && "Expected all forward declarations to be resolved"); if (!N->isResolved()) - N->resolveCycles(); + N->resolveCycles(AllowTemps); } } Index: lib/Target/AMDGPU/AMDGPUOpenCLImageTypeLoweringPass.cpp =================================================================== --- lib/Target/AMDGPU/AMDGPUOpenCLImageTypeLoweringPass.cpp +++ lib/Target/AMDGPU/AMDGPUOpenCLImageTypeLoweringPass.cpp @@ -301,7 +301,7 @@ } } SmallVector Returns; - CloneFunctionInto(NewF, F, VMap, /*ModuleLevelChanges=*/false, Returns); + CloneFunctionInto(NewF, F, VMap, RF_NoModuleLevelChanges, Returns); // Build new MDNode. SmallVector KernelMDArgs; Index: lib/Transforms/Utils/CloneFunction.cpp =================================================================== --- lib/Transforms/Utils/CloneFunction.cpp +++ lib/Transforms/Utils/CloneFunction.cpp @@ -76,9 +76,8 @@ // VMap values. // void llvm::CloneFunctionInto(Function *NewFunc, const Function *OldFunc, - ValueToValueMapTy &VMap, - bool ModuleLevelChanges, - SmallVectorImpl &Returns, + ValueToValueMapTy &VMap, RemapFlags Flags, + SmallVectorImpl &Returns, const char *NameSuffix, ClonedCodeInfo *CodeInfo, ValueMapTypeRemapper *TypeMapper, ValueMaterializer *Materializer) { @@ -97,10 +96,8 @@ // Fix up the personality function that got copied over. if (OldFunc->hasPersonalityFn()) - NewFunc->setPersonalityFn( - MapValue(OldFunc->getPersonalityFn(), VMap, - ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges, - TypeMapper, Materializer)); + NewFunc->setPersonalityFn(MapValue(OldFunc->getPersonalityFn(), VMap, Flags, + TypeMapper, Materializer)); AttributeSet OldAttrs = OldFunc->getAttributes(); // Clone any argument attributes that are present in the VMap. @@ -158,9 +155,7 @@ BB != BE; ++BB) // Loop over all instructions, fixing each one as we find it... for (Instruction &II : *BB) - RemapInstruction(&II, VMap, - ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges, - TypeMapper, Materializer); + RemapInstruction(&II, VMap, Flags, TypeMapper, Materializer); } // Find the MDNode which corresponds to the subprogram data that described F. @@ -251,7 +246,9 @@ CloneDebugInfoMetadata(NewF, F, VMap); SmallVector Returns; // Ignore returns cloned. - CloneFunctionInto(NewF, F, VMap, ModuleLevelChanges, Returns, "", CodeInfo); + CloneFunctionInto(NewF, F, VMap, + ModuleLevelChanges ? RF_None : RF_NoModuleLevelChanges, + Returns, "", CodeInfo); return NewF; } Index: lib/Transforms/Utils/CloneModule.cpp =================================================================== --- lib/Transforms/Utils/CloneModule.cpp +++ lib/Transforms/Utils/CloneModule.cpp @@ -38,7 +38,8 @@ std::unique_ptr llvm::CloneModule( const Module *M, ValueToValueMapTy &VMap, - std::function ShouldCloneDefinition) { + std::function ShouldCloneDefinition, + llvm::RemapFlags ExtraFlags) { // First off, we need to create the new module. std::unique_ptr New = llvm::make_unique(M->getModuleIdentifier(), M->getContext()); @@ -116,7 +117,7 @@ continue; } if (I->hasInitializer()) - GV->setInitializer(MapValue(I->getInitializer(), VMap)); + GV->setInitializer(MapValue(I->getInitializer(), VMap, ExtraFlags)); } // Similarly, copy over function bodies now... @@ -137,11 +138,12 @@ } SmallVector Returns; // Ignore returns cloned. - CloneFunctionInto(F, &*I, VMap, /*ModuleLevelChanges=*/true, Returns); + assert(!(ExtraFlags & RF_NoModuleLevelChanges)); + CloneFunctionInto(F, &*I, VMap, ExtraFlags, Returns); } if (I->hasPersonalityFn()) - F->setPersonalityFn(MapValue(I->getPersonalityFn(), VMap)); + F->setPersonalityFn(MapValue(I->getPersonalityFn(), VMap, ExtraFlags)); } // And aliases @@ -152,7 +154,7 @@ continue; GlobalAlias *GA = cast(VMap[&*I]); if (const Constant *C = I->getAliasee()) - GA->setAliasee(MapValue(C, VMap)); + GA->setAliasee(MapValue(C, VMap, ExtraFlags)); } // And named metadata.... @@ -161,7 +163,7 @@ const NamedMDNode &NMD = *I; NamedMDNode *NewNMD = New->getOrInsertNamedMetadata(NMD.getName()); for (unsigned i = 0, e = NMD.getNumOperands(); i != e; ++i) - NewNMD->addOperand(MapMetadata(NMD.getOperand(i), VMap)); + NewNMD->addOperand(MapMetadata(NMD.getOperand(i), VMap, ExtraFlags)); } return New; Index: test/BugPoint/metadata.ll =================================================================== --- test/BugPoint/metadata.ll +++ test/BugPoint/metadata.ll @@ -1,4 +1,4 @@ -; RUN: bugpoint -load %llvmshlibdir/BugpointPasses%shlibext %s -output-prefix %t -bugpoint-crashcalls -silence-passes > /dev/null +; RUN: bugpoint -load %llvmshlibdir/BugpointPasses%shlibext %s -output-prefix %t -bugpoint-crashcalls -silence-passes -disable-namedmd-remove > /dev/null ; RUN: llvm-dis %t-reduced-simplified.bc -o - | FileCheck %s ; REQUIRES: loadable_module Index: tools/bugpoint-passes/TestPasses.cpp =================================================================== --- tools/bugpoint-passes/TestPasses.cpp +++ tools/bugpoint-passes/TestPasses.cpp @@ -75,7 +75,7 @@ "BugPoint Test Pass - Intentionally 'misoptimize' CallInsts"); namespace { - /// CrashOnDeclFunc - This pass is used to test bugpoint. It intentionally +/// CrashOnDeclFunc - This pass is used to test bugpoint. It intentionally /// crashes if the module has an undefined function (ie a function that is /// defined in an external module). class CrashOnDeclFunc : public ModulePass { @@ -99,7 +99,62 @@ Z("bugpoint-crash-decl-funcs", "BugPoint Test Pass - Intentionally crash on declared functions"); -#include +namespace { +/// CrashOnVar - This pass is used to test bugpoint. It intentionally +/// crashes if the module has an a global variable. Checking for the CU +/// is necessary because otherwise it will realize that it can drop the debug +/// info version. +class CrashOnVarAndCU : public ModulePass { +public: + static char ID; // Pass ID, replacement for typeid + CrashOnVarAndCU() : ModulePass(ID) {} + +private: + bool runOnModule(Module &M) override { + for (auto &GV : M.globals()) { + (void)GV; + if (M.getNamedMetadata("llvm.dbg.cu")) + abort(); + } + return false; + } +}; +} + +char CrashOnVarAndCU::ID = 0; +static RegisterPass + A("bugpoint-crash-var-and-cu", + "BugPoint Test Pass - Intentionally crash on global variables as long as " + "the module has at least one CU"); + +namespace { +/// CrashOnVar - This pass is used to test bugpoint. It intentionally +/// crashes if the module has an a global variable. +class DropUnsedVar : public ModulePass { +public: + static char ID; // Pass ID, replacement for typeid + DropUnsedVar() : ModulePass(ID) {} + +private: + bool runOnModule(Module &M) override { + std::vector ToDelete; + for (auto &GV : M.globals()) + if (GV.use_empty() && !GV.isUsedByMetadata()) + ToDelete.push_back(&GV); + if (ToDelete.empty()) + return false; + for (auto *GV : ToDelete) + GV->eraseFromParent(); + return true; + } +}; +} + +char DropUnsedVar::ID = 0; +static RegisterPass + B("bugpoint-drop-unref-var", + "BugPoint Test Pass - Drop unreferenced Global Variables"); + namespace { /// CrashOnOneCU - This pass is used to test bugpoint. It intentionally /// crashes if the Module has two or more compile units @@ -122,5 +177,5 @@ char CrashOnTooManyCUs::ID = 0; static RegisterPass - A("bugpoint-crash-too-many-cus", + C("bugpoint-crash-too-many-cus", "BugPoint Test Pass - Intentionally crash on too many CUs"); Index: tools/bugpoint/CrashDebugger.cpp =================================================================== --- tools/bugpoint/CrashDebugger.cpp +++ tools/bugpoint/CrashDebugger.cpp @@ -54,6 +54,11 @@ cl::opt NoNamedMDRM("disable-namedmd-remove", cl::desc("Do not remove global named metadata"), cl::init(false)); + + cl::opt + NoTupleSquashing("disable-mdtuple-squashing", + cl::desc("Do not suqash nulls out of MDTuples"), + cl::init(false)); } namespace llvm { @@ -626,10 +631,11 @@ NewNamedMDNode->addOperand(cast(MapMetadata(op, VMap))); } - // Verify that this is still valid. - legacy::PassManager Passes; - Passes.add(createVerifierPass()); - Passes.run(*M); + // If the result is invalid, try something else + if (verifyModule(*M)) { + delete M; + return false; + } // Try running on the hacked up program... if (TestFn(BD, M)) { @@ -646,6 +652,204 @@ return false; } +namespace { +// Reduce the number of MDNodes +class ReduceCrashingMDs : public ListReducer { + BugDriver &BD; + std::vector AllMDNodes; + bool (*TestFn)(const BugDriver &, Module *); + +public: + ReduceCrashingMDs(BugDriver &bd, std::vector All, + bool (*testFn)(const BugDriver &, Module *)) + : BD(bd), AllMDNodes(All), TestFn(testFn) {} + + TestResult doTest(std::vector &Prefix, + std::vector &Kept, + std::string &Error) override { + if (!Kept.empty() && TestMDNodes(Kept)) + return KeepSuffix; + if (!Prefix.empty() && TestMDNodes(Prefix)) + return KeepPrefix; + return NoFailure; + } + + bool TestMDNodes(std::vector &MDNodes); +}; +} + +bool ReduceCrashingMDs::TestMDNodes(std::vector &MDNodes) { + // Convert list to set for fast lookup... + SmallPtrSet OldMDNodes; + for (unsigned i = 0, e = MDNodes.size(); i != e; ++i) { + OldMDNodes.insert(MDNodes[i]); + } + + outs() << "Checking for crash with only " << OldMDNodes.size(); + if (OldMDNodes.size() == 1) + outs() << " metadata node: "; + else + outs() << " metadata nodes: "; + + // Named Metadata Nodes cannnot have null operands, so always + // preserve those MD nodes (plus we already reduced them before) + SmallPtrSet NMDRoots; + for (auto &NamedMD : BD.getProgram()->named_metadata()) + for (MDNode *op : NamedMD.operands()) + NMDRoots.insert(op); + + ValueToValueMapTy VMap; + LLVMContext &Context = BD.getProgram()->getContext(); + // Insert everything we want to remove as a temporary mapping in + // the Value map + TempMDTuple Temp = MDNode::getTemporary(Context, {}); + for (const MDNode *MD : AllMDNodes) { + if (!OldMDNodes.count(MD) && !NMDRoots.count(MD)) + VMap.MD()[MD].reset(Temp.get()); + } + + // However, we need to make sure to squash tuples, since the verifier checks + // that some tuples don't have null operands. However, we also can't just + // map the operands over yet, because they may depend on global values that + // only get created in CloneModule. Thus, create temporaries for them now and + // keep a list of everything we need to resolve later. + // TODO: This isn't great, there could very well be tuples where nulls have + // semantic meaning. However, without this, the verifier will prevent us from + // getting a meaningful reduction. For now, just add a switch to disable this + // behavior. If it becomes a problem, we could do something smarter, (e.g. + // only do it for references from Debug Info nodes or making the Verifier more + // permissive) + std::vector Tuples; + if (!NoTupleSquashing) { + for (const MDNode *Node : AllMDNodes) { + if (Node && OldMDNodes.count(Node) && Node->getNumOperands() != 0 && + isa(Node)) { + if (std::any_of(Node->op_begin(), Node->op_end(), + [&](const Metadata *Operand) { + return VMap.MD()[Operand].get() == Temp.get(); + })) { + auto TempTuple = MDNode::getTemporary(Context, {}); + VMap.MD()[Node].reset(TempTuple.release()); + Tuples.push_back(cast(Node)); + } + } + } + } + + auto M = CloneModule(BD.getProgram(), VMap, + [](const GlobalValue *) { return true; }, + RF_HaveUnmaterializedMetadata); + + if (!NoTupleSquashing) { + for (const MDTuple *Tuple : Tuples) { + SmallVector Operands; + MDTuple *TempTuple = cast(VMap.MD()[Tuple].get()); + // Already mapped this tuple before (this can happen because the list of + // MD nodes is not necessarily deduplicated if two tuples map to the same + // tuple when an operand is dropped - rather than paying the cost to + // dedup, + // we just handle it here). + if (!TempTuple->isTemporary()) + continue; + for (Metadata *Operand : Tuple->operands()) + if (Operand && + (!isa(Operand) || OldMDNodes.count(cast(Operand)))) + Operands.push_back(Operand); + Metadata *SquashedNode = Tuple->isDistinct() + ? MDNode::getDistinct(Context, Operands) + : MDNode::get(Context, Operands); + // We could be in the following situation: + // !1 = {!4, !5, !6} + // !2 = {!4, !5} + // If !2 and !6 get selected for removal, the SquashedNode for !1 would be + // !2 by uniquing, but the VMap already has our guard entry. To avoid that + // situation, clear the VMap for the squashed node here. + VMap.MD()[SquashedNode].reset(); + Metadata *Replacement = + MapMetadata(SquashedNode, VMap, RF_HaveUnmaterializedMetadata); + TempTuple->replaceAllUsesWith(Replacement); + MDNode::deleteTemporary(TempTuple); + } + } + + Temp->replaceAllUsesWith(nullptr); + if (verifyModule(*M, &outs())) { + outs() << "Replacement invalidated module..."; + return false; + } + + // Try running on the hacked up program... + if (TestFn(BD, M.get())) { + // Make sure to use pointers that point into the now-current module. + std::vector NewMDNodes; + for (const MDNode *Node : MDNodes) { + // Even if something was in the preserve list, it is possible that it + // is null if all it's parents got dropped. Do still keep in the list + // however, because otherwise the list reducer gets confused. + MDNode *MD = cast_or_null(VMap.MD()[Node].get()); + NewMDNodes.push_back(MD); + } + MDNodes.swap(NewMDNodes); + + std::vector AllNewMDNodes; + for (const MDNode *Node : AllMDNodes) { + MDNode *MD = cast_or_null(VMap.MD()[Node].get()); + if (MD) + AllNewMDNodes.push_back(MD); + } + AllMDNodes = std::move(AllNewMDNodes); + + BD.setNewProgram(M.release()); // It crashed, keep the trimmed version... + return true; + } + return false; +} + +static void CollectMDNodeOps(const MDNode *Node, + std::set &MDs) { + MDs.insert(Node); + for (const MDOperand &Op : Node->operands()) { + const Metadata *MD = Op.get(); + if (!MD || !isa(MD)) + continue; + if (MDs.count(cast(MD))) + continue; + CollectMDNodeOps(cast(MD), MDs); + } +} + +static std::vector CollectMDNodes(llvm::Module *M) { + // Collect all roots (instruction attachments and named metadata) + std::set Roots; + for (auto &NamedMD : M->named_metadata()) + for (auto op : NamedMD.operands()) + Roots.insert(op); + + for (Module::iterator MI = M->begin(), ME = M->end(); MI != ME; ++MI) + for (Function::iterator FI = MI->begin(), FE = MI->end(); FI != FE; ++FI) + for (BasicBlock::iterator I = FI->begin(), E = FI->end(); I != E;) { + Instruction *Inst = &*I++; + SmallVector, 1> MDs; + Inst->getAllMetadata(MDs); + for (auto p : MDs) + Roots.insert(p.second); + } + + // Collect all Metadata reachable from the roots + std::set AllNodes; + for (const MDNode *Node : Roots) + CollectMDNodeOps(Node, AllNodes); + + // Convert to list suitable for reducing + std::vector AllNodeList(AllNodes.begin(), AllNodes.end()); + + // Clear the two temporary sets + Roots.clear(); + AllNodes.clear(); + + return AllNodeList; +} + /// DebugACrash - Given a predicate that determines whether a component crashes /// on a program, try to destructively reduce the program while still keeping /// the predicate true. @@ -833,6 +1037,12 @@ NamedMDOps.push_back(op); ReduceCrashingNamedMDOps(BD, TestFn).reduceList(NamedMDOps, Error); } + + if (!BugpointIsInterrupted) { + // Finally go through all metadata nodes and try to delete them + std::vector AllNodeList(CollectMDNodes(BD.getProgram())); + ReduceCrashingMDs(BD, AllNodeList, TestFn).reduceList(AllNodeList, Error); + } } ExitLoops: Index: tools/bugpoint/ListReducer.h =================================================================== --- tools/bugpoint/ListReducer.h +++ tools/bugpoint/ListReducer.h @@ -173,8 +173,8 @@ // improve the convergence speed. if (std::rand() % 100 < BackjumpProbability) goto Backjump; - - for (unsigned i = 1; i < TheList.size()-1; ++i) { // Check interior elts + + for (unsigned i = 1; i < TheList.size(); ++i) { // Check interior elts if (BugpointIsInterrupted) { errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n"; return true; Index: unittests/Transforms/Utils/Cloning.cpp =================================================================== --- unittests/Transforms/Utils/Cloning.cpp +++ unittests/Transforms/Utils/Cloning.cpp @@ -172,7 +172,7 @@ ValueToValueMapTy VMap; VMap[A] = UndefValue::get(A->getType()); - CloneFunctionInto(F2, F1, VMap, false, Returns); + CloneFunctionInto(F2, F1, VMap, RF_NoModuleLevelChanges, Returns); EXPECT_FALSE(F2->arg_begin()->hasNoCaptureAttr()); delete F1; @@ -195,7 +195,7 @@ ValueToValueMapTy VMap; VMap[&*F1->arg_begin()] = &*F2->arg_begin(); - CloneFunctionInto(F2, F1, VMap, false, Returns); + CloneFunctionInto(F2, F1, VMap, RF_NoModuleLevelChanges, Returns); EXPECT_EQ(CallingConv::Cold, F2->getCallingConv()); delete F1;