diff options
Diffstat (limited to 'lib/Transforms/Utils/Local.cpp')
-rw-r--r-- | lib/Transforms/Utils/Local.cpp | 866 |
1 files changed, 678 insertions, 188 deletions
diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp index a1961eecb391..ae3cb077a3af 100644 --- a/lib/Transforms/Utils/Local.cpp +++ b/lib/Transforms/Utils/Local.cpp @@ -73,6 +73,7 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/KnownBits.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/ValueMapper.h" #include <algorithm> #include <cassert> #include <climits> @@ -100,26 +101,23 @@ STATISTIC(NumRemoved, "Number of unreachable basic blocks removed"); /// conditions and indirectbr addresses this might make dead if /// DeleteDeadConditions is true. bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, - const TargetLibraryInfo *TLI) { + const TargetLibraryInfo *TLI, + DeferredDominance *DDT) { TerminatorInst *T = BB->getTerminator(); IRBuilder<> Builder(T); // Branch - See if we are conditional jumping on constant - if (BranchInst *BI = dyn_cast<BranchInst>(T)) { + if (auto *BI = dyn_cast<BranchInst>(T)) { if (BI->isUnconditional()) return false; // Can't optimize uncond branch BasicBlock *Dest1 = BI->getSuccessor(0); BasicBlock *Dest2 = BI->getSuccessor(1); - if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { + if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) { // Are we branching on constant? // YES. Change to unconditional branch... BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2; BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1; - //cerr << "Function: " << T->getParent()->getParent() - // << "\nRemoving branch from " << T->getParent() - // << "\n\nTo: " << OldDest << endl; - // Let the basic block know that we are letting go of it. Based on this, // it will adjust it's PHI nodes. OldDest->removePredecessor(BB); @@ -127,6 +125,8 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, // Replace the conditional branch with an unconditional one. Builder.CreateBr(Destination); BI->eraseFromParent(); + if (DDT) + DDT->deleteEdge(BB, OldDest); return true; } @@ -150,10 +150,10 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, return false; } - if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) { + if (auto *SI = dyn_cast<SwitchInst>(T)) { // If we are switching on a constant, we can convert the switch to an // unconditional branch. - ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition()); + auto *CI = dyn_cast<ConstantInt>(SI->getCondition()); BasicBlock *DefaultDest = SI->getDefaultDest(); BasicBlock *TheOnlyDest = DefaultDest; @@ -197,9 +197,12 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, createBranchWeights(Weights)); } // Remove this entry. - DefaultDest->removePredecessor(SI->getParent()); + BasicBlock *ParentBB = SI->getParent(); + DefaultDest->removePredecessor(ParentBB); i = SI->removeCase(i); e = SI->case_end(); + if (DDT) + DDT->deleteEdge(ParentBB, DefaultDest); continue; } @@ -225,14 +228,20 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, // Insert the new branch. Builder.CreateBr(TheOnlyDest); BasicBlock *BB = SI->getParent(); + std::vector <DominatorTree::UpdateType> Updates; + if (DDT) + Updates.reserve(SI->getNumSuccessors() - 1); // Remove entries from PHI nodes which we no longer branch to... for (BasicBlock *Succ : SI->successors()) { // Found case matching a constant operand? - if (Succ == TheOnlyDest) + if (Succ == TheOnlyDest) { TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest - else + } else { Succ->removePredecessor(BB); + if (DDT) + Updates.push_back({DominatorTree::Delete, BB, Succ}); + } } // Delete the old switch. @@ -240,6 +249,8 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, SI->eraseFromParent(); if (DeleteDeadConditions) RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI); + if (DDT) + DDT->applyUpdates(Updates); return true; } @@ -280,19 +291,28 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, return false; } - if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) { + if (auto *IBI = dyn_cast<IndirectBrInst>(T)) { // indirectbr blockaddress(@F, @BB) -> br label @BB - if (BlockAddress *BA = + if (auto *BA = dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) { BasicBlock *TheOnlyDest = BA->getBasicBlock(); + std::vector <DominatorTree::UpdateType> Updates; + if (DDT) + Updates.reserve(IBI->getNumDestinations() - 1); + // Insert the new branch. Builder.CreateBr(TheOnlyDest); for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { - if (IBI->getDestination(i) == TheOnlyDest) + if (IBI->getDestination(i) == TheOnlyDest) { TheOnlyDest = nullptr; - else - IBI->getDestination(i)->removePredecessor(IBI->getParent()); + } else { + BasicBlock *ParentBB = IBI->getParent(); + BasicBlock *DestBB = IBI->getDestination(i); + DestBB->removePredecessor(ParentBB); + if (DDT) + Updates.push_back({DominatorTree::Delete, ParentBB, DestBB}); + } } Value *Address = IBI->getAddress(); IBI->eraseFromParent(); @@ -307,6 +327,8 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, new UnreachableInst(BB->getContext(), BB); } + if (DDT) + DDT->applyUpdates(Updates); return true; } } @@ -350,6 +372,11 @@ bool llvm::wouldInstructionBeTriviallyDead(Instruction *I, return false; return true; } + if (DbgLabelInst *DLI = dyn_cast<DbgLabelInst>(I)) { + if (DLI->getLabel()) + return false; + return true; + } if (!I->mayHaveSideEffects()) return true; @@ -357,8 +384,9 @@ bool llvm::wouldInstructionBeTriviallyDead(Instruction *I, // Special case intrinsics that "may have side effects" but can be deleted // when dead. if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { - // Safe to delete llvm.stacksave if dead. - if (II->getIntrinsicID() == Intrinsic::stacksave) + // Safe to delete llvm.stacksave and launder.invariant.group if dead. + if (II->getIntrinsicID() == Intrinsic::stacksave || + II->getIntrinsicID() == Intrinsic::launder_invariant_group) return true; // Lifetime intrinsics are dead when their right-hand is undef. @@ -406,17 +434,31 @@ llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V, SmallVector<Instruction*, 16> DeadInsts; DeadInsts.push_back(I); + RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI); - do { - I = DeadInsts.pop_back_val(); + return true; +} + +void llvm::RecursivelyDeleteTriviallyDeadInstructions( + SmallVectorImpl<Instruction *> &DeadInsts, const TargetLibraryInfo *TLI) { + // Process the dead instruction list until empty. + while (!DeadInsts.empty()) { + Instruction &I = *DeadInsts.pop_back_val(); + assert(I.use_empty() && "Instructions with uses are not dead."); + assert(isInstructionTriviallyDead(&I, TLI) && + "Live instruction found in dead worklist!"); + + // Don't lose the debug info while deleting the instructions. + salvageDebugInfo(I); // Null out all of the instruction's operands to see if any operand becomes // dead as we go. - for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { - Value *OpV = I->getOperand(i); - I->setOperand(i, nullptr); + for (Use &OpU : I.operands()) { + Value *OpV = OpU.get(); + OpU.set(nullptr); - if (!OpV->use_empty()) continue; + if (!OpV->use_empty()) + continue; // If the operand is an instruction that became dead as we nulled out the // operand, and if it is 'trivially' dead, delete it in a future loop @@ -426,10 +468,8 @@ llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V, DeadInsts.push_back(OpI); } - I->eraseFromParent(); - } while (!DeadInsts.empty()); - - return true; + I.eraseFromParent(); + } } /// areAllUsesEqual - Check whether the uses of a value are all the same. @@ -481,6 +521,8 @@ simplifyAndDCEInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI) { if (isInstructionTriviallyDead(I, TLI)) { + salvageDebugInfo(*I); + // Null out all of the instruction's operands to see if any operand becomes // dead as we go. for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { @@ -583,7 +625,8 @@ bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, /// /// .. and delete the predecessor corresponding to the '1', this will attempt to /// recursively fold the and to 0. -void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred) { +void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, + DeferredDominance *DDT) { // This only adjusts blocks with PHI nodes. if (!isa<PHINode>(BB->begin())) return; @@ -606,13 +649,18 @@ void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred) { // of the block. if (PhiIt != OldPhiIt) PhiIt = &BB->front(); } + if (DDT) + DDT->deleteEdge(Pred, BB); } /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its /// predecessor is known to have one successor (DestBB!). Eliminate the edge /// between them, moving the instructions in the predecessor into DestBB and /// deleting the predecessor block. -void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) { +void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT, + DeferredDominance *DDT) { + assert(!(DT && DDT) && "Cannot call with both DT and DDT."); + // If BB has single-entry PHI nodes, fold them. while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) { Value *NewVal = PN->getIncomingValue(0); @@ -625,6 +673,24 @@ void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) { BasicBlock *PredBB = DestBB->getSinglePredecessor(); assert(PredBB && "Block doesn't have a single predecessor!"); + bool ReplaceEntryBB = false; + if (PredBB == &DestBB->getParent()->getEntryBlock()) + ReplaceEntryBB = true; + + // Deferred DT update: Collect all the edges that enter PredBB. These + // dominator edges will be redirected to DestBB. + std::vector <DominatorTree::UpdateType> Updates; + if (DDT && !ReplaceEntryBB) { + Updates.reserve(1 + (2 * pred_size(PredBB))); + Updates.push_back({DominatorTree::Delete, PredBB, DestBB}); + for (auto I = pred_begin(PredBB), E = pred_end(PredBB); I != E; ++I) { + Updates.push_back({DominatorTree::Delete, *I, PredBB}); + // This predecessor of PredBB may already have DestBB as a successor. + if (llvm::find(successors(*I), DestBB) == succ_end(*I)) + Updates.push_back({DominatorTree::Insert, *I, DestBB}); + } + } + // Zap anything that took the address of DestBB. Not doing this will give the // address an invalid value. if (DestBB->hasAddressTaken()) { @@ -645,7 +711,7 @@ void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) { // If the PredBB is the entry block of the function, move DestBB up to // become the entry block after we erase PredBB. - if (PredBB == &DestBB->getParent()->getEntryBlock()) + if (ReplaceEntryBB) DestBB->moveAfter(PredBB); if (DT) { @@ -657,8 +723,19 @@ void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) { DT->eraseNode(PredBB); } } - // Nuke BB. - PredBB->eraseFromParent(); + + if (DDT) { + DDT->deleteBB(PredBB); // Deferred deletion of BB. + if (ReplaceEntryBB) + // The entry block was removed and there is no external interface for the + // dominator tree to be notified of this change. In this corner-case we + // recalculate the entire tree. + DDT->recalculate(*(DestBB->getParent())); + else + DDT->applyUpdates(Updates); + } else { + PredBB->eraseFromParent(); // Nuke BB. + } } /// CanMergeValues - Return true if we can choose one of these values to use @@ -675,8 +752,8 @@ static bool CanMergeValues(Value *First, Value *Second) { static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); - DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into " - << Succ->getName() << "\n"); + LLVM_DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into " + << Succ->getName() << "\n"); // Shortcut, if there is only a single predecessor it must be BB and merging // is always safe if (Succ->getSinglePredecessor()) return true; @@ -699,10 +776,11 @@ static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { if (BBPreds.count(IBB) && !CanMergeValues(BBPN->getIncomingValueForBlock(IBB), PN->getIncomingValue(PI))) { - DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " - << Succ->getName() << " is conflicting with " - << BBPN->getName() << " with regard to common predecessor " - << IBB->getName() << "\n"); + LLVM_DEBUG(dbgs() + << "Can't fold, phi node " << PN->getName() << " in " + << Succ->getName() << " is conflicting with " + << BBPN->getName() << " with regard to common predecessor " + << IBB->getName() << "\n"); return false; } } @@ -715,9 +793,10 @@ static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { BasicBlock *IBB = PN->getIncomingBlock(PI); if (BBPreds.count(IBB) && !CanMergeValues(Val, PN->getIncomingValue(PI))) { - DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in " - << Succ->getName() << " is conflicting with regard to common " - << "predecessor " << IBB->getName() << "\n"); + LLVM_DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() + << " in " << Succ->getName() + << " is conflicting with regard to common " + << "predecessor " << IBB->getName() << "\n"); return false; } } @@ -730,7 +809,7 @@ static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { using PredBlockVector = SmallVector<BasicBlock *, 16>; using IncomingValueMap = DenseMap<BasicBlock *, Value *>; -/// \brief Determines the value to use as the phi node input for a block. +/// Determines the value to use as the phi node input for a block. /// /// Select between \p OldVal any value that we know flows from \p BB /// to a particular phi on the basis of which one (if either) is not @@ -759,7 +838,7 @@ static Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB, return OldVal; } -/// \brief Create a map from block to value for the operands of a +/// Create a map from block to value for the operands of a /// given phi. /// /// Create a map from block to value for each non-undef value flowing @@ -778,7 +857,7 @@ static void gatherIncomingValuesToPhi(PHINode *PN, } } -/// \brief Replace the incoming undef values to a phi with the values +/// Replace the incoming undef values to a phi with the values /// from a block-to-value map. /// /// \param PN The phi we are replacing the undefs in. @@ -798,7 +877,7 @@ static void replaceUndefValuesInPhi(PHINode *PN, } } -/// \brief Replace a value flowing from a block to a phi with +/// Replace a value flowing from a block to a phi with /// potentially multiple instances of that value flowing from the /// block's predecessors to the phi. /// @@ -865,7 +944,8 @@ static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB, /// potential side-effect free intrinsics and the branch. If possible, /// eliminate BB by rewriting all the predecessors to branch to the successor /// block and return true. If we can't transform, return false. -bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { +bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, + DeferredDominance *DDT) { assert(BB != &BB->getParent()->getEntryBlock() && "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!"); @@ -904,7 +984,20 @@ bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { } } - DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); + LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); + + std::vector<DominatorTree::UpdateType> Updates; + if (DDT) { + Updates.reserve(1 + (2 * pred_size(BB))); + Updates.push_back({DominatorTree::Delete, BB, Succ}); + // All predecessors of BB will be moved to Succ. + for (auto I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { + Updates.push_back({DominatorTree::Delete, *I, BB}); + // This predecessor of BB may already have Succ as a successor. + if (llvm::find(successors(*I), Succ) == succ_end(*I)) + Updates.push_back({DominatorTree::Insert, *I, Succ}); + } + } if (isa<PHINode>(Succ->begin())) { // If there is more than one pred of succ, and there are PHI nodes in @@ -950,7 +1043,13 @@ bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { // Everything that jumped to BB now goes to Succ. BB->replaceAllUsesWith(Succ); if (!Succ->hasName()) Succ->takeName(BB); - BB->eraseFromParent(); // Delete the old basic block. + + if (DDT) { + DDT->deleteBB(BB); // Deferred deletion of the old basic block. + DDT->applyUpdates(Updates); + } else { + BB->eraseFromParent(); // Delete the old basic block. + } return true; } @@ -1129,6 +1228,31 @@ static bool PhiHasDebugValue(DILocalVariable *DIVar, return false; } +/// Check if the alloc size of \p ValTy is large enough to cover the variable +/// (or fragment of the variable) described by \p DII. +/// +/// This is primarily intended as a helper for the different +/// ConvertDebugDeclareToDebugValue functions. The dbg.declare/dbg.addr that is +/// converted describes an alloca'd variable, so we need to use the +/// alloc size of the value when doing the comparison. E.g. an i1 value will be +/// identified as covering an n-bit fragment, if the store size of i1 is at +/// least n bits. +static bool valueCoversEntireFragment(Type *ValTy, DbgInfoIntrinsic *DII) { + const DataLayout &DL = DII->getModule()->getDataLayout(); + uint64_t ValueSize = DL.getTypeAllocSizeInBits(ValTy); + if (auto FragmentSize = DII->getFragmentSizeInBits()) + return ValueSize >= *FragmentSize; + // We can't always calculate the size of the DI variable (e.g. if it is a + // VLA). Try to use the size of the alloca that the dbg intrinsic describes + // intead. + if (DII->isAddressOfVariable()) + if (auto *AI = dyn_cast_or_null<AllocaInst>(DII->getVariableLocation())) + if (auto FragmentSize = AI->getAllocationSizeInBits(DL)) + return ValueSize >= *FragmentSize; + // Could not determine size of variable. Conservatively return false. + return false; +} + /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic. void llvm::ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, @@ -1139,6 +1263,21 @@ void llvm::ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, auto *DIExpr = DII->getExpression(); Value *DV = SI->getOperand(0); + if (!valueCoversEntireFragment(SI->getValueOperand()->getType(), DII)) { + // FIXME: If storing to a part of the variable described by the dbg.declare, + // then we want to insert a dbg.value for the corresponding fragment. + LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: " + << *DII << '\n'); + // For now, when there is a store to parts of the variable (but we do not + // know which part) we insert an dbg.value instrinsic to indicate that we + // know nothing about the variable's content. + DV = UndefValue::get(DV->getType()); + if (!LdStHasDebugValue(DIVar, DIExpr, SI)) + Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, DII->getDebugLoc(), + SI); + return; + } + // If an argument is zero extended then use argument directly. The ZExt // may be zapped by an optimization pass in future. Argument *ExtendedArg = nullptr; @@ -1182,6 +1321,15 @@ void llvm::ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, if (LdStHasDebugValue(DIVar, DIExpr, LI)) return; + if (!valueCoversEntireFragment(LI->getType(), DII)) { + // FIXME: If only referring to a part of the variable described by the + // dbg.declare, then we want to insert a dbg.value for the corresponding + // fragment. + LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: " + << *DII << '\n'); + return; + } + // We are now tracking the loaded value instead of the address. In the // future if multi-location support is added to the IR, it might be // preferable to keep tracking both the loaded value and the original @@ -1202,6 +1350,15 @@ void llvm::ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, if (PhiHasDebugValue(DIVar, DIExpr, APN)) return; + if (!valueCoversEntireFragment(APN->getType(), DII)) { + // FIXME: If only referring to a part of the variable described by the + // dbg.declare, then we want to insert a dbg.value for the corresponding + // fragment. + LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: " + << *DII << '\n'); + return; + } + BasicBlock *BB = APN->getParent(); auto InsertionPt = BB->getFirstInsertionPt(); @@ -1241,33 +1398,91 @@ bool llvm::LowerDbgDeclare(Function &F) { // stored on the stack, while the dbg.declare can only describe // the stack slot (and at a lexical-scope granularity). Later // passes will attempt to elide the stack slot. - if (AI && !isArray(AI)) { - for (auto &AIUse : AI->uses()) { - User *U = AIUse.getUser(); - if (StoreInst *SI = dyn_cast<StoreInst>(U)) { - if (AIUse.getOperandNo() == 1) - ConvertDebugDeclareToDebugValue(DDI, SI, DIB); - } else if (LoadInst *LI = dyn_cast<LoadInst>(U)) { - ConvertDebugDeclareToDebugValue(DDI, LI, DIB); - } else if (CallInst *CI = dyn_cast<CallInst>(U)) { - // This is a call by-value or some other instruction that - // takes a pointer to the variable. Insert a *value* - // intrinsic that describes the alloca. - DIB.insertDbgValueIntrinsic(AI, DDI->getVariable(), - DDI->getExpression(), DDI->getDebugLoc(), - CI); - } + if (!AI || isArray(AI)) + continue; + + // A volatile load/store means that the alloca can't be elided anyway. + if (llvm::any_of(AI->users(), [](User *U) -> bool { + if (LoadInst *LI = dyn_cast<LoadInst>(U)) + return LI->isVolatile(); + if (StoreInst *SI = dyn_cast<StoreInst>(U)) + return SI->isVolatile(); + return false; + })) + continue; + + for (auto &AIUse : AI->uses()) { + User *U = AIUse.getUser(); + if (StoreInst *SI = dyn_cast<StoreInst>(U)) { + if (AIUse.getOperandNo() == 1) + ConvertDebugDeclareToDebugValue(DDI, SI, DIB); + } else if (LoadInst *LI = dyn_cast<LoadInst>(U)) { + ConvertDebugDeclareToDebugValue(DDI, LI, DIB); + } else if (CallInst *CI = dyn_cast<CallInst>(U)) { + // This is a call by-value or some other instruction that takes a + // pointer to the variable. Insert a *value* intrinsic that describes + // the variable by dereferencing the alloca. + auto *DerefExpr = + DIExpression::append(DDI->getExpression(), dwarf::DW_OP_deref); + DIB.insertDbgValueIntrinsic(AI, DDI->getVariable(), DerefExpr, + DDI->getDebugLoc(), CI); } - DDI->eraseFromParent(); } + DDI->eraseFromParent(); } return true; } +/// Propagate dbg.value intrinsics through the newly inserted PHIs. +void llvm::insertDebugValuesForPHIs(BasicBlock *BB, + SmallVectorImpl<PHINode *> &InsertedPHIs) { + assert(BB && "No BasicBlock to clone dbg.value(s) from."); + if (InsertedPHIs.size() == 0) + return; + + // Map existing PHI nodes to their dbg.values. + ValueToValueMapTy DbgValueMap; + for (auto &I : *BB) { + if (auto DbgII = dyn_cast<DbgInfoIntrinsic>(&I)) { + if (auto *Loc = dyn_cast_or_null<PHINode>(DbgII->getVariableLocation())) + DbgValueMap.insert({Loc, DbgII}); + } + } + if (DbgValueMap.size() == 0) + return; + + // Then iterate through the new PHIs and look to see if they use one of the + // previously mapped PHIs. If so, insert a new dbg.value intrinsic that will + // propagate the info through the new PHI. + LLVMContext &C = BB->getContext(); + for (auto PHI : InsertedPHIs) { + BasicBlock *Parent = PHI->getParent(); + // Avoid inserting an intrinsic into an EH block. + if (Parent->getFirstNonPHI()->isEHPad()) + continue; + auto PhiMAV = MetadataAsValue::get(C, ValueAsMetadata::get(PHI)); + for (auto VI : PHI->operand_values()) { + auto V = DbgValueMap.find(VI); + if (V != DbgValueMap.end()) { + auto *DbgII = cast<DbgInfoIntrinsic>(V->second); + Instruction *NewDbgII = DbgII->clone(); + NewDbgII->setOperand(0, PhiMAV); + auto InsertionPt = Parent->getFirstInsertionPt(); + assert(InsertionPt != Parent->end() && "Ill-formed basic block"); + NewDbgII->insertBefore(&*InsertionPt); + } + } + } +} + /// Finds all intrinsics declaring local variables as living in the memory that /// 'V' points to. This may include a mix of dbg.declare and /// dbg.addr intrinsics. TinyPtrVector<DbgInfoIntrinsic *> llvm::FindDbgAddrUses(Value *V) { + // This function is hot. Check whether the value has any metadata to avoid a + // DenseMap lookup. + if (!V->isUsedByMetadata()) + return {}; auto *L = LocalAsMetadata::getIfExists(V); if (!L) return {}; @@ -1286,6 +1501,10 @@ TinyPtrVector<DbgInfoIntrinsic *> llvm::FindDbgAddrUses(Value *V) { } void llvm::findDbgValues(SmallVectorImpl<DbgValueInst *> &DbgValues, Value *V) { + // This function is hot. Check whether the value has any metadata to avoid a + // DenseMap lookup. + if (!V->isUsedByMetadata()) + return; if (auto *L = LocalAsMetadata::getIfExists(V)) if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L)) for (User *U : MDV->users()) @@ -1293,8 +1512,12 @@ void llvm::findDbgValues(SmallVectorImpl<DbgValueInst *> &DbgValues, Value *V) { DbgValues.push_back(DVI); } -static void findDbgUsers(SmallVectorImpl<DbgInfoIntrinsic *> &DbgUsers, - Value *V) { +void llvm::findDbgUsers(SmallVectorImpl<DbgInfoIntrinsic *> &DbgUsers, + Value *V) { + // This function is hot. Check whether the value has any metadata to avoid a + // DenseMap lookup. + if (!V->isUsedByMetadata()) + return; if (auto *L = LocalAsMetadata::getIfExists(V)) if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L)) for (User *U : MDV->users()) @@ -1312,11 +1535,11 @@ bool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress, auto *DIExpr = DII->getExpression(); assert(DIVar && "Missing variable"); DIExpr = DIExpression::prepend(DIExpr, DerefBefore, Offset, DerefAfter); - // Insert llvm.dbg.declare immediately after InsertBefore, and remove old + // Insert llvm.dbg.declare immediately before InsertBefore, and remove old // llvm.dbg.declare. Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, InsertBefore); if (DII == InsertBefore) - InsertBefore = &*std::next(InsertBefore->getIterator()); + InsertBefore = InsertBefore->getNextNode(); DII->eraseFromParent(); } return !DbgAddrs.empty(); @@ -1368,66 +1591,293 @@ void llvm::replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, } } -void llvm::salvageDebugInfo(Instruction &I) { - SmallVector<DbgValueInst *, 1> DbgValues; +/// Wrap \p V in a ValueAsMetadata instance. +static MetadataAsValue *wrapValueInMetadata(LLVMContext &C, Value *V) { + return MetadataAsValue::get(C, ValueAsMetadata::get(V)); +} + +bool llvm::salvageDebugInfo(Instruction &I) { + SmallVector<DbgInfoIntrinsic *, 1> DbgUsers; + findDbgUsers(DbgUsers, &I); + if (DbgUsers.empty()) + return false; + auto &M = *I.getModule(); + auto &DL = M.getDataLayout(); + auto &Ctx = I.getContext(); + auto wrapMD = [&](Value *V) { return wrapValueInMetadata(Ctx, V); }; - auto wrapMD = [&](Value *V) { - return MetadataAsValue::get(I.getContext(), ValueAsMetadata::get(V)); + auto doSalvage = [&](DbgInfoIntrinsic *DII, SmallVectorImpl<uint64_t> &Ops) { + auto *DIExpr = DII->getExpression(); + if (!Ops.empty()) { + // Do not add DW_OP_stack_value for DbgDeclare and DbgAddr, because they + // are implicitly pointing out the value as a DWARF memory location + // description. + bool WithStackValue = isa<DbgValueInst>(DII); + DIExpr = DIExpression::prependOpcodes(DIExpr, Ops, WithStackValue); + } + DII->setOperand(0, wrapMD(I.getOperand(0))); + DII->setOperand(2, MetadataAsValue::get(Ctx, DIExpr)); + LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n'); }; - auto applyOffset = [&](DbgValueInst *DVI, uint64_t Offset) { - auto *DIExpr = DVI->getExpression(); - DIExpr = DIExpression::prepend(DIExpr, DIExpression::NoDeref, Offset, - DIExpression::NoDeref, - DIExpression::WithStackValue); - DVI->setOperand(0, wrapMD(I.getOperand(0))); - DVI->setOperand(2, MetadataAsValue::get(I.getContext(), DIExpr)); - DEBUG(dbgs() << "SALVAGE: " << *DVI << '\n'); + auto applyOffset = [&](DbgInfoIntrinsic *DII, uint64_t Offset) { + SmallVector<uint64_t, 8> Ops; + DIExpression::appendOffset(Ops, Offset); + doSalvage(DII, Ops); }; - if (isa<BitCastInst>(&I) || isa<IntToPtrInst>(&I)) { - // Bitcasts are entirely irrelevant for debug info. Rewrite dbg.value, - // dbg.addr, and dbg.declare to use the cast's source. - SmallVector<DbgInfoIntrinsic *, 1> DbgUsers; - findDbgUsers(DbgUsers, &I); + auto applyOps = [&](DbgInfoIntrinsic *DII, + std::initializer_list<uint64_t> Opcodes) { + SmallVector<uint64_t, 8> Ops(Opcodes); + doSalvage(DII, Ops); + }; + + if (auto *CI = dyn_cast<CastInst>(&I)) { + if (!CI->isNoopCast(DL)) + return false; + + // No-op casts are irrelevant for debug info. + MetadataAsValue *CastSrc = wrapMD(I.getOperand(0)); for (auto *DII : DbgUsers) { - DII->setOperand(0, wrapMD(I.getOperand(0))); - DEBUG(dbgs() << "SALVAGE: " << *DII << '\n'); + DII->setOperand(0, CastSrc); + LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n'); } + return true; } else if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) { - findDbgValues(DbgValues, &I); - for (auto *DVI : DbgValues) { - unsigned BitWidth = - M.getDataLayout().getPointerSizeInBits(GEP->getPointerAddressSpace()); - APInt Offset(BitWidth, 0); - // Rewrite a constant GEP into a DIExpression. Since we are performing - // arithmetic to compute the variable's *value* in the DIExpression, we - // need to mark the expression with a DW_OP_stack_value. - if (GEP->accumulateConstantOffset(M.getDataLayout(), Offset)) - // GEP offsets are i32 and thus always fit into an int64_t. - applyOffset(DVI, Offset.getSExtValue()); - } + unsigned BitWidth = + M.getDataLayout().getIndexSizeInBits(GEP->getPointerAddressSpace()); + // Rewrite a constant GEP into a DIExpression. Since we are performing + // arithmetic to compute the variable's *value* in the DIExpression, we + // need to mark the expression with a DW_OP_stack_value. + APInt Offset(BitWidth, 0); + if (GEP->accumulateConstantOffset(M.getDataLayout(), Offset)) + for (auto *DII : DbgUsers) + applyOffset(DII, Offset.getSExtValue()); + return true; } else if (auto *BI = dyn_cast<BinaryOperator>(&I)) { - if (BI->getOpcode() == Instruction::Add) - if (auto *ConstInt = dyn_cast<ConstantInt>(I.getOperand(1))) - if (ConstInt->getBitWidth() <= 64) { - APInt Offset = ConstInt->getValue(); - findDbgValues(DbgValues, &I); - for (auto *DVI : DbgValues) - applyOffset(DVI, Offset.getSExtValue()); - } + // Rewrite binary operations with constant integer operands. + auto *ConstInt = dyn_cast<ConstantInt>(I.getOperand(1)); + if (!ConstInt || ConstInt->getBitWidth() > 64) + return false; + + uint64_t Val = ConstInt->getSExtValue(); + for (auto *DII : DbgUsers) { + switch (BI->getOpcode()) { + case Instruction::Add: + applyOffset(DII, Val); + break; + case Instruction::Sub: + applyOffset(DII, -int64_t(Val)); + break; + case Instruction::Mul: + applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_mul}); + break; + case Instruction::SDiv: + applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_div}); + break; + case Instruction::SRem: + applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_mod}); + break; + case Instruction::Or: + applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_or}); + break; + case Instruction::And: + applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_and}); + break; + case Instruction::Xor: + applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_xor}); + break; + case Instruction::Shl: + applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_shl}); + break; + case Instruction::LShr: + applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_shr}); + break; + case Instruction::AShr: + applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_shra}); + break; + default: + // TODO: Salvage constants from each kind of binop we know about. + return false; + } + } + return true; } else if (isa<LoadInst>(&I)) { - findDbgValues(DbgValues, &I); - for (auto *DVI : DbgValues) { + MetadataAsValue *AddrMD = wrapMD(I.getOperand(0)); + for (auto *DII : DbgUsers) { // Rewrite the load into DW_OP_deref. - auto *DIExpr = DVI->getExpression(); + auto *DIExpr = DII->getExpression(); DIExpr = DIExpression::prepend(DIExpr, DIExpression::WithDeref); - DVI->setOperand(0, wrapMD(I.getOperand(0))); - DVI->setOperand(2, MetadataAsValue::get(I.getContext(), DIExpr)); - DEBUG(dbgs() << "SALVAGE: " << *DVI << '\n'); + DII->setOperand(0, AddrMD); + DII->setOperand(2, MetadataAsValue::get(Ctx, DIExpr)); + LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n'); + } + return true; + } + return false; +} + +/// A replacement for a dbg.value expression. +using DbgValReplacement = Optional<DIExpression *>; + +/// Point debug users of \p From to \p To using exprs given by \p RewriteExpr, +/// possibly moving/deleting users to prevent use-before-def. Returns true if +/// changes are made. +static bool rewriteDebugUsers( + Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT, + function_ref<DbgValReplacement(DbgInfoIntrinsic &DII)> RewriteExpr) { + // Find debug users of From. + SmallVector<DbgInfoIntrinsic *, 1> Users; + findDbgUsers(Users, &From); + if (Users.empty()) + return false; + + // Prevent use-before-def of To. + bool Changed = false; + SmallPtrSet<DbgInfoIntrinsic *, 1> DeleteOrSalvage; + if (isa<Instruction>(&To)) { + bool DomPointAfterFrom = From.getNextNonDebugInstruction() == &DomPoint; + + for (auto *DII : Users) { + // It's common to see a debug user between From and DomPoint. Move it + // after DomPoint to preserve the variable update without any reordering. + if (DomPointAfterFrom && DII->getNextNonDebugInstruction() == &DomPoint) { + LLVM_DEBUG(dbgs() << "MOVE: " << *DII << '\n'); + DII->moveAfter(&DomPoint); + Changed = true; + + // Users which otherwise aren't dominated by the replacement value must + // be salvaged or deleted. + } else if (!DT.dominates(&DomPoint, DII)) { + DeleteOrSalvage.insert(DII); + } } } + + // Update debug users without use-before-def risk. + for (auto *DII : Users) { + if (DeleteOrSalvage.count(DII)) + continue; + + LLVMContext &Ctx = DII->getContext(); + DbgValReplacement DVR = RewriteExpr(*DII); + if (!DVR) + continue; + + DII->setOperand(0, wrapValueInMetadata(Ctx, &To)); + DII->setOperand(2, MetadataAsValue::get(Ctx, *DVR)); + LLVM_DEBUG(dbgs() << "REWRITE: " << *DII << '\n'); + Changed = true; + } + + if (!DeleteOrSalvage.empty()) { + // Try to salvage the remaining debug users. + Changed |= salvageDebugInfo(From); + + // Delete the debug users which weren't salvaged. + for (auto *DII : DeleteOrSalvage) { + if (DII->getVariableLocation() == &From) { + LLVM_DEBUG(dbgs() << "Erased UseBeforeDef: " << *DII << '\n'); + DII->eraseFromParent(); + Changed = true; + } + } + } + + return Changed; +} + +/// Check if a bitcast between a value of type \p FromTy to type \p ToTy would +/// losslessly preserve the bits and semantics of the value. This predicate is +/// symmetric, i.e swapping \p FromTy and \p ToTy should give the same result. +/// +/// Note that Type::canLosslesslyBitCastTo is not suitable here because it +/// allows semantically unequivalent bitcasts, such as <2 x i64> -> <4 x i32>, +/// and also does not allow lossless pointer <-> integer conversions. +static bool isBitCastSemanticsPreserving(const DataLayout &DL, Type *FromTy, + Type *ToTy) { + // Trivially compatible types. + if (FromTy == ToTy) + return true; + + // Handle compatible pointer <-> integer conversions. + if (FromTy->isIntOrPtrTy() && ToTy->isIntOrPtrTy()) { + bool SameSize = DL.getTypeSizeInBits(FromTy) == DL.getTypeSizeInBits(ToTy); + bool LosslessConversion = !DL.isNonIntegralPointerType(FromTy) && + !DL.isNonIntegralPointerType(ToTy); + return SameSize && LosslessConversion; + } + + // TODO: This is not exhaustive. + return false; +} + +bool llvm::replaceAllDbgUsesWith(Instruction &From, Value &To, + Instruction &DomPoint, DominatorTree &DT) { + // Exit early if From has no debug users. + if (!From.isUsedByMetadata()) + return false; + + assert(&From != &To && "Can't replace something with itself"); + + Type *FromTy = From.getType(); + Type *ToTy = To.getType(); + + auto Identity = [&](DbgInfoIntrinsic &DII) -> DbgValReplacement { + return DII.getExpression(); + }; + + // Handle no-op conversions. + Module &M = *From.getModule(); + const DataLayout &DL = M.getDataLayout(); + if (isBitCastSemanticsPreserving(DL, FromTy, ToTy)) + return rewriteDebugUsers(From, To, DomPoint, DT, Identity); + + // Handle integer-to-integer widening and narrowing. + // FIXME: Use DW_OP_convert when it's available everywhere. + if (FromTy->isIntegerTy() && ToTy->isIntegerTy()) { + uint64_t FromBits = FromTy->getPrimitiveSizeInBits(); + uint64_t ToBits = ToTy->getPrimitiveSizeInBits(); + assert(FromBits != ToBits && "Unexpected no-op conversion"); + + // When the width of the result grows, assume that a debugger will only + // access the low `FromBits` bits when inspecting the source variable. + if (FromBits < ToBits) + return rewriteDebugUsers(From, To, DomPoint, DT, Identity); + + // The width of the result has shrunk. Use sign/zero extension to describe + // the source variable's high bits. + auto SignOrZeroExt = [&](DbgInfoIntrinsic &DII) -> DbgValReplacement { + DILocalVariable *Var = DII.getVariable(); + + // Without knowing signedness, sign/zero extension isn't possible. + auto Signedness = Var->getSignedness(); + if (!Signedness) + return None; + + bool Signed = *Signedness == DIBasicType::Signedness::Signed; + + if (!Signed) { + // In the unsigned case, assume that a debugger will initialize the + // high bits to 0 and do a no-op conversion. + return Identity(DII); + } else { + // In the signed case, the high bits are given by sign extension, i.e: + // (To >> (ToBits - 1)) * ((2 ^ FromBits) - 1) + // Calculate the high bits and OR them together with the low bits. + SmallVector<uint64_t, 8> Ops({dwarf::DW_OP_dup, dwarf::DW_OP_constu, + (ToBits - 1), dwarf::DW_OP_shr, + dwarf::DW_OP_lit0, dwarf::DW_OP_not, + dwarf::DW_OP_mul, dwarf::DW_OP_or}); + return DIExpression::appendToStack(DII.getExpression(), Ops); + } + }; + return rewriteDebugUsers(From, To, DomPoint, DT, SignOrZeroExt); + } + + // TODO: Floating-point conversions, vectors. + return false; } unsigned llvm::removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB) { @@ -1452,13 +1902,19 @@ unsigned llvm::removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB) { } unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap, - bool PreserveLCSSA) { + bool PreserveLCSSA, DeferredDominance *DDT) { BasicBlock *BB = I->getParent(); + std::vector <DominatorTree::UpdateType> Updates; + // Loop over all of the successors, removing BB's entry from any PHI // nodes. - for (BasicBlock *Successor : successors(BB)) + if (DDT) + Updates.reserve(BB->getTerminator()->getNumSuccessors()); + for (BasicBlock *Successor : successors(BB)) { Successor->removePredecessor(BB, PreserveLCSSA); - + if (DDT) + Updates.push_back({DominatorTree::Delete, BB, Successor}); + } // Insert a call to llvm.trap right before this. This turns the undefined // behavior into a hard fail instead of falling through into random code. if (UseLLVMTrap) { @@ -1478,11 +1934,13 @@ unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap, BB->getInstList().erase(BBI++); ++NumInstrsRemoved; } + if (DDT) + DDT->applyUpdates(Updates); return NumInstrsRemoved; } /// changeToCall - Convert the specified invoke into a normal call. -static void changeToCall(InvokeInst *II) { +static void changeToCall(InvokeInst *II, DeferredDominance *DDT = nullptr) { SmallVector<Value*, 8> Args(II->arg_begin(), II->arg_end()); SmallVector<OperandBundleDef, 1> OpBundles; II->getOperandBundlesAsDefs(OpBundles); @@ -1495,11 +1953,16 @@ static void changeToCall(InvokeInst *II) { II->replaceAllUsesWith(NewCall); // Follow the call by a branch to the normal destination. - BranchInst::Create(II->getNormalDest(), II); + BasicBlock *NormalDestBB = II->getNormalDest(); + BranchInst::Create(NormalDestBB, II); // Update PHI nodes in the unwind destination - II->getUnwindDest()->removePredecessor(II->getParent()); + BasicBlock *BB = II->getParent(); + BasicBlock *UnwindDestBB = II->getUnwindDest(); + UnwindDestBB->removePredecessor(BB); II->eraseFromParent(); + if (DDT) + DDT->deleteEdge(BB, UnwindDestBB); } BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI, @@ -1540,7 +2003,8 @@ BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI, } static bool markAliveBlocks(Function &F, - SmallPtrSetImpl<BasicBlock*> &Reachable) { + SmallPtrSetImpl<BasicBlock*> &Reachable, + DeferredDominance *DDT = nullptr) { SmallVector<BasicBlock*, 128> Worklist; BasicBlock *BB = &F.front(); Worklist.push_back(BB); @@ -1553,41 +2017,44 @@ static bool markAliveBlocks(Function &F, // instructions into LLVM unreachable insts. The instruction combining pass // canonicalizes unreachable insts into stores to null or undef. for (Instruction &I : *BB) { - // Assumptions that are known to be false are equivalent to unreachable. - // Also, if the condition is undefined, then we make the choice most - // beneficial to the optimizer, and choose that to also be unreachable. - if (auto *II = dyn_cast<IntrinsicInst>(&I)) { - if (II->getIntrinsicID() == Intrinsic::assume) { - if (match(II->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) { - // Don't insert a call to llvm.trap right before the unreachable. - changeToUnreachable(II, false); - Changed = true; - break; - } - } - - if (II->getIntrinsicID() == Intrinsic::experimental_guard) { - // A call to the guard intrinsic bails out of the current compilation - // unit if the predicate passed to it is false. If the predicate is a - // constant false, then we know the guard will bail out of the current - // compile unconditionally, so all code following it is dead. - // - // Note: unlike in llvm.assume, it is not "obviously profitable" for - // guards to treat `undef` as `false` since a guard on `undef` can - // still be useful for widening. - if (match(II->getArgOperand(0), m_Zero())) - if (!isa<UnreachableInst>(II->getNextNode())) { - changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/ false); + if (auto *CI = dyn_cast<CallInst>(&I)) { + Value *Callee = CI->getCalledValue(); + // Handle intrinsic calls. + if (Function *F = dyn_cast<Function>(Callee)) { + auto IntrinsicID = F->getIntrinsicID(); + // Assumptions that are known to be false are equivalent to + // unreachable. Also, if the condition is undefined, then we make the + // choice most beneficial to the optimizer, and choose that to also be + // unreachable. + if (IntrinsicID == Intrinsic::assume) { + if (match(CI->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) { + // Don't insert a call to llvm.trap right before the unreachable. + changeToUnreachable(CI, false, false, DDT); Changed = true; break; } - } - } - - if (auto *CI = dyn_cast<CallInst>(&I)) { - Value *Callee = CI->getCalledValue(); - if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) { - changeToUnreachable(CI, /*UseLLVMTrap=*/false); + } else if (IntrinsicID == Intrinsic::experimental_guard) { + // A call to the guard intrinsic bails out of the current + // compilation unit if the predicate passed to it is false. If the + // predicate is a constant false, then we know the guard will bail + // out of the current compile unconditionally, so all code following + // it is dead. + // + // Note: unlike in llvm.assume, it is not "obviously profitable" for + // guards to treat `undef` as `false` since a guard on `undef` can + // still be useful for widening. + if (match(CI->getArgOperand(0), m_Zero())) + if (!isa<UnreachableInst>(CI->getNextNode())) { + changeToUnreachable(CI->getNextNode(), /*UseLLVMTrap=*/false, + false, DDT); + Changed = true; + break; + } + } + } else if ((isa<ConstantPointerNull>(Callee) && + !NullPointerIsDefined(CI->getFunction())) || + isa<UndefValue>(Callee)) { + changeToUnreachable(CI, /*UseLLVMTrap=*/false, false, DDT); Changed = true; break; } @@ -1597,17 +2064,16 @@ static bool markAliveBlocks(Function &F, // though. if (!isa<UnreachableInst>(CI->getNextNode())) { // Don't insert a call to llvm.trap right before the unreachable. - changeToUnreachable(CI->getNextNode(), false); + changeToUnreachable(CI->getNextNode(), false, false, DDT); Changed = true; } break; } - } + } else if (auto *SI = dyn_cast<StoreInst>(&I)) { + // Store to undef and store to null are undefined and used to signal + // that they should be changed to unreachable by passes that can't + // modify the CFG. - // Store to undef and store to null are undefined and used to signal that - // they should be changed to unreachable by passes that can't modify the - // CFG. - if (auto *SI = dyn_cast<StoreInst>(&I)) { // Don't touch volatile stores. if (SI->isVolatile()) continue; @@ -1615,8 +2081,9 @@ static bool markAliveBlocks(Function &F, if (isa<UndefValue>(Ptr) || (isa<ConstantPointerNull>(Ptr) && - SI->getPointerAddressSpace() == 0)) { - changeToUnreachable(SI, true); + !NullPointerIsDefined(SI->getFunction(), + SI->getPointerAddressSpace()))) { + changeToUnreachable(SI, true, false, DDT); Changed = true; break; } @@ -1627,17 +2094,23 @@ static bool markAliveBlocks(Function &F, if (auto *II = dyn_cast<InvokeInst>(Terminator)) { // Turn invokes that call 'nounwind' functions into ordinary calls. Value *Callee = II->getCalledValue(); - if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) { - changeToUnreachable(II, true); + if ((isa<ConstantPointerNull>(Callee) && + !NullPointerIsDefined(BB->getParent())) || + isa<UndefValue>(Callee)) { + changeToUnreachable(II, true, false, DDT); Changed = true; } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) { if (II->use_empty() && II->onlyReadsMemory()) { // jump to the normal destination branch. - BranchInst::Create(II->getNormalDest(), II); - II->getUnwindDest()->removePredecessor(II->getParent()); + BasicBlock *NormalDestBB = II->getNormalDest(); + BasicBlock *UnwindDestBB = II->getUnwindDest(); + BranchInst::Create(NormalDestBB, II); + UnwindDestBB->removePredecessor(II->getParent()); II->eraseFromParent(); + if (DDT) + DDT->deleteEdge(BB, UnwindDestBB); } else - changeToCall(II); + changeToCall(II, DDT); Changed = true; } } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) { @@ -1683,7 +2156,7 @@ static bool markAliveBlocks(Function &F, } } - Changed |= ConstantFoldTerminator(BB, true); + Changed |= ConstantFoldTerminator(BB, true, nullptr, DDT); for (BasicBlock *Successor : successors(BB)) if (Reachable.insert(Successor).second) Worklist.push_back(Successor); @@ -1691,11 +2164,11 @@ static bool markAliveBlocks(Function &F, return Changed; } -void llvm::removeUnwindEdge(BasicBlock *BB) { +void llvm::removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT) { TerminatorInst *TI = BB->getTerminator(); if (auto *II = dyn_cast<InvokeInst>(TI)) { - changeToCall(II); + changeToCall(II, DDT); return; } @@ -1723,15 +2196,18 @@ void llvm::removeUnwindEdge(BasicBlock *BB) { UnwindDest->removePredecessor(BB); TI->replaceAllUsesWith(NewTI); TI->eraseFromParent(); + if (DDT) + DDT->deleteEdge(BB, UnwindDest); } /// removeUnreachableBlocks - Remove blocks that are not reachable, even /// if they are in a dead cycle. Return true if a change was made, false /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo /// after modifying the CFG. -bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI) { +bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI, + DeferredDominance *DDT) { SmallPtrSet<BasicBlock*, 16> Reachable; - bool Changed = markAliveBlocks(F, Reachable); + bool Changed = markAliveBlocks(F, Reachable, DDT); // If there are unreachable blocks in the CFG... if (Reachable.size() == F.size()) @@ -1741,25 +2217,39 @@ bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI) { NumRemoved += F.size()-Reachable.size(); // Loop over all of the basic blocks that are not reachable, dropping all of - // their internal references... - for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) { - if (Reachable.count(&*BB)) + // their internal references. Update DDT and LVI if available. + std::vector <DominatorTree::UpdateType> Updates; + for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ++I) { + auto *BB = &*I; + if (Reachable.count(BB)) continue; - - for (BasicBlock *Successor : successors(&*BB)) + for (BasicBlock *Successor : successors(BB)) { if (Reachable.count(Successor)) - Successor->removePredecessor(&*BB); + Successor->removePredecessor(BB); + if (DDT) + Updates.push_back({DominatorTree::Delete, BB, Successor}); + } if (LVI) - LVI->eraseBlock(&*BB); + LVI->eraseBlock(BB); BB->dropAllReferences(); } - for (Function::iterator I = ++F.begin(); I != F.end();) - if (!Reachable.count(&*I)) - I = F.getBasicBlockList().erase(I); - else + for (Function::iterator I = ++F.begin(); I != F.end();) { + auto *BB = &*I; + if (Reachable.count(BB)) { ++I; + continue; + } + if (DDT) { + DDT->deleteBB(BB); // deferred deletion of BB. + ++I; + } else { + I = F.getBasicBlockList().erase(I); + } + } + if (DDT) + DDT->applyUpdates(Updates); return true; } @@ -1852,8 +2342,8 @@ static unsigned replaceDominatedUsesWith(Value *From, Value *To, if (!Dominates(Root, U)) continue; U.set(To); - DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as " - << *To << " in " << *U << "\n"); + LLVM_DEBUG(dbgs() << "Replace dominated use of '" << From->getName() + << "' as " << *To << " in " << *U << "\n"); ++Count; } return Count; @@ -1957,7 +2447,7 @@ void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, if (!NewTy->isPointerTy()) return; - unsigned BitWidth = DL.getTypeSizeInBits(NewTy); + unsigned BitWidth = DL.getIndexTypeSizeInBits(NewTy); if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) { MDNode *NN = MDNode::get(OldLI.getContext(), None); NewLI.setMetadata(LLVMContext::MD_nonnull, NN); @@ -2269,7 +2759,7 @@ bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) { // Static allocas (constant size in the entry block) are handled by // prologue/epilogue insertion so they're free anyway. We definitely don't // want to make them non-constant. - return !dyn_cast<AllocaInst>(I)->isStaticAlloca(); + return !cast<AllocaInst>(I)->isStaticAlloca(); case Instruction::GetElementPtr: if (OpIdx == 0) return true; |