X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FLocal.cpp;h=391ed685766852d6b6b472cce16217f849550a09;hp=78217c8efa3dd894f9bf73a7b7cf44640d34c080;hb=fd947f33ba2b1260d7496776c96d5674ee3c9ef4;hpb=d5b7f2b62cdb3a14162c57e27c06a27dda9a78c4 diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp index 78217c8efa3..391ed685766 100644 --- a/lib/Transforms/Utils/Local.cpp +++ b/lib/Transforms/Utils/Local.cpp @@ -14,18 +14,24 @@ #include "llvm/Transforms/Utils/Local.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/Hashing.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" -#include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/EHPersonalities.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/ValueTracking.h" -#include "llvm/DIBuilder.h" -#include "llvm/DebugInfo.h" +#include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" +#include "llvm/IR/DIBuilder.h" #include "llvm/IR/DataLayout.h" +#include "llvm/IR/DebugInfo.h" #include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/GlobalAlias.h" #include "llvm/IR/GlobalVariable.h" #include "llvm/IR/IRBuilder.h" @@ -35,14 +41,14 @@ #include "llvm/IR/MDBuilder.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/Operator.h" -#include "llvm/Support/CFG.h" +#include "llvm/IR/ValueHandle.h" #include "llvm/Support/Debug.h" -#include "llvm/Support/GetElementPtrTypeIterator.h" #include "llvm/Support/MathExtras.h" -#include "llvm/Support/ValueHandle.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; +#define DEBUG_TYPE "local" + STATISTIC(NumRemoved, "Number of unreachable basic blocks removed"); //===----------------------------------------------------------------------===// @@ -108,11 +114,17 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, } if (SwitchInst *SI = dyn_cast(T)) { - // If we are switching on a constant, we can convert the switch into a - // single branch instruction! + // If we are switching on a constant, we can convert the switch to an + // unconditional branch. ConstantInt *CI = dyn_cast(SI->getCondition()); - BasicBlock *TheOnlyDest = SI->getDefaultDest(); - BasicBlock *DefaultDest = TheOnlyDest; + BasicBlock *DefaultDest = SI->getDefaultDest(); + BasicBlock *TheOnlyDest = DefaultDest; + + // If the default is unreachable, ignore it when searching for TheOnlyDest. + if (isa(DefaultDest->getFirstNonPHIOrDbg()) && + SI->getNumCases() > 0) { + TheOnlyDest = SI->case_begin().getCaseSuccessor(); + } // Figure out which case it goes to. for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); @@ -126,14 +138,17 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, // Check to see if this branch is going to the same place as the default // dest. If so, eliminate it as an explicit compare. if (i.getCaseSuccessor() == DefaultDest) { - MDNode* MD = SI->getMetadata(LLVMContext::MD_prof); - // MD should have 2 + NumCases operands. - if (MD && MD->getNumOperands() == 2 + SI->getNumCases()) { + MDNode *MD = SI->getMetadata(LLVMContext::MD_prof); + unsigned NCases = SI->getNumCases(); + // Fold the case metadata into the default if there will be any branches + // left, unless the metadata doesn't match the switch. + if (NCases > 1 && MD && MD->getNumOperands() == 2 + NCases) { // Collect branch weights into a vector. SmallVector Weights; for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e; ++MD_i) { - ConstantInt* CI = dyn_cast(MD->getOperand(MD_i)); + ConstantInt *CI = + mdconst::dyn_extract(MD->getOperand(MD_i)); assert(CI); Weights.push_back(CI->getValue().getZExtValue()); } @@ -157,7 +172,7 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, // Otherwise, check to see if the switch only branches to one destination. // We do this by reseting "TheOnlyDest" to null when we find two non-equal // destinations. - if (i.getCaseSuccessor() != TheOnlyDest) TheOnlyDest = 0; + if (i.getCaseSuccessor() != TheOnlyDest) TheOnlyDest = nullptr; } if (CI && !TheOnlyDest) { @@ -174,11 +189,10 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, BasicBlock *BB = SI->getParent(); // Remove entries from PHI nodes which we no longer branch to... - for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { + for (BasicBlock *Succ : SI->successors()) { // Found case matching a constant operand? - BasicBlock *Succ = SI->getSuccessor(i); if (Succ == TheOnlyDest) - TheOnlyDest = 0; // Don't modify the first branch to TheOnlyDest + TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest else Succ->removePredecessor(BB); } @@ -202,10 +216,12 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, BranchInst *NewBr = Builder.CreateCondBr(Cond, FirstCase.getCaseSuccessor(), SI->getDefaultDest()); - MDNode* MD = SI->getMetadata(LLVMContext::MD_prof); + MDNode *MD = SI->getMetadata(LLVMContext::MD_prof); if (MD && MD->getNumOperands() == 3) { - ConstantInt *SICase = dyn_cast(MD->getOperand(2)); - ConstantInt *SIDef = dyn_cast(MD->getOperand(1)); + ConstantInt *SICase = + mdconst::dyn_extract(MD->getOperand(2)); + ConstantInt *SIDef = + mdconst::dyn_extract(MD->getOperand(1)); assert(SICase && SIDef); // The TrueWeight should be the weight for the single case of SI. NewBr->setMetadata(LLVMContext::MD_prof, @@ -214,6 +230,11 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, SIDef->getValue().getZExtValue())); } + // Update make.implicit metadata to the newly-created conditional branch. + MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit); + if (MakeImplicitMD) + NewBr->setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD); + // Delete the old switch. SI->eraseFromParent(); return true; @@ -231,7 +252,7 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { if (IBI->getDestination(i) == TheOnlyDest) - TheOnlyDest = 0; + TheOnlyDest = nullptr; else IBI->getDestination(i)->removePredecessor(IBI->getParent()); } @@ -267,8 +288,9 @@ bool llvm::isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI) { if (!I->use_empty() || isa(I)) return false; - // We don't want the landingpad instruction removed by anything this general. - if (isa(I)) + // We don't want the landingpad-like instructions removed by anything this + // general. + if (I->isEHPad()) return false; // We don't want debug info removed by anything this general, unless @@ -297,6 +319,14 @@ bool llvm::isInstructionTriviallyDead(Instruction *I, if (II->getIntrinsicID() == Intrinsic::lifetime_start || II->getIntrinsicID() == Intrinsic::lifetime_end) return isa(II->getArgOperand(1)); + + // Assumptions are dead if their condition is trivially true. + if (II->getIntrinsicID() == Intrinsic::assume) { + if (ConstantInt *Cond = dyn_cast(II->getArgOperand(0))) + return !Cond->isZero(); + + return false; + } } if (isAllocLikeFn(I, TLI)) return true; @@ -329,7 +359,7 @@ llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V, // dead as we go. for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { Value *OpV = I->getOperand(i); - I->setOperand(i, 0); + I->setOperand(i, nullptr); if (!OpV->use_empty()) continue; @@ -352,8 +382,8 @@ llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V, /// true when there are no uses or multiple uses that all refer to the same /// value. static bool areAllUsesEqual(Instruction *I) { - Value::use_iterator UI = I->use_begin(); - Value::use_iterator UE = I->use_end(); + Value::user_iterator UI = I->user_begin(); + Value::user_iterator UE = I->user_end(); if (UI == UE) return true; @@ -374,13 +404,13 @@ bool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI) { SmallPtrSet Visited; for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects(); - I = cast(*I->use_begin())) { + I = cast(*I->user_begin())) { if (I->use_empty()) return RecursivelyDeleteTriviallyDeadInstructions(I, TLI); // If we find an instruction more than once, we're on a cycle that // won't prove fruitful. - if (!Visited.insert(I)) { + if (!Visited.insert(I).second) { // Break the cycle and delete the instruction and its operands. I->replaceAllUsesWith(UndefValue::get(I->getType())); (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI); @@ -390,38 +420,85 @@ bool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN, return false; } +static bool +simplifyAndDCEInstruction(Instruction *I, + SmallSetVector &WorkList, + const DataLayout &DL, + const TargetLibraryInfo *TLI) { + if (isInstructionTriviallyDead(I, TLI)) { + // 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); + + if (!OpV->use_empty() || I == OpV) + 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 + // iteration. + if (Instruction *OpI = dyn_cast(OpV)) + if (isInstructionTriviallyDead(OpI, TLI)) + WorkList.insert(OpI); + } + + I->eraseFromParent(); + + return true; + } + + if (Value *SimpleV = SimplifyInstruction(I, DL)) { + // Add the users to the worklist. CAREFUL: an instruction can use itself, + // in the case of a phi node. + for (User *U : I->users()) + if (U != I) + WorkList.insert(cast(U)); + + // Replace the instruction with its simplified value. + I->replaceAllUsesWith(SimpleV); + I->eraseFromParent(); + return true; + } + return false; +} + /// SimplifyInstructionsInBlock - Scan the specified basic block and try to /// simplify any instructions in it and recursively delete dead instructions. /// /// This returns true if it changed the code, note that it can delete /// instructions in other blocks as well in this block. -bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, const DataLayout *TD, +bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI) { bool MadeChange = false; + const DataLayout &DL = BB->getModule()->getDataLayout(); #ifndef NDEBUG // In debug builds, ensure that the terminator of the block is never replaced // or deleted by these simplifications. The idea of simplification is that it // cannot introduce new instructions, and there is no way to replace the // terminator of a block without introducing a new instruction. - AssertingVH TerminatorVH(--BB->end()); + AssertingVH TerminatorVH(&BB->back()); #endif - for (BasicBlock::iterator BI = BB->begin(), E = --BB->end(); BI != E; ) { + SmallSetVector WorkList; + // Iterate over the original function, only adding insts to the worklist + // if they actually need to be revisited. This avoids having to pre-init + // the worklist with the entire function's worth of instructions. + for (BasicBlock::iterator BI = BB->begin(), E = std::prev(BB->end()); BI != E;) { assert(!BI->isTerminator()); - Instruction *Inst = BI++; + Instruction *I = &*BI; + ++BI; - WeakVH BIHandle(BI); - if (recursivelySimplifyInstruction(Inst, TD, TLI)) { - MadeChange = true; - if (BIHandle != BI) - BI = BB->begin(); - continue; - } + // We're visiting this instruction now, so make sure it's not in the + // worklist from an earlier visit. + if (!WorkList.count(I)) + MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI); + } - MadeChange |= RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI); - if (BIHandle != BI) - BI = BB->begin(); + while (!WorkList.empty()) { + Instruction *I = WorkList.pop_back_val(); + MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI); } return MadeChange; } @@ -442,8 +519,7 @@ bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, const DataLayout *TD, /// /// .. 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, - DataLayout *TD) { +void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred) { // This only adjusts blocks with PHI nodes. if (!isa(BB->begin())) return; @@ -458,7 +534,7 @@ void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, PhiIt = &*++BasicBlock::iterator(cast(PhiIt)); Value *OldPhiIt = PhiIt; - if (!recursivelySimplifyInstruction(PN, TD)) + if (!recursivelySimplifyInstruction(PN)) continue; // If recursive simplification ended up deleting the next PHI node we would @@ -474,7 +550,7 @@ void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, /// between them, moving the instructions in the predecessor into DestBB and /// deleting the predecessor block. /// -void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { +void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) { // If BB has single-entry PHI nodes, fold them. while (PHINode *PN = dyn_cast(DestBB->begin())) { Value *NewVal = PN->getIncomingValue(0); @@ -503,29 +579,18 @@ void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) { // Splice all the instructions from PredBB to DestBB. PredBB->getTerminator()->eraseFromParent(); + DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList()); - // First splice over the PHI nodes. - BasicBlock::iterator PI = PredBB->begin(); - while (isa(PI)) - ++PI; - - if (PI != PredBB->begin()) - DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList(), - PredBB->begin(), PI); - - // Now splice over the rest of the instructions. - DestBB->getInstList().splice(DestBB->getFirstInsertionPt(), - PredBB->getInstList(), PI, PredBB->end()); - - if (P) { - DominatorTree *DT = P->getAnalysisIfAvailable(); - if (DT) { - BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock(); - DT->changeImmediateDominator(DestBB, PredBBIDom); - DT->eraseNode(PredBB); - } - } + // 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()) + DestBB->moveAfter(PredBB); + if (DT) { + BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock(); + DT->changeImmediateDominator(DestBB, PredBBIDom); + DT->eraseNode(PredBB); + } // Nuke BB. PredBB->eraseFromParent(); } @@ -762,10 +827,9 @@ bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { if (!Succ->getSinglePredecessor()) { BasicBlock::iterator BBI = BB->begin(); while (isa(*BBI)) { - for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); - UI != E; ++UI) { - if (PHINode* PN = dyn_cast(*UI)) { - if (PN->getIncomingBlock(UI) != BB) + for (Use &U : BBI->uses()) { + if (PHINode* PN = dyn_cast(U.getUser())) { + if (PN->getIncomingBlock(U) != BB) return false; } else { return false; @@ -797,7 +861,8 @@ bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { // Copy over any phi, debug or lifetime instruction. BB->getTerminator()->eraseFromParent(); - Succ->getInstList().splice(Succ->getFirstNonPHI(), BB->getInstList()); + Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(), + BB->getInstList()); } else { while (PHINode *PN = dyn_cast(&BB->front())) { // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. @@ -819,64 +884,50 @@ bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) { /// orders them so it usually won't matter. /// bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { - bool Changed = false; - // This implementation doesn't currently consider undef operands // specially. Theoretically, two phis which are identical except for // one having an undef where the other doesn't could be collapsed. - // Map from PHI hash values to PHI nodes. If multiple PHIs have - // the same hash value, the element is the first PHI in the - // linked list in CollisionMap. - DenseMap HashMap; + struct PHIDenseMapInfo { + static PHINode *getEmptyKey() { + return DenseMapInfo::getEmptyKey(); + } + static PHINode *getTombstoneKey() { + return DenseMapInfo::getTombstoneKey(); + } + static unsigned getHashValue(PHINode *PN) { + // Compute a hash value on the operands. Instcombine will likely have + // sorted them, which helps expose duplicates, but we have to check all + // the operands to be safe in case instcombine hasn't run. + return static_cast(hash_combine( + hash_combine_range(PN->value_op_begin(), PN->value_op_end()), + hash_combine_range(PN->block_begin(), PN->block_end()))); + } + static bool isEqual(PHINode *LHS, PHINode *RHS) { + if (LHS == getEmptyKey() || LHS == getTombstoneKey() || + RHS == getEmptyKey() || RHS == getTombstoneKey()) + return LHS == RHS; + return LHS->isIdenticalTo(RHS); + } + }; - // Maintain linked lists of PHI nodes with common hash values. - DenseMap CollisionMap; + // Set of unique PHINodes. + DenseSet PHISet; // Examine each PHI. - for (BasicBlock::iterator I = BB->begin(); - PHINode *PN = dyn_cast(I++); ) { - // Compute a hash value on the operands. Instcombine will likely have sorted - // them, which helps expose duplicates, but we have to check all the - // operands to be safe in case instcombine hasn't run. - uintptr_t Hash = 0; - // This hash algorithm is quite weak as hash functions go, but it seems - // to do a good enough job for this particular purpose, and is very quick. - for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) { - Hash ^= reinterpret_cast(static_cast(*I)); - Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); - } - for (PHINode::block_iterator I = PN->block_begin(), E = PN->block_end(); - I != E; ++I) { - Hash ^= reinterpret_cast(static_cast(*I)); - Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7)); - } - // Avoid colliding with the DenseMap sentinels ~0 and ~0-1. - Hash >>= 1; - // If we've never seen this hash value before, it's a unique PHI. - std::pair::iterator, bool> Pair = - HashMap.insert(std::make_pair(Hash, PN)); - if (Pair.second) continue; - // Otherwise it's either a duplicate or a hash collision. - for (PHINode *OtherPN = Pair.first->second; ; ) { - if (OtherPN->isIdenticalTo(PN)) { - // A duplicate. Replace this PHI with its duplicate. - PN->replaceAllUsesWith(OtherPN); - PN->eraseFromParent(); - Changed = true; - break; - } - // A non-duplicate hash collision. - DenseMap::iterator I = CollisionMap.find(OtherPN); - if (I == CollisionMap.end()) { - // Set this PHI to be the head of the linked list of colliding PHIs. - PHINode *Old = Pair.first->second; - Pair.first->second = PN; - CollisionMap[PN] = Old; - break; - } - // Proceed to the next PHI in the list. - OtherPN = I->second; + bool Changed = false; + for (auto I = BB->begin(); PHINode *PN = dyn_cast(I++);) { + auto Inserted = PHISet.insert(PN); + if (!Inserted.second) { + // A duplicate. Replace this PHI with its duplicate. + PN->replaceAllUsesWith(*Inserted.first); + PN->eraseFromParent(); + Changed = true; + + // The RAUW can change PHIs that we already visited. Start over from the + // beginning. + PHISet.clear(); + I = BB->begin(); } } @@ -890,13 +941,14 @@ bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { /// their preferred alignment from the beginning. /// static unsigned enforceKnownAlignment(Value *V, unsigned Align, - unsigned PrefAlign, const DataLayout *TD) { + unsigned PrefAlign, + const DataLayout &DL) { V = V->stripPointerCasts(); if (AllocaInst *AI = dyn_cast(V)) { // If the preferred alignment is greater than the natural stack alignment // then don't round up. This avoids dynamic stack realignment. - if (TD && TD->exceedsNaturalStackAlignment(PrefAlign)) + if (DL.exceedsNaturalStackAlignment(PrefAlign)) return Align; // If there is a requested alignment and if this is an alloca, round up. if (AI->getAlignment() >= PrefAlign) @@ -905,24 +957,23 @@ static unsigned enforceKnownAlignment(Value *V, unsigned Align, return PrefAlign; } - if (GlobalValue *GV = dyn_cast(V)) { + if (auto *GO = dyn_cast(V)) { // If there is a large requested alignment and we can, bump up the alignment - // of the global. - if (GV->isDeclaration()) return Align; - // If the memory we set aside for the global may not be the memory used by - // the final program then it is impossible for us to reliably enforce the - // preferred alignment. - if (GV->isWeakForLinker()) return Align; - - if (GV->getAlignment() >= PrefAlign) - return GV->getAlignment(); + // of the global. If the memory we set aside for the global may not be the + // memory used by the final program then it is impossible for us to reliably + // enforce the preferred alignment. + if (!GO->isStrongDefinitionForLinker()) + return Align; + + if (GO->getAlignment() >= PrefAlign) + return GO->getAlignment(); // We can only increase the alignment of the global if it has no alignment // specified or if it is not assigned a section. If it is assigned a // section, the global could be densely packed with other objects in the // section, increasing the alignment could cause padding issues. - if (!GV->hasSection() || GV->getAlignment() == 0) - GV->setAlignment(PrefAlign); - return GV->getAlignment(); + if (!GO->hasSection() || GO->getAlignment() == 0) + GO->setAlignment(PrefAlign); + return GO->getAlignment(); } return Align; @@ -933,13 +984,16 @@ static unsigned enforceKnownAlignment(Value *V, unsigned Align, /// and it is more than the alignment of the ultimate object, see if we can /// increase the alignment of the ultimate object, making this check succeed. unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, - const DataLayout *DL) { + const DataLayout &DL, + const Instruction *CxtI, + AssumptionCache *AC, + const DominatorTree *DT) { assert(V->getType()->isPointerTy() && "getOrEnforceKnownAlignment expects a pointer!"); - unsigned BitWidth = DL ? DL->getPointerTypeSizeInBits(V->getType()) : 64; + unsigned BitWidth = DL.getPointerTypeSizeInBits(V->getType()); APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); - ComputeMaskedBits(V, KnownZero, KnownOne, DL); + computeKnownBits(V, KnownZero, KnownOne, DL, 0, AC, CxtI, DT); unsigned TrailZ = KnownZero.countTrailingOnes(); // Avoid trouble with ridiculously large TrailZ values, such as @@ -963,7 +1017,7 @@ unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, /// /// See if there is a dbg.value intrinsic for DIVar before I. -static bool LdStHasDebugValue(DIVariable &DIVar, Instruction *I) { +static bool LdStHasDebugValue(const DILocalVariable *DIVar, Instruction *I) { // Since we can't guarantee that the original dbg.declare instrinsic // is removed by LowerDbgDeclare(), we need to make sure that we are // not inserting the same dbg.value intrinsic over and over. @@ -983,35 +1037,26 @@ static bool LdStHasDebugValue(DIVariable &DIVar, Instruction *I) { /// that has an associated llvm.dbg.decl intrinsic. bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, StoreInst *SI, DIBuilder &Builder) { - DIVariable DIVar(DDI->getVariable()); - assert((!DIVar || DIVar.isVariable()) && - "Variable in DbgDeclareInst should be either null or a DIVariable."); - if (!DIVar) - return false; + auto *DIVar = DDI->getVariable(); + auto *DIExpr = DDI->getExpression(); + assert(DIVar && "Missing variable"); if (LdStHasDebugValue(DIVar, SI)) return true; - Instruction *DbgVal = NULL; // If an argument is zero extended then use argument directly. The ZExt // may be zapped by an optimization pass in future. - Argument *ExtendedArg = NULL; + Argument *ExtendedArg = nullptr; if (ZExtInst *ZExt = dyn_cast(SI->getOperand(0))) ExtendedArg = dyn_cast(ZExt->getOperand(0)); if (SExtInst *SExt = dyn_cast(SI->getOperand(0))) ExtendedArg = dyn_cast(SExt->getOperand(0)); if (ExtendedArg) - DbgVal = Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, SI); - else - DbgVal = Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar, SI); - - // Propagate any debug metadata from the store onto the dbg.value. - DebugLoc SIDL = SI->getDebugLoc(); - if (!SIDL.isUnknown()) - DbgVal->setDebugLoc(SIDL); - // Otherwise propagate debug metadata from dbg.declare. + Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, DIExpr, + DDI->getDebugLoc(), SI); else - DbgVal->setDebugLoc(DDI->getDebugLoc()); + Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar, DIExpr, + DDI->getDebugLoc(), SI); return true; } @@ -1019,59 +1064,61 @@ bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, /// that has an associated llvm.dbg.decl intrinsic. bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, LoadInst *LI, DIBuilder &Builder) { - DIVariable DIVar(DDI->getVariable()); - assert((!DIVar || DIVar.isVariable()) && - "Variable in DbgDeclareInst should be either null or a DIVariable."); - if (!DIVar) - return false; + auto *DIVar = DDI->getVariable(); + auto *DIExpr = DDI->getExpression(); + assert(DIVar && "Missing variable"); if (LdStHasDebugValue(DIVar, LI)) return true; - Instruction *DbgVal = - Builder.insertDbgValueIntrinsic(LI->getOperand(0), 0, - DIVar, LI); - - // Propagate any debug metadata from the store onto the dbg.value. - DebugLoc LIDL = LI->getDebugLoc(); - if (!LIDL.isUnknown()) - DbgVal->setDebugLoc(LIDL); - // Otherwise propagate debug metadata from dbg.declare. - else - DbgVal->setDebugLoc(DDI->getDebugLoc()); + Builder.insertDbgValueIntrinsic(LI->getOperand(0), 0, DIVar, DIExpr, + DDI->getDebugLoc(), LI); return true; } +/// Determine whether this alloca is either a VLA or an array. +static bool isArray(AllocaInst *AI) { + return AI->isArrayAllocation() || + AI->getType()->getElementType()->isArrayTy(); +} + /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set /// of llvm.dbg.value intrinsics. bool llvm::LowerDbgDeclare(Function &F) { - DIBuilder DIB(*F.getParent()); + DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false); SmallVector Dbgs; - for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) - for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ++BI) { - if (DbgDeclareInst *DDI = dyn_cast(BI)) + for (auto &FI : F) + for (Instruction &BI : FI) + if (auto DDI = dyn_cast(&BI)) Dbgs.push_back(DDI); - } + if (Dbgs.empty()) return false; - for (SmallVectorImpl::iterator I = Dbgs.begin(), - E = Dbgs.end(); I != E; ++I) { - DbgDeclareInst *DDI = *I; - if (AllocaInst *AI = dyn_cast_or_null(DDI->getAddress())) { - // We only remove the dbg.declare intrinsic if all uses are - // converted to dbg.value intrinsics. - bool RemoveDDI = true; - for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); - UI != E; ++UI) - if (StoreInst *SI = dyn_cast(*UI)) + for (auto &I : Dbgs) { + DbgDeclareInst *DDI = I; + AllocaInst *AI = dyn_cast_or_null(DDI->getAddress()); + // If this is an alloca for a scalar variable, insert a dbg.value + // at each load and store to the alloca and erase the dbg.declare. + // The dbg.values allow tracking a variable even if it is not + // 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 (User *U : AI->users()) + if (StoreInst *SI = dyn_cast(U)) ConvertDebugDeclareToDebugValue(DDI, SI, DIB); - else if (LoadInst *LI = dyn_cast(*UI)) + else if (LoadInst *LI = dyn_cast(U)) ConvertDebugDeclareToDebugValue(DDI, LI, DIB); - else - RemoveDDI = false; - if (RemoveDDI) - DDI->eraseFromParent(); + else if (CallInst *CI = dyn_cast(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, 0, DDI->getVariable(), + DDI->getExpression(), DDI->getDebugLoc(), + CI); + } + DDI->eraseFromParent(); } } return true; @@ -1080,52 +1127,59 @@ bool llvm::LowerDbgDeclare(Function &F) { /// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic describing the /// alloca 'V', if any. DbgDeclareInst *llvm::FindAllocaDbgDeclare(Value *V) { - if (MDNode *DebugNode = MDNode::getIfExists(V->getContext(), V)) - for (Value::use_iterator UI = DebugNode->use_begin(), - E = DebugNode->use_end(); UI != E; ++UI) - if (DbgDeclareInst *DDI = dyn_cast(*UI)) - return DDI; + if (auto *L = LocalAsMetadata::getIfExists(V)) + if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L)) + for (User *U : MDV->users()) + if (DbgDeclareInst *DDI = dyn_cast(U)) + return DDI; - return 0; + return nullptr; } -bool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, - DIBuilder &Builder) { - DbgDeclareInst *DDI = FindAllocaDbgDeclare(AI); +bool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress, + Instruction *InsertBefore, DIBuilder &Builder, + bool Deref, int Offset) { + DbgDeclareInst *DDI = FindAllocaDbgDeclare(Address); if (!DDI) return false; - DIVariable DIVar(DDI->getVariable()); - assert((!DIVar || DIVar.isVariable()) && - "Variable in DbgDeclareInst should be either null or a DIVariable."); - if (!DIVar) - return false; - - // Create a copy of the original DIDescriptor for user variable, appending - // "deref" operation to a list of address elements, as new llvm.dbg.declare - // will take a value storing address of the memory for variable, not - // alloca itself. - Type *Int64Ty = Type::getInt64Ty(AI->getContext()); - SmallVector NewDIVarAddress; - if (DIVar.hasComplexAddress()) { - for (unsigned i = 0, n = DIVar.getNumAddrElements(); i < n; ++i) { - NewDIVarAddress.push_back( - ConstantInt::get(Int64Ty, DIVar.getAddrElement(i))); + DebugLoc Loc = DDI->getDebugLoc(); + auto *DIVar = DDI->getVariable(); + auto *DIExpr = DDI->getExpression(); + assert(DIVar && "Missing variable"); + + if (Deref || Offset) { + // Create a copy of the original DIDescriptor for user variable, prepending + // "deref" operation to a list of address elements, as new llvm.dbg.declare + // will take a value storing address of the memory for variable, not + // alloca itself. + SmallVector NewDIExpr; + if (Deref) + NewDIExpr.push_back(dwarf::DW_OP_deref); + if (Offset > 0) { + NewDIExpr.push_back(dwarf::DW_OP_plus); + NewDIExpr.push_back(Offset); + } else if (Offset < 0) { + NewDIExpr.push_back(dwarf::DW_OP_minus); + NewDIExpr.push_back(-Offset); } + if (DIExpr) + NewDIExpr.append(DIExpr->elements_begin(), DIExpr->elements_end()); + DIExpr = Builder.createExpression(NewDIExpr); } - NewDIVarAddress.push_back(ConstantInt::get(Int64Ty, DIBuilder::OpDeref)); - DIVariable NewDIVar = Builder.createComplexVariable( - DIVar.getTag(), DIVar.getContext(), DIVar.getName(), - DIVar.getFile(), DIVar.getLineNumber(), DIVar.getType(), - NewDIVarAddress, DIVar.getArgNumber()); - - // Insert llvm.dbg.declare in the same basic block as the original alloca, - // and remove old llvm.dbg.declare. - BasicBlock *BB = AI->getParent(); - Builder.insertDeclare(NewAllocaAddress, NewDIVar, BB); + + // Insert llvm.dbg.declare immediately after the original alloca, and remove + // old llvm.dbg.declare. + Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, InsertBefore); DDI->eraseFromParent(); return true; } +bool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, + DIBuilder &Builder, bool Deref, int Offset) { + return replaceDbgDeclare(AI, NewAllocaAddress, AI->getNextNode(), Builder, + Deref, Offset); +} + /// changeToUnreachable - Insert an unreachable instruction before the specified /// instruction, making it and the rest of the code in the block dead. static void changeToUnreachable(Instruction *I, bool UseLLVMTrap) { @@ -1146,7 +1200,7 @@ static void changeToUnreachable(Instruction *I, bool UseLLVMTrap) { new UnreachableInst(I->getContext(), I); // All instructions after this are dead. - BasicBlock::iterator BBI = I, BBE = BB->end(); + BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end(); while (BBI != BBE) { if (!BBI->use_empty()) BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); @@ -1156,8 +1210,11 @@ static void changeToUnreachable(Instruction *I, bool UseLLVMTrap) { /// changeToCall - Convert the specified invoke into a normal call. static void changeToCall(InvokeInst *II) { - SmallVector Args(II->op_begin(), II->op_end() - 3); - CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, "", II); + SmallVector Args(II->arg_begin(), II->arg_end()); + SmallVector OpBundles; + II->getOperandBundlesAsDefs(OpBundles); + CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles, + "", II); NewCall->takeName(II); NewCall->setCallingConv(II->getCallingConv()); NewCall->setAttributes(II->getAttributes()); @@ -1172,10 +1229,11 @@ static void changeToCall(InvokeInst *II) { II->eraseFromParent(); } -static bool markAliveBlocks(BasicBlock *BB, - SmallPtrSet &Reachable) { +static bool markAliveBlocks(Function &F, + SmallPtrSetImpl &Reachable) { SmallVector Worklist; + BasicBlock *BB = &F.front(); Worklist.push_back(BB); Reachable.insert(BB); bool Changed = false; @@ -1186,6 +1244,26 @@ static bool markAliveBlocks(BasicBlock *BB, // instructions into LLVM unreachable insts. The instruction combining pass // canonicalizes unreachable insts into stores to null or undef. for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){ + // 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 (IntrinsicInst *II = dyn_cast(BBI)) + if (II->getIntrinsicID() == Intrinsic::assume) { + bool MakeUnreachable = false; + if (isa(II->getArgOperand(0))) + MakeUnreachable = true; + else if (ConstantInt *Cond = + dyn_cast(II->getArgOperand(0))) + MakeUnreachable = Cond->isZero(); + + if (MakeUnreachable) { + // Don't insert a call to llvm.trap right before the unreachable. + changeToUnreachable(&*BBI, false); + Changed = true; + break; + } + } + if (CallInst *CI = dyn_cast(BBI)) { if (CI->doesNotReturn()) { // If we found a call to a no-return function, insert an unreachable @@ -1194,7 +1272,7 @@ static bool markAliveBlocks(BasicBlock *BB, ++BBI; if (!isa(BBI)) { // Don't insert a call to llvm.trap right before the unreachable. - changeToUnreachable(BBI, false); + changeToUnreachable(&*BBI, false); Changed = true; } break; @@ -1226,7 +1304,7 @@ static bool markAliveBlocks(BasicBlock *BB, if (isa(Callee) || isa(Callee)) { changeToUnreachable(II, true); Changed = true; - } else if (II->doesNotThrow()) { + } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) { if (II->use_empty() && II->onlyReadsMemory()) { // jump to the normal destination branch. BranchInst::Create(II->getNormalDest(), II); @@ -1240,18 +1318,55 @@ static bool markAliveBlocks(BasicBlock *BB, Changed |= ConstantFoldTerminator(BB, true); for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) - if (Reachable.insert(*SI)) + if (Reachable.insert(*SI).second) Worklist.push_back(*SI); } while (!Worklist.empty()); return Changed; } +void llvm::removeUnwindEdge(BasicBlock *BB) { + TerminatorInst *TI = BB->getTerminator(); + + if (auto *II = dyn_cast(TI)) { + changeToCall(II); + return; + } + + TerminatorInst *NewTI; + BasicBlock *UnwindDest; + + if (auto *CRI = dyn_cast(TI)) { + NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI); + UnwindDest = CRI->getUnwindDest(); + } else if (auto *CEP = dyn_cast(TI)) { + NewTI = CleanupEndPadInst::Create(CEP->getCleanupPad(), nullptr, CEP); + UnwindDest = CEP->getUnwindDest(); + } else if (auto *CEP = dyn_cast(TI)) { + NewTI = CatchEndPadInst::Create(CEP->getContext(), nullptr, CEP); + UnwindDest = CEP->getUnwindDest(); + } else if (auto *TPI = dyn_cast(TI)) { + SmallVector TerminatePadArgs; + for (Value *Operand : TPI->arg_operands()) + TerminatePadArgs.push_back(Operand); + NewTI = TerminatePadInst::Create(TPI->getContext(), nullptr, + TerminatePadArgs, TPI); + UnwindDest = TPI->getUnwindDest(); + } else { + llvm_unreachable("Could not find unwind successor"); + } + + NewTI->takeName(TI); + NewTI->setDebugLoc(TI->getDebugLoc()); + UnwindDest->removePredecessor(BB); + TI->eraseFromParent(); +} + /// removeUnreachableBlocksFromFn - Remove blocks that are not reachable, even /// if they are in a dead cycle. Return true if a change was made, false /// otherwise. bool llvm::removeUnreachableBlocks(Function &F) { SmallPtrSet Reachable; - bool Changed = markAliveBlocks(F.begin(), Reachable); + bool Changed = markAliveBlocks(F, Reachable); // If there are unreachable blocks in the CFG... if (Reachable.size() == F.size()) @@ -1263,20 +1378,142 @@ bool llvm::removeUnreachableBlocks(Function &F) { // 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)) + if (Reachable.count(&*BB)) continue; - for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) + for (succ_iterator SI = succ_begin(&*BB), SE = succ_end(&*BB); SI != SE; + ++SI) if (Reachable.count(*SI)) - (*SI)->removePredecessor(BB); + (*SI)->removePredecessor(&*BB); BB->dropAllReferences(); } for (Function::iterator I = ++F.begin(); I != F.end();) - if (!Reachable.count(I)) + if (!Reachable.count(&*I)) I = F.getBasicBlockList().erase(I); else ++I; return true; } + +void llvm::combineMetadata(Instruction *K, const Instruction *J, + ArrayRef KnownIDs) { + SmallVector, 4> Metadata; + K->dropUnknownNonDebugMetadata(KnownIDs); + K->getAllMetadataOtherThanDebugLoc(Metadata); + for (unsigned i = 0, n = Metadata.size(); i < n; ++i) { + unsigned Kind = Metadata[i].first; + MDNode *JMD = J->getMetadata(Kind); + MDNode *KMD = Metadata[i].second; + + switch (Kind) { + default: + K->setMetadata(Kind, nullptr); // Remove unknown metadata + break; + case LLVMContext::MD_dbg: + llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg"); + case LLVMContext::MD_tbaa: + K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD)); + break; + case LLVMContext::MD_alias_scope: + K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD)); + break; + case LLVMContext::MD_noalias: + K->setMetadata(Kind, MDNode::intersect(JMD, KMD)); + break; + case LLVMContext::MD_range: + K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD)); + break; + case LLVMContext::MD_fpmath: + K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD)); + break; + case LLVMContext::MD_invariant_load: + // Only set the !invariant.load if it is present in both instructions. + K->setMetadata(Kind, JMD); + break; + case LLVMContext::MD_nonnull: + // Only set the !nonnull if it is present in both instructions. + K->setMetadata(Kind, JMD); + break; + case LLVMContext::MD_invariant_group: + // Preserve !invariant.group in K. + break; + case LLVMContext::MD_align: + K->setMetadata(Kind, + MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD)); + break; + case LLVMContext::MD_dereferenceable: + case LLVMContext::MD_dereferenceable_or_null: + K->setMetadata(Kind, + MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD)); + break; + } + } + // Set !invariant.group from J if J has it. If both instructions have it + // then we will just pick it from J - even when they are different. + // Also make sure that K is load or store - f.e. combining bitcast with load + // could produce bitcast with invariant.group metadata, which is invalid. + // FIXME: we should try to preserve both invariant.group md if they are + // different, but right now instruction can only have one invariant.group. + if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group)) + if (isa(K) || isa(K)) + K->setMetadata(LLVMContext::MD_invariant_group, JMD); +} + +unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, + DominatorTree &DT, + const BasicBlockEdge &Root) { + assert(From->getType() == To->getType()); + + unsigned Count = 0; + for (Value::use_iterator UI = From->use_begin(), UE = From->use_end(); + UI != UE; ) { + Use &U = *UI++; + if (DT.dominates(Root, U)) { + U.set(To); + DEBUG(dbgs() << "Replace dominated use of '" + << From->getName() << "' as " + << *To << " in " << *U << "\n"); + ++Count; + } + } + return Count; +} + +unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To, + DominatorTree &DT, + const BasicBlock *BB) { + assert(From->getType() == To->getType()); + + unsigned Count = 0; + for (Value::use_iterator UI = From->use_begin(), UE = From->use_end(); + UI != UE;) { + Use &U = *UI++; + auto *I = cast(U.getUser()); + if (DT.dominates(BB, I->getParent())) { + U.set(To); + DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as " + << *To << " in " << *U << "\n"); + ++Count; + } + } + return Count; +} + +bool llvm::callsGCLeafFunction(ImmutableCallSite CS) { + if (isa(CS.getInstruction())) + // Most LLVM intrinsics are things which can never take a safepoint. + // As a result, we don't need to have the stack parsable at the + // callsite. This is a highly useful optimization since intrinsic + // calls are fairly prevalent, particularly in debug builds. + return true; + + // Check if the function is specifically marked as a gc leaf function. + // + // TODO: we should be checking the attributes on the call site as well. + if (const Function *F = CS.getCalledFunction()) + return F->hasFnAttribute("gc-leaf-function"); + + return false; +}