diff options
Diffstat (limited to 'contrib/llvm/lib/Transforms/Utils')
19 files changed, 1252 insertions, 334 deletions
diff --git a/contrib/llvm/lib/Transforms/Utils/AddrModeMatcher.cpp b/contrib/llvm/lib/Transforms/Utils/AddrModeMatcher.cpp index be7bed1..8e5a1eb 100644 --- a/contrib/llvm/lib/Transforms/Utils/AddrModeMatcher.cpp +++ b/contrib/llvm/lib/Transforms/Utils/AddrModeMatcher.cpp @@ -222,7 +222,7 @@ bool AddressingModeMatcher::MatchOperationAddr(User *AddrInst, unsigned Opcode, const TargetData *TD = TLI.getTargetData(); gep_type_iterator GTI = gep_type_begin(AddrInst); for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) { - if (const StructType *STy = dyn_cast<StructType>(*GTI)) { + if (StructType *STy = dyn_cast<StructType>(*GTI)) { const StructLayout *SL = TD->getStructLayout(STy); unsigned Idx = cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue(); @@ -557,7 +557,7 @@ IsProfitableToFoldIntoAddressingMode(Instruction *I, ExtAddrMode &AMBefore, Value *Address = User->getOperand(OpNo); if (!Address->getType()->isPointerTy()) return false; - const Type *AddressAccessTy = + Type *AddressAccessTy = cast<PointerType>(Address->getType())->getElementType(); // Do a match against the root of this address, ignoring profitability. This diff --git a/contrib/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/contrib/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp index b4f74f9..a7f9efd 100644 --- a/contrib/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/contrib/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -287,7 +287,7 @@ BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, Pass *P) { /// BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) { BasicBlock::iterator SplitIt = SplitPt; - while (isa<PHINode>(SplitIt)) + while (isa<PHINode>(SplitIt) || isa<LandingPadInst>(SplitIt)) ++SplitIt; BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split"); @@ -299,138 +299,114 @@ BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) { if (DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>()) { // Old dominates New. New node dominates all other nodes dominated by Old. - DomTreeNode *OldNode = DT->getNode(Old); - std::vector<DomTreeNode *> Children; - for (DomTreeNode::iterator I = OldNode->begin(), E = OldNode->end(); - I != E; ++I) - Children.push_back(*I); + if (DomTreeNode *OldNode = DT->getNode(Old)) { + std::vector<DomTreeNode *> Children; + for (DomTreeNode::iterator I = OldNode->begin(), E = OldNode->end(); + I != E; ++I) + Children.push_back(*I); DomTreeNode *NewNode = DT->addNewBlock(New,Old); for (std::vector<DomTreeNode *>::iterator I = Children.begin(), E = Children.end(); I != E; ++I) DT->changeImmediateDominator(*I, NewNode); + } } return New; } +/// UpdateAnalysisInformation - Update DominatorTree, LoopInfo, and LCCSA +/// analysis information. +static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, + ArrayRef<BasicBlock *> Preds, + Pass *P, bool &HasLoopExit) { + if (!P) return; -/// SplitBlockPredecessors - This method transforms BB by introducing a new -/// basic block into the function, and moving some of the predecessors of BB to -/// be predecessors of the new block. The new predecessors are indicated by the -/// Preds array, which has NumPreds elements in it. The new block is given a -/// suffix of 'Suffix'. -/// -/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree, -/// LoopInfo, and LCCSA but no other analyses. In particular, it does not -/// preserve LoopSimplify (because it's complicated to handle the case where one -/// of the edges being split is an exit of a loop with other exits). -/// -BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, - BasicBlock *const *Preds, - unsigned NumPreds, const char *Suffix, - Pass *P) { - // Create new basic block, insert right before the original block. - BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), BB->getName()+Suffix, - BB->getParent(), BB); - - // The new block unconditionally branches to the old block. - BranchInst *BI = BranchInst::Create(BB, NewBB); - - LoopInfo *LI = P ? P->getAnalysisIfAvailable<LoopInfo>() : 0; - Loop *L = LI ? LI->getLoopFor(BB) : 0; - bool PreserveLCSSA = P->mustPreserveAnalysisID(LCSSAID); + LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>(); + Loop *L = LI ? LI->getLoopFor(OldBB) : 0; - // Move the edges from Preds to point to NewBB instead of BB. - // While here, if we need to preserve loop analyses, collect - // some information about how this split will affect loops. - bool HasLoopExit = false; + // If we need to preserve loop analyses, collect some information about how + // this split will affect loops. bool IsLoopEntry = !!L; bool SplitMakesNewLoopHeader = false; - for (unsigned i = 0; i != NumPreds; ++i) { - // This is slightly more strict than necessary; the minimum requirement - // is that there be no more than one indirectbr branching to BB. And - // all BlockAddress uses would need to be updated. - assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) && - "Cannot split an edge from an IndirectBrInst"); - - Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB); - - if (LI) { - // If we need to preserve LCSSA, determine if any of - // the preds is a loop exit. + if (LI) { + bool PreserveLCSSA = P->mustPreserveAnalysisID(LCSSAID); + for (ArrayRef<BasicBlock*>::iterator + i = Preds.begin(), e = Preds.end(); i != e; ++i) { + BasicBlock *Pred = *i; + + // If we need to preserve LCSSA, determine if any of the preds is a loop + // exit. if (PreserveLCSSA) - if (Loop *PL = LI->getLoopFor(Preds[i])) - if (!PL->contains(BB)) + if (Loop *PL = LI->getLoopFor(Pred)) + if (!PL->contains(OldBB)) HasLoopExit = true; - // If we need to preserve LoopInfo, note whether any of the - // preds crosses an interesting loop boundary. - if (L) { - if (L->contains(Preds[i])) - IsLoopEntry = false; - else - SplitMakesNewLoopHeader = true; - } + + // If we need to preserve LoopInfo, note whether any of the preds crosses + // an interesting loop boundary. + if (!L) continue; + if (L->contains(Pred)) + IsLoopEntry = false; + else + SplitMakesNewLoopHeader = true; } } // Update dominator tree if available. - DominatorTree *DT = P ? P->getAnalysisIfAvailable<DominatorTree>() : 0; + DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>(); if (DT) DT->splitBlock(NewBB); - // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI - // node becomes an incoming value for BB's phi node. However, if the Preds - // list is empty, we need to insert dummy entries into the PHI nodes in BB to - // account for the newly created predecessor. - if (NumPreds == 0) { - // Insert dummy values as the incoming value. - for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) - cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB); - return NewBB; + if (!L) return; + + if (IsLoopEntry) { + // Add the new block to the nearest enclosing loop (and not an adjacent + // loop). To find this, examine each of the predecessors and determine which + // loops enclose them, and select the most-nested loop which contains the + // loop containing the block being split. + Loop *InnermostPredLoop = 0; + for (ArrayRef<BasicBlock*>::iterator + i = Preds.begin(), e = Preds.end(); i != e; ++i) { + BasicBlock *Pred = *i; + if (Loop *PredLoop = LI->getLoopFor(Pred)) { + // Seek a loop which actually contains the block being split (to avoid + // adjacent loops). + while (PredLoop && !PredLoop->contains(OldBB)) + PredLoop = PredLoop->getParentLoop(); + + // Select the most-nested of these loops which contains the block. + if (PredLoop && PredLoop->contains(OldBB) && + (!InnermostPredLoop || + InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth())) + InnermostPredLoop = PredLoop; + } + } + + if (InnermostPredLoop) + InnermostPredLoop->addBasicBlockToLoop(NewBB, LI->getBase()); + } else { + L->addBasicBlockToLoop(NewBB, LI->getBase()); + if (SplitMakesNewLoopHeader) + L->moveToHeader(NewBB); } +} +/// UpdatePHINodes - Update the PHI nodes in OrigBB to include the values coming +/// from NewBB. This also updates AliasAnalysis, if available. +static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB, + ArrayRef<BasicBlock*> Preds, BranchInst *BI, + Pass *P, bool HasLoopExit) { + // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB. AliasAnalysis *AA = P ? P->getAnalysisIfAvailable<AliasAnalysis>() : 0; - - if (L) { - if (IsLoopEntry) { - // Add the new block to the nearest enclosing loop (and not an - // adjacent loop). To find this, examine each of the predecessors and - // determine which loops enclose them, and select the most-nested loop - // which contains the loop containing the block being split. - Loop *InnermostPredLoop = 0; - for (unsigned i = 0; i != NumPreds; ++i) - if (Loop *PredLoop = LI->getLoopFor(Preds[i])) { - // Seek a loop which actually contains the block being split (to - // avoid adjacent loops). - while (PredLoop && !PredLoop->contains(BB)) - PredLoop = PredLoop->getParentLoop(); - // Select the most-nested of these loops which contains the block. - if (PredLoop && - PredLoop->contains(BB) && - (!InnermostPredLoop || - InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth())) - InnermostPredLoop = PredLoop; - } - if (InnermostPredLoop) - InnermostPredLoop->addBasicBlockToLoop(NewBB, LI->getBase()); - } else { - L->addBasicBlockToLoop(NewBB, LI->getBase()); - if (SplitMakesNewLoopHeader) - L->moveToHeader(NewBB); - } - } - - // Otherwise, create a new PHI node in NewBB for each PHI node in BB. - for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) { + for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) { PHINode *PN = cast<PHINode>(I++); - + // Check to see if all of the values coming in are the same. If so, we // don't need to create a new PHI node, unless it's needed for LCSSA. Value *InVal = 0; if (!HasLoopExit) { InVal = PN->getIncomingValueForBlock(Preds[0]); - for (unsigned i = 1; i != NumPreds; ++i) + for (unsigned i = 1, e = Preds.size(); i != e; ++i) if (InVal != PN->getIncomingValueForBlock(Preds[i])) { InVal = 0; break; @@ -441,31 +417,191 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, // If all incoming values for the new PHI would be the same, just don't // make a new PHI. Instead, just remove the incoming values from the old // PHI. - for (unsigned i = 0; i != NumPreds; ++i) + for (unsigned i = 0, e = Preds.size(); i != e; ++i) PN->removeIncomingValue(Preds[i], false); } else { // If the values coming into the block are not the same, we need a PHI. // Create the new PHI node, insert it into NewBB at the end of the block PHINode *NewPHI = - PHINode::Create(PN->getType(), NumPreds, PN->getName()+".ph", BI); + PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI); if (AA) AA->copyValue(PN, NewPHI); // Move all of the PHI values for 'Preds' to the new PHI. - for (unsigned i = 0; i != NumPreds; ++i) { + for (unsigned i = 0, e = Preds.size(); i != e; ++i) { Value *V = PN->removeIncomingValue(Preds[i], false); NewPHI->addIncoming(V, Preds[i]); } + InVal = NewPHI; } - + // Add an incoming value to the PHI node in the loop for the preheader // edge. PN->addIncoming(InVal, NewBB); } +} + +/// SplitBlockPredecessors - This method transforms BB by introducing a new +/// basic block into the function, and moving some of the predecessors of BB to +/// be predecessors of the new block. The new predecessors are indicated by the +/// Preds array, which has NumPreds elements in it. The new block is given a +/// suffix of 'Suffix'. +/// +/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree, +/// LoopInfo, and LCCSA but no other analyses. In particular, it does not +/// preserve LoopSimplify (because it's complicated to handle the case where one +/// of the edges being split is an exit of a loop with other exits). +/// +BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, + BasicBlock *const *Preds, + unsigned NumPreds, const char *Suffix, + Pass *P) { + // Create new basic block, insert right before the original block. + BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), BB->getName()+Suffix, + BB->getParent(), BB); + // The new block unconditionally branches to the old block. + BranchInst *BI = BranchInst::Create(BB, NewBB); + + // Move the edges from Preds to point to NewBB instead of BB. + for (unsigned i = 0; i != NumPreds; ++i) { + // This is slightly more strict than necessary; the minimum requirement + // is that there be no more than one indirectbr branching to BB. And + // all BlockAddress uses would need to be updated. + assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) && + "Cannot split an edge from an IndirectBrInst"); + Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB); + } + + // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI + // node becomes an incoming value for BB's phi node. However, if the Preds + // list is empty, we need to insert dummy entries into the PHI nodes in BB to + // account for the newly created predecessor. + if (NumPreds == 0) { + // Insert dummy values as the incoming value. + for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) + cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB); + return NewBB; + } + + // Update DominatorTree, LoopInfo, and LCCSA analysis information. + bool HasLoopExit = false; + UpdateAnalysisInformation(BB, NewBB, ArrayRef<BasicBlock*>(Preds, NumPreds), + P, HasLoopExit); + + // Update the PHI nodes in BB with the values coming from NewBB. + UpdatePHINodes(BB, NewBB, ArrayRef<BasicBlock*>(Preds, NumPreds), BI, + P, HasLoopExit); return NewBB; } +/// SplitLandingPadPredecessors - This method transforms the landing pad, +/// OrigBB, by introducing two new basic blocks into the function. One of those +/// new basic blocks gets the predecessors listed in Preds. The other basic +/// block gets the remaining predecessors of OrigBB. The landingpad instruction +/// OrigBB is clone into both of the new basic blocks. The new blocks are given +/// the suffixes 'Suffix1' and 'Suffix2', and are returned in the NewBBs vector. +/// +/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree, +/// DominanceFrontier, LoopInfo, and LCCSA but no other analyses. In particular, +/// it does not preserve LoopSimplify (because it's complicated to handle the +/// case where one of the edges being split is an exit of a loop with other +/// exits). +/// +void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, + ArrayRef<BasicBlock*> Preds, + const char *Suffix1, const char *Suffix2, + Pass *P, + SmallVectorImpl<BasicBlock*> &NewBBs) { + assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!"); + + // Create a new basic block for OrigBB's predecessors listed in Preds. Insert + // it right before the original block. + BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(), + OrigBB->getName() + Suffix1, + OrigBB->getParent(), OrigBB); + NewBBs.push_back(NewBB1); + + // The new block unconditionally branches to the old block. + BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1); + + // Move the edges from Preds to point to NewBB1 instead of OrigBB. + for (unsigned i = 0, e = Preds.size(); i != e; ++i) { + // This is slightly more strict than necessary; the minimum requirement + // is that there be no more than one indirectbr branching to BB. And + // all BlockAddress uses would need to be updated. + assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) && + "Cannot split an edge from an IndirectBrInst"); + Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1); + } + + // Update DominatorTree, LoopInfo, and LCCSA analysis information. + bool HasLoopExit = false; + UpdateAnalysisInformation(OrigBB, NewBB1, Preds, P, HasLoopExit); + + // Update the PHI nodes in OrigBB with the values coming from NewBB1. + UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, P, HasLoopExit); + + // Move the remaining edges from OrigBB to point to NewBB2. + SmallVector<BasicBlock*, 8> NewBB2Preds; + for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB); + i != e; ) { + BasicBlock *Pred = *i++; + if (Pred == NewBB1) continue; + assert(!isa<IndirectBrInst>(Pred->getTerminator()) && + "Cannot split an edge from an IndirectBrInst"); + NewBB2Preds.push_back(Pred); + e = pred_end(OrigBB); + } + + BasicBlock *NewBB2 = 0; + if (!NewBB2Preds.empty()) { + // Create another basic block for the rest of OrigBB's predecessors. + NewBB2 = BasicBlock::Create(OrigBB->getContext(), + OrigBB->getName() + Suffix2, + OrigBB->getParent(), OrigBB); + NewBBs.push_back(NewBB2); + + // The new block unconditionally branches to the old block. + BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2); + + // Move the remaining edges from OrigBB to point to NewBB2. + for (SmallVectorImpl<BasicBlock*>::iterator + i = NewBB2Preds.begin(), e = NewBB2Preds.end(); i != e; ++i) + (*i)->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2); + + // Update DominatorTree, LoopInfo, and LCCSA analysis information. + HasLoopExit = false; + UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, P, HasLoopExit); + + // Update the PHI nodes in OrigBB with the values coming from NewBB2. + UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, P, HasLoopExit); + } + + LandingPadInst *LPad = OrigBB->getLandingPadInst(); + Instruction *Clone1 = LPad->clone(); + Clone1->setName(Twine("lpad") + Suffix1); + NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1); + + if (NewBB2) { + Instruction *Clone2 = LPad->clone(); + Clone2->setName(Twine("lpad") + Suffix2); + NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2); + + // Create a PHI node for the two cloned landingpad instructions. + PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad); + PN->addIncoming(Clone1, NewBB1); + PN->addIncoming(Clone2, NewBB2); + LPad->replaceAllUsesWith(PN); + LPad->eraseFromParent(); + } else { + // There is no second clone. Just replace the landing pad with the first + // clone. + LPad->replaceAllUsesWith(Clone1); + LPad->eraseFromParent(); + } +} + /// FindFunctionBackedges - Analyze the specified function to find all of the /// loop backedges in the function and return them. This is a relatively cheap /// (compared to computing dominators and loop info) analysis. diff --git a/contrib/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp b/contrib/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp index 92ce500..c052910 100644 --- a/contrib/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/contrib/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -102,7 +102,7 @@ bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, ++I; // Skip one edge due to the incoming arc from TI. if (!AllowIdenticalEdges) return I != E; - + // If AllowIdenticalEdges is true, then we allow this edge to be considered // non-critical iff all preds come from TI's block. while (I != E) { @@ -155,10 +155,10 @@ static void CreatePHIsForSplitLoopExit(SmallVectorImpl<BasicBlock *> &Preds, /// This returns the new block if the edge was split, null otherwise. /// /// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the -/// specified successor will be merged into the same critical edge block. -/// This is most commonly interesting with switch instructions, which may +/// specified successor will be merged into the same critical edge block. +/// This is most commonly interesting with switch instructions, which may /// have many edges to any one destination. This ensures that all edges to that -/// dest go to one block instead of each going to a different block, but isn't +/// dest go to one block instead of each going to a different block, but isn't /// the standard definition of a "critical edge". /// /// It is invalid to call this function on a critical edge that starts at an @@ -167,15 +167,20 @@ static void CreatePHIsForSplitLoopExit(SmallVectorImpl<BasicBlock *> &Preds, /// to. /// BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, - Pass *P, bool MergeIdenticalEdges) { + Pass *P, bool MergeIdenticalEdges, + bool DontDeleteUselessPhis) { if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return 0; - + assert(!isa<IndirectBrInst>(TI) && "Cannot split critical edge from IndirectBrInst"); - + BasicBlock *TIBB = TI->getParent(); BasicBlock *DestBB = TI->getSuccessor(SuccNum); + // Splitting the critical edge to a landing pad block is non-trivial. Don't do + // it in this generic function. + if (DestBB->isLandingPad()) return 0; + // Create a new basic block, linking it into the CFG. BasicBlock *NewBB = BasicBlock::Create(TI->getContext(), TIBB->getName() + "." + DestBB->getName() + "_crit_edge"); @@ -190,7 +195,7 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Function &F = *TIBB->getParent(); Function::iterator FBBI = TIBB; F.getBasicBlockList().insert(++FBBI, NewBB); - + // If there are any PHI nodes in DestBB, we need to update them so that they // merge incoming values from NewBB instead of from TIBB. { @@ -207,35 +212,35 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, // happens because the BB list of PHI nodes are usually in the same // order. if (PN->getIncomingBlock(BBIdx) != TIBB) - BBIdx = PN->getBasicBlockIndex(TIBB); + BBIdx = PN->getBasicBlockIndex(TIBB); PN->setIncomingBlock(BBIdx, NewBB); } } - + // If there are any other edges from TIBB to DestBB, update those to go // through the split block, making those edges non-critical as well (and // reducing the number of phi entries in the DestBB if relevant). if (MergeIdenticalEdges) { for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) { if (TI->getSuccessor(i) != DestBB) continue; - + // Remove an entry for TIBB from DestBB phi nodes. - DestBB->removePredecessor(TIBB); - + DestBB->removePredecessor(TIBB, DontDeleteUselessPhis); + // We found another edge to DestBB, go to NewBB instead. TI->setSuccessor(i, NewBB); } } - - + + // If we don't have a pass object, we can't update anything... if (P == 0) return NewBB; - + DominatorTree *DT = P->getAnalysisIfAvailable<DominatorTree>(); LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>(); ProfileInfo *PI = P->getAnalysisIfAvailable<ProfileInfo>(); - + // If we have nothing to update, just return. if (DT == 0 && LI == 0 && PI == 0) return NewBB; @@ -263,7 +268,7 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, } bool NewBBDominatesDestBB = true; - + // Should we update DominatorTree information? if (DT) { DomTreeNode *TINode = DT->getNode(TIBB); @@ -274,7 +279,7 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, if (TINode) { // Don't break unreachable code! DomTreeNode *NewBBNode = DT->addNewBlock(NewBB, TIBB); DomTreeNode *DestBBNode = 0; - + // If NewBBDominatesDestBB hasn't been computed yet, do so with DT. if (!OtherPreds.empty()) { DestBBNode = DT->getNode(DestBB); @@ -285,7 +290,7 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, } OtherPreds.clear(); } - + // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it // doesn't dominate anything. if (NewBBDominatesDestBB) { @@ -337,6 +342,8 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, } // For each unique exit block... + // FIXME: This code is functionally equivalent to the corresponding + // loop in LoopSimplify. SmallVector<BasicBlock *, 4> ExitBlocks; TIL->getExitBlocks(ExitBlocks); for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { @@ -348,10 +355,15 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) { BasicBlock *P = *I; - if (TIL->contains(P)) + if (TIL->contains(P)) { + if (isa<IndirectBrInst>(P->getTerminator())) { + Preds.clear(); + break; + } Preds.push_back(P); - else + } else { HasPredOutsideOfLoop = true; + } } // If there are any preds not in the loop, we'll need to split // the edges. The Preds.empty() check is needed because a block diff --git a/contrib/llvm/lib/Transforms/Utils/BuildLibCalls.cpp b/contrib/llvm/lib/Transforms/Utils/BuildLibCalls.cpp index 14bb17f..4b5f45b 100644 --- a/contrib/llvm/lib/Transforms/Utils/BuildLibCalls.cpp +++ b/contrib/llvm/lib/Transforms/Utils/BuildLibCalls.cpp @@ -58,8 +58,8 @@ Value *llvm::EmitStrChr(Value *Ptr, char C, IRBuilder<> &B, AttributeWithIndex AWI = AttributeWithIndex::get(~0u, Attribute::ReadOnly | Attribute::NoUnwind); - const Type *I8Ptr = B.getInt8PtrTy(); - const Type *I32Ty = B.getInt32Ty(); + Type *I8Ptr = B.getInt8PtrTy(); + Type *I32Ty = B.getInt32Ty(); Constant *StrChr = M->getOrInsertFunction("strchr", AttrListPtr::get(&AWI, 1), I8Ptr, I8Ptr, I32Ty, NULL); CallInst *CI = B.CreateCall2(StrChr, CastToCStr(Ptr, B), @@ -102,7 +102,7 @@ Value *llvm::EmitStrCpy(Value *Dst, Value *Src, IRBuilder<> &B, AttributeWithIndex AWI[2]; AWI[0] = AttributeWithIndex::get(2, Attribute::NoCapture); AWI[1] = AttributeWithIndex::get(~0u, Attribute::NoUnwind); - const Type *I8Ptr = B.getInt8PtrTy(); + Type *I8Ptr = B.getInt8PtrTy(); Value *StrCpy = M->getOrInsertFunction(Name, AttrListPtr::get(AWI, 2), I8Ptr, I8Ptr, I8Ptr, NULL); CallInst *CI = B.CreateCall2(StrCpy, CastToCStr(Dst, B), CastToCStr(Src, B), @@ -120,7 +120,7 @@ Value *llvm::EmitStrNCpy(Value *Dst, Value *Src, Value *Len, AttributeWithIndex AWI[2]; AWI[0] = AttributeWithIndex::get(2, Attribute::NoCapture); AWI[1] = AttributeWithIndex::get(~0u, Attribute::NoUnwind); - const Type *I8Ptr = B.getInt8PtrTy(); + Type *I8Ptr = B.getInt8PtrTy(); Value *StrNCpy = M->getOrInsertFunction(Name, AttrListPtr::get(AWI, 2), I8Ptr, I8Ptr, I8Ptr, Len->getType(), NULL); @@ -361,7 +361,7 @@ bool SimplifyFortifiedLibCalls::fold(CallInst *CI, const TargetData *TD) { this->CI = CI; Function *Callee = CI->getCalledFunction(); StringRef Name = Callee->getName(); - const FunctionType *FT = Callee->getFunctionType(); + FunctionType *FT = Callee->getFunctionType(); LLVMContext &Context = CI->getParent()->getContext(); IRBuilder<> B(CI); diff --git a/contrib/llvm/lib/Transforms/Utils/CloneFunction.cpp b/contrib/llvm/lib/Transforms/Utils/CloneFunction.cpp index 6ea831f..cf21f1e 100644 --- a/contrib/llvm/lib/Transforms/Utils/CloneFunction.cpp +++ b/contrib/llvm/lib/Transforms/Utils/CloneFunction.cpp @@ -331,15 +331,10 @@ ConstantFoldMappedInstruction(const Instruction *I) { TD); if (const LoadInst *LI = dyn_cast<LoadInst>(I)) - if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ops[0])) - if (!LI->isVolatile() && CE->getOpcode() == Instruction::GetElementPtr) - if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0))) - if (GV->isConstant() && GV->hasDefinitiveInitializer()) - return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), - CE); - - return ConstantFoldInstOperands(I->getOpcode(), I->getType(), &Ops[0], - Ops.size(), TD); + if (!LI->isVolatile()) + return ConstantFoldLoadFromConstPtr(Ops[0], TD); + + return ConstantFoldInstOperands(I->getOpcode(), I->getType(), Ops, TD); } /// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto, diff --git a/contrib/llvm/lib/Transforms/Utils/CloneModule.cpp b/contrib/llvm/lib/Transforms/Utils/CloneModule.cpp index a08fa35..a0e027b 100644 --- a/contrib/llvm/lib/Transforms/Utils/CloneModule.cpp +++ b/contrib/llvm/lib/Transforms/Utils/CloneModule.cpp @@ -50,10 +50,12 @@ Module *llvm::CloneModule(const Module *M, ValueToValueMapTy &VMap) { I != E; ++I) { GlobalVariable *GV = new GlobalVariable(*New, I->getType()->getElementType(), - false, - GlobalValue::ExternalLinkage, 0, - I->getName()); - GV->setAlignment(I->getAlignment()); + I->isConstant(), I->getLinkage(), + (Constant*) 0, I->getName(), + (GlobalVariable*) 0, + I->isThreadLocal(), + I->getType()->getAddressSpace()); + GV->copyAttributesFrom(I); VMap[I] = GV; } @@ -61,16 +63,19 @@ Module *llvm::CloneModule(const Module *M, ValueToValueMapTy &VMap) { for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) { Function *NF = Function::Create(cast<FunctionType>(I->getType()->getElementType()), - GlobalValue::ExternalLinkage, I->getName(), New); + I->getLinkage(), I->getName(), New); NF->copyAttributesFrom(I); VMap[I] = NF; } // Loop over the aliases in the module for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); - I != E; ++I) - VMap[I] = new GlobalAlias(I->getType(), GlobalAlias::ExternalLinkage, - I->getName(), NULL, New); + I != E; ++I) { + GlobalAlias *GA = new GlobalAlias(I->getType(), I->getLinkage(), + I->getName(), NULL, New); + GA->copyAttributesFrom(I); + VMap[I] = GA; + } // Now that all of the things that global variable initializer can refer to // have been created, loop through and copy the global variable referrers @@ -81,9 +86,6 @@ Module *llvm::CloneModule(const Module *M, ValueToValueMapTy &VMap) { GlobalVariable *GV = cast<GlobalVariable>(VMap[I]); if (I->hasInitializer()) GV->setInitializer(MapValue(I->getInitializer(), VMap)); - GV->setLinkage(I->getLinkage()); - GV->setThreadLocal(I->isThreadLocal()); - GV->setConstant(I->isConstant()); } // Similarly, copy over function bodies now... @@ -101,15 +103,12 @@ Module *llvm::CloneModule(const Module *M, ValueToValueMapTy &VMap) { SmallVector<ReturnInst*, 8> Returns; // Ignore returns cloned. CloneFunctionInto(F, I, VMap, /*ModuleLevelChanges=*/true, Returns); } - - F->setLinkage(I->getLinkage()); } // And aliases for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); I != E; ++I) { GlobalAlias *GA = cast<GlobalAlias>(VMap[I]); - GA->setLinkage(I->getLinkage()); if (const Constant *C = I->getAliasee()) GA->setAliasee(MapValue(C, VMap)); } diff --git a/contrib/llvm/lib/Transforms/Utils/CodeExtractor.cpp b/contrib/llvm/lib/Transforms/Utils/CodeExtractor.cpp index 0813523..5f47ebb 100644 --- a/contrib/llvm/lib/Transforms/Utils/CodeExtractor.cpp +++ b/contrib/llvm/lib/Transforms/Utils/CodeExtractor.cpp @@ -50,14 +50,14 @@ namespace { DominatorTree* DT; bool AggregateArgs; unsigned NumExitBlocks; - const Type *RetTy; + Type *RetTy; public: CodeExtractor(DominatorTree* dt = 0, bool AggArgs = false) : DT(dt), AggregateArgs(AggArgs||AggregateArgsOpt), NumExitBlocks(~0U) {} - Function *ExtractCodeRegion(const std::vector<BasicBlock*> &code); + Function *ExtractCodeRegion(ArrayRef<BasicBlock*> code); - bool isEligible(const std::vector<BasicBlock*> &code); + bool isEligible(ArrayRef<BasicBlock*> code); private: /// definedInRegion - Return true if the specified value is defined in the @@ -290,7 +290,7 @@ Function *CodeExtractor::constructFunction(const Values &inputs, paramTy.clear(); paramTy.push_back(StructPtr); } - const FunctionType *funcType = + FunctionType *funcType = FunctionType::get(RetTy, paramTy, false); // Create the new function @@ -317,8 +317,7 @@ Function *CodeExtractor::constructFunction(const Values &inputs, Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i); TerminatorInst *TI = newFunction->begin()->getTerminator(); GetElementPtrInst *GEP = - GetElementPtrInst::Create(AI, Idx, Idx+2, - "gep_" + inputs[i]->getName(), TI); + GetElementPtrInst::Create(AI, Idx, "gep_" + inputs[i]->getName(), TI); RewriteVal = new LoadInst(GEP, "loadgep_" + inputs[i]->getName(), TI); } else RewriteVal = AI++; @@ -420,7 +419,7 @@ emitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer, Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i); GetElementPtrInst *GEP = - GetElementPtrInst::Create(Struct, Idx, Idx + 2, + GetElementPtrInst::Create(Struct, Idx, "gep_" + StructValues[i]->getName()); codeReplacer->getInstList().push_back(GEP); StoreInst *SI = new StoreInst(StructValues[i], GEP); @@ -446,7 +445,7 @@ emitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer, Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i); GetElementPtrInst *GEP - = GetElementPtrInst::Create(Struct, Idx, Idx + 2, + = GetElementPtrInst::Create(Struct, Idx, "gep_reload_" + outputs[i]->getName()); codeReplacer->getInstList().push_back(GEP); Output = GEP; @@ -561,7 +560,7 @@ emitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer, Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut+out); GetElementPtrInst *GEP = - GetElementPtrInst::Create(OAI, Idx, Idx + 2, + GetElementPtrInst::Create(OAI, Idx, "gep_" + outputs[out]->getName(), NTRet); new StoreInst(outputs[out], GEP, NTRet); @@ -580,7 +579,7 @@ emitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer, } // Now that we've done the deed, simplify the switch instruction. - const Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType(); + Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType(); switch (NumExitBlocks) { case 0: // There are no successors (the block containing the switch itself), which @@ -655,7 +654,7 @@ void CodeExtractor::moveCodeToFunction(Function *newFunction) { /// computed result back into memory. /// Function *CodeExtractor:: -ExtractCodeRegion(const std::vector<BasicBlock*> &code) { +ExtractCodeRegion(ArrayRef<BasicBlock*> code) { if (!isEligible(code)) return 0; @@ -755,9 +754,13 @@ ExtractCodeRegion(const std::vector<BasicBlock*> &code) { return newFunction; } -bool CodeExtractor::isEligible(const std::vector<BasicBlock*> &code) { +bool CodeExtractor::isEligible(ArrayRef<BasicBlock*> code) { + // Deny a single basic block that's a landing pad block. + if (code.size() == 1 && code[0]->isLandingPad()) + return false; + // Deny code region if it contains allocas or vastarts. - for (std::vector<BasicBlock*>::const_iterator BB = code.begin(), e=code.end(); + for (ArrayRef<BasicBlock*>::iterator BB = code.begin(), e=code.end(); BB != e; ++BB) for (BasicBlock::const_iterator I = (*BB)->begin(), Ie = (*BB)->end(); I != Ie; ++I) @@ -771,25 +774,23 @@ bool CodeExtractor::isEligible(const std::vector<BasicBlock*> &code) { } -/// ExtractCodeRegion - slurp a sequence of basic blocks into a brand new -/// function +/// ExtractCodeRegion - Slurp a sequence of basic blocks into a brand new +/// function. /// Function* llvm::ExtractCodeRegion(DominatorTree &DT, - const std::vector<BasicBlock*> &code, + ArrayRef<BasicBlock*> code, bool AggregateArgs) { return CodeExtractor(&DT, AggregateArgs).ExtractCodeRegion(code); } -/// ExtractBasicBlock - slurp a natural loop into a brand new function +/// ExtractLoop - Slurp a natural loop into a brand new function. /// Function* llvm::ExtractLoop(DominatorTree &DT, Loop *L, bool AggregateArgs) { return CodeExtractor(&DT, AggregateArgs).ExtractCodeRegion(L->getBlocks()); } -/// ExtractBasicBlock - slurp a basic block into a brand new function +/// ExtractBasicBlock - Slurp a basic block into a brand new function. /// -Function* llvm::ExtractBasicBlock(BasicBlock *BB, bool AggregateArgs) { - std::vector<BasicBlock*> Blocks; - Blocks.push_back(BB); - return CodeExtractor(0, AggregateArgs).ExtractCodeRegion(Blocks); +Function* llvm::ExtractBasicBlock(ArrayRef<BasicBlock*> BBs, bool AggregateArgs){ + return CodeExtractor(0, AggregateArgs).ExtractCodeRegion(BBs); } diff --git a/contrib/llvm/lib/Transforms/Utils/InlineFunction.cpp b/contrib/llvm/lib/Transforms/Utils/InlineFunction.cpp index d5b382e..5464dbc 100644 --- a/contrib/llvm/lib/Transforms/Utils/InlineFunction.cpp +++ b/contrib/llvm/lib/Transforms/Utils/InlineFunction.cpp @@ -45,6 +45,9 @@ bool llvm::InlineFunction(InvokeInst *II, InlineFunctionInfo &IFI) { return InlineFunction(CallSite(II), IFI); } +// FIXME: New EH - Remove the functions marked [LIBUNWIND] when new EH is +// turned on. + /// [LIBUNWIND] Look for an llvm.eh.exception call in the given block. static EHExceptionInst *findExceptionInBlock(BasicBlock *bb) { for (BasicBlock::iterator i = bb->begin(), e = bb->end(); i != e; i++) { @@ -250,20 +253,32 @@ namespace { PHINode *InnerSelectorPHI; SmallVector<Value*, 8> UnwindDestPHIValues; + // FIXME: New EH - These will replace the analogous ones above. + BasicBlock *OuterResumeDest; //< Destination of the invoke's unwind. + BasicBlock *InnerResumeDest; //< Destination for the callee's resume. + LandingPadInst *CallerLPad; //< LandingPadInst associated with the invoke. + PHINode *InnerEHValuesPHI; //< PHI for EH values from landingpad insts. + public: - InvokeInliningInfo(InvokeInst *II) : - OuterUnwindDest(II->getUnwindDest()), OuterSelector(0), - InnerUnwindDest(0), InnerExceptionPHI(0), InnerSelectorPHI(0) { - - // If there are PHI nodes in the unwind destination block, we - // need to keep track of which values came into them from the - // invoke before removing the edge from this block. - llvm::BasicBlock *invokeBB = II->getParent(); - for (BasicBlock::iterator I = OuterUnwindDest->begin(); - isa<PHINode>(I); ++I) { + InvokeInliningInfo(InvokeInst *II) + : OuterUnwindDest(II->getUnwindDest()), OuterSelector(0), + InnerUnwindDest(0), InnerExceptionPHI(0), InnerSelectorPHI(0), + OuterResumeDest(II->getUnwindDest()), InnerResumeDest(0), + CallerLPad(0), InnerEHValuesPHI(0) { + // If there are PHI nodes in the unwind destination block, we need to keep + // track of which values came into them from the invoke before removing + // the edge from this block. + llvm::BasicBlock *InvokeBB = II->getParent(); + BasicBlock::iterator I = OuterUnwindDest->begin(); + for (; isa<PHINode>(I); ++I) { // Save the value to use for this edge. - PHINode *phi = cast<PHINode>(I); - UnwindDestPHIValues.push_back(phi->getIncomingValueForBlock(invokeBB)); + PHINode *PHI = cast<PHINode>(I); + UnwindDestPHIValues.push_back(PHI->getIncomingValueForBlock(InvokeBB)); + } + + // FIXME: With the new EH, this if/dyn_cast should be a 'cast'. + if (LandingPadInst *LPI = dyn_cast<LandingPadInst>(I)) { + CallerLPad = LPI; } } @@ -281,11 +296,23 @@ namespace { BasicBlock *getInnerUnwindDest(); + // FIXME: New EH - Rename when new EH is turned on. + BasicBlock *getInnerUnwindDestNewEH(); + + LandingPadInst *getLandingPadInst() const { return CallerLPad; } + bool forwardEHResume(CallInst *call, BasicBlock *src); - /// Add incoming-PHI values to the unwind destination block for - /// the given basic block, using the values for the original - /// invoke's source block. + /// forwardResume - Forward the 'resume' instruction to the caller's landing + /// pad block. When the landing pad block has only one predecessor, this is + /// a simple branch. When there is more than one predecessor, we need to + /// split the landing pad block after the landingpad instruction and jump + /// to there. + void forwardResume(ResumeInst *RI); + + /// addIncomingPHIValuesFor - Add incoming-PHI values to the unwind + /// destination block for the given basic block, using the values for the + /// original invoke's source block. void addIncomingPHIValuesFor(BasicBlock *BB) const { addIncomingPHIValuesForInto(BB, OuterUnwindDest); } @@ -300,7 +327,7 @@ namespace { }; } -/// Get or create a target for the branch out of rewritten calls to +/// [LIBUNWIND] Get or create a target for the branch out of rewritten calls to /// llvm.eh.resume. BasicBlock *InvokeInliningInfo::getInnerUnwindDest() { if (InnerUnwindDest) return InnerUnwindDest; @@ -404,6 +431,60 @@ bool InvokeInliningInfo::forwardEHResume(CallInst *call, BasicBlock *src) { return true; } +/// Get or create a target for the branch from ResumeInsts. +BasicBlock *InvokeInliningInfo::getInnerUnwindDestNewEH() { + // FIXME: New EH - rename this function when new EH is turned on. + if (InnerResumeDest) return InnerResumeDest; + + // Split the landing pad. + BasicBlock::iterator SplitPoint = CallerLPad; ++SplitPoint; + InnerResumeDest = + OuterResumeDest->splitBasicBlock(SplitPoint, + OuterResumeDest->getName() + ".body"); + + // The number of incoming edges we expect to the inner landing pad. + const unsigned PHICapacity = 2; + + // Create corresponding new PHIs for all the PHIs in the outer landing pad. + BasicBlock::iterator InsertPoint = InnerResumeDest->begin(); + BasicBlock::iterator I = OuterResumeDest->begin(); + for (unsigned i = 0, e = UnwindDestPHIValues.size(); i != e; ++i, ++I) { + PHINode *OuterPHI = cast<PHINode>(I); + PHINode *InnerPHI = PHINode::Create(OuterPHI->getType(), PHICapacity, + OuterPHI->getName() + ".lpad-body", + InsertPoint); + OuterPHI->replaceAllUsesWith(InnerPHI); + InnerPHI->addIncoming(OuterPHI, OuterResumeDest); + } + + // Create a PHI for the exception values. + InnerEHValuesPHI = PHINode::Create(CallerLPad->getType(), PHICapacity, + "eh.lpad-body", InsertPoint); + CallerLPad->replaceAllUsesWith(InnerEHValuesPHI); + InnerEHValuesPHI->addIncoming(CallerLPad, OuterResumeDest); + + // All done. + return InnerResumeDest; +} + +/// forwardResume - Forward the 'resume' instruction to the caller's landing pad +/// block. When the landing pad block has only one predecessor, this is a simple +/// branch. When there is more than one predecessor, we need to split the +/// landing pad block after the landingpad instruction and jump to there. +void InvokeInliningInfo::forwardResume(ResumeInst *RI) { + BasicBlock *Dest = getInnerUnwindDestNewEH(); + BasicBlock *Src = RI->getParent(); + + BranchInst::Create(Dest, Src); + + // Update the PHIs in the destination. They were inserted in an order which + // makes this work. + addIncomingPHIValuesForInto(Src, Dest); + + InnerEHValuesPHI->addIncoming(RI->getOperand(0), Src); + RI->eraseFromParent(); +} + /// [LIBUNWIND] Check whether this selector is "only cleanups": /// call i32 @llvm.eh.selector(blah, blah, i32 0) static bool isCleanupOnlySelector(EHSelectorInst *selector) { @@ -421,9 +502,19 @@ static bool isCleanupOnlySelector(EHSelectorInst *selector) { /// Returns true to indicate that the next block should be skipped. static bool HandleCallsInBlockInlinedThroughInvoke(BasicBlock *BB, InvokeInliningInfo &Invoke) { + LandingPadInst *LPI = Invoke.getLandingPadInst(); + for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) { Instruction *I = BBI++; - + + if (LPI) // FIXME: New EH - This won't be NULL in the new EH. + if (LandingPadInst *L = dyn_cast<LandingPadInst>(I)) { + unsigned NumClauses = LPI->getNumClauses(); + L->reserveClauses(NumClauses); + for (unsigned i = 0; i != NumClauses; ++i) + L->addClause(LPI->getClause(i)); + } + // We only need to check for function calls: inlined invoke // instructions require no special handling. CallInst *CI = dyn_cast<CallInst>(I); @@ -557,6 +648,10 @@ static void HandleInlinedInvoke(InvokeInst *II, BasicBlock *FirstNewBlock, // there is now a new entry in them. Invoke.addIncomingPHIValuesFor(BB); } + + if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator())) { + Invoke.forwardResume(RI); + } } // Now that everything is happy, we have one final detail. The PHI nodes in @@ -636,7 +731,7 @@ static Value *HandleByValArgument(Value *Arg, Instruction *TheCall, const Function *CalledFunc, InlineFunctionInfo &IFI, unsigned ByValAlignment) { - const Type *AggTy = cast<PointerType>(Arg->getType())->getElementType(); + Type *AggTy = cast<PointerType>(Arg->getType())->getElementType(); // If the called function is readonly, then it could not mutate the caller's // copy of the byval'd memory. In this case, it is safe to elide the copy and @@ -726,7 +821,7 @@ static bool isUsedByLifetimeMarker(Value *V) { // hasLifetimeMarkers - Check whether the given alloca already has // lifetime.start or lifetime.end intrinsics. static bool hasLifetimeMarkers(AllocaInst *AI) { - const Type *Int8PtrTy = Type::getInt8PtrTy(AI->getType()->getContext()); + Type *Int8PtrTy = Type::getInt8PtrTy(AI->getType()->getContext()); if (AI->getType() == Int8PtrTy) return isUsedByLifetimeMarker(AI); @@ -770,8 +865,15 @@ static void fixupLineNumbers(Function *Fn, Function::iterator FI, for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ++BI) { DebugLoc DL = BI->getDebugLoc(); - if (!DL.isUnknown()) + if (!DL.isUnknown()) { BI->setDebugLoc(updateInlinedAtInfo(DL, TheCallDL, BI->getContext())); + if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(BI)) { + LLVMContext &Ctx = BI->getContext(); + MDNode *InlinedAt = BI->getDebugLoc().getInlinedAt(Ctx); + DVI->setOperand(2, createInlinedVariable(DVI->getVariable(), + InlinedAt, Ctx)); + } + } } } } @@ -822,6 +924,40 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI) { return false; } + // Find the personality function used by the landing pads of the caller. If it + // exists, then check to see that it matches the personality function used in + // the callee. + for (Function::const_iterator + I = Caller->begin(), E = Caller->end(); I != E; ++I) + if (const InvokeInst *II = dyn_cast<InvokeInst>(I->getTerminator())) { + const BasicBlock *BB = II->getUnwindDest(); + // FIXME: This 'isa' here should become go away once the new EH system is + // in place. + if (!isa<LandingPadInst>(BB->getFirstNonPHI())) + continue; + const LandingPadInst *LP = cast<LandingPadInst>(BB->getFirstNonPHI()); + const Value *CallerPersFn = LP->getPersonalityFn(); + + // If the personality functions match, then we can perform the + // inlining. Otherwise, we can't inline. + // TODO: This isn't 100% true. Some personality functions are proper + // supersets of others and can be used in place of the other. + for (Function::const_iterator + I = CalledFunc->begin(), E = CalledFunc->end(); I != E; ++I) + if (const InvokeInst *II = dyn_cast<InvokeInst>(I->getTerminator())) { + const BasicBlock *BB = II->getUnwindDest(); + // FIXME: This 'if/dyn_cast' here should become a normal 'cast' once + // the new EH system is in place. + if (const LandingPadInst *LP = + dyn_cast<LandingPadInst>(BB->getFirstNonPHI())) + if (CallerPersFn != LP->getPersonalityFn()) + return false; + break; + } + + break; + } + // Get an iterator to the last basic block in the function, which will have // the new function inlined after it. // @@ -1090,7 +1226,7 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI) { // Handle all of the return instructions that we just cloned in, and eliminate // any users of the original call/invoke instruction. - const Type *RTy = CalledFunc->getReturnType(); + Type *RTy = CalledFunc->getReturnType(); PHINode *PHI = 0; if (Returns.size() > 1) { diff --git a/contrib/llvm/lib/Transforms/Utils/Local.cpp b/contrib/llvm/lib/Transforms/Utils/Local.cpp index 0f6d9ae..7034feb 100644 --- a/contrib/llvm/lib/Transforms/Utils/Local.cpp +++ b/contrib/llvm/lib/Transforms/Utils/Local.cpp @@ -27,7 +27,6 @@ #include "llvm/Analysis/DebugInfo.h" #include "llvm/Analysis/DIBuilder.h" #include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/ProfileInfo.h" #include "llvm/Analysis/ValueTracking.h" @@ -227,13 +226,17 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions) { bool llvm::isInstructionTriviallyDead(Instruction *I) { if (!I->use_empty() || isa<TerminatorInst>(I)) return false; + // We don't want the landingpad instruction removed by anything this general. + if (isa<LandingPadInst>(I)) + return false; + // We don't want debug info removed by anything this general, unless // debug info is empty. if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) { - if (DDI->getAddress()) + if (DDI->getAddress()) return false; return true; - } + } if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) { if (DVI->getValue()) return false; @@ -244,10 +247,16 @@ bool llvm::isInstructionTriviallyDead(Instruction *I) { // Special case intrinsics that "may have side effects" but can be deleted // when dead. - if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) + if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { // Safe to delete llvm.stacksave if dead. if (II->getIntrinsicID() == Intrinsic::stacksave) return true; + + // Lifetime intrinsics are dead when their right-hand is undef. + if (II->getIntrinsicID() == Intrinsic::lifetime_start || + II->getIntrinsicID() == Intrinsic::lifetime_end) + return isa<UndefValue>(II->getArgOperand(1)); + } return false; } @@ -712,10 +721,14 @@ bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { /// their preferred alignment from the beginning. /// static unsigned enforceKnownAlignment(Value *V, unsigned Align, - unsigned PrefAlign) { + unsigned PrefAlign, const TargetData *TD) { V = V->stripPointerCasts(); if (AllocaInst *AI = dyn_cast<AllocaInst>(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)) + return Align; // If there is a requested alignment and if this is an alloca, round up. if (AI->getAlignment() >= PrefAlign) return AI->getAlignment(); @@ -766,7 +779,7 @@ unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, Align = std::min(Align, +Value::MaximumAlignment); if (PrefAlign > Align) - Align = enforceKnownAlignment(V, Align, PrefAlign); + Align = enforceKnownAlignment(V, Align, PrefAlign, TD); // We don't need to make any adjustment. return Align; diff --git a/contrib/llvm/lib/Transforms/Utils/LoopSimplify.cpp b/contrib/llvm/lib/Transforms/Utils/LoopSimplify.cpp index e79fb5a..cbd54a8 100644 --- a/contrib/llvm/lib/Transforms/Utils/LoopSimplify.cpp +++ b/contrib/llvm/lib/Transforms/Utils/LoopSimplify.cpp @@ -213,7 +213,7 @@ ReprocessLoop: // predecessors from outside of the loop, split the edge now. SmallVector<BasicBlock*, 8> ExitBlocks; L->getExitBlocks(ExitBlocks); - + SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); for (SmallSetVector<BasicBlock *, 8>::iterator I = ExitBlockSet.begin(), @@ -325,6 +325,14 @@ ReprocessLoop: DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block " << ExitingBlock->getName() << "\n"); + // If any reachable control flow within this loop has changed, notify + // ScalarEvolution. Currently assume the parent loop doesn't change + // (spliting edges doesn't count). If blocks, CFG edges, or other values + // in the parent loop change, then we need call to forgetLoop() for the + // parent instead. + if (SE) + SE->forgetLoop(L); + assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock)); Changed = true; LI->removeBlock(ExitingBlock); @@ -402,13 +410,24 @@ BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { } assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); - BasicBlock *NewBB = SplitBlockPredecessors(Exit, &LoopBlocks[0], - LoopBlocks.size(), ".loopexit", - this); + BasicBlock *NewExitBB = 0; + + if (Exit->isLandingPad()) { + SmallVector<BasicBlock*, 2> NewBBs; + SplitLandingPadPredecessors(Exit, ArrayRef<BasicBlock*>(&LoopBlocks[0], + LoopBlocks.size()), + ".loopexit", ".nonloopexit", + this, NewBBs); + NewExitBB = NewBBs[0]; + } else { + NewExitBB = SplitBlockPredecessors(Exit, &LoopBlocks[0], + LoopBlocks.size(), ".loopexit", + this); + } DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block " - << NewBB->getName() << "\n"); - return NewBB; + << NewExitBB->getName() << "\n"); + return NewExitBB; } /// AddBlockAndPredsToSet - Add the specified block, and all of its @@ -467,23 +486,23 @@ void LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB, if (&*BBI == SplitPreds[i]) return; } - + // If it isn't already after an outside block, move it after one. This is // always good as it makes the uncond branch from the outside block into a // fall-through. - + // Figure out *which* outside block to put this after. Prefer an outside // block that neighbors a BB actually in the loop. BasicBlock *FoundBB = 0; for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { Function::iterator BBI = SplitPreds[i]; - if (++BBI != NewBB->getParent()->end() && + if (++BBI != NewBB->getParent()->end() && L->contains(BBI)) { FoundBB = SplitPreds[i]; break; } } - + // If our heuristic for a *good* bb to place this after doesn't find // anything, just pick something. It's likely better than leaving it within // the loop. @@ -544,7 +563,7 @@ Loop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM) { // Make sure that NewBB is put someplace intelligent, which doesn't mess up // code layout too horribly. PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L); - + // Create the new outer loop. Loop *NewOuter = new Loop(); @@ -735,6 +754,7 @@ void LoopSimplify::verifyAnalysis() const { } assert(HasIndBrPred && "LoopSimplify has no excuse for missing loop header info!"); + (void)HasIndBrPred; } // Indirectbr can interfere with exit block canonicalization. @@ -742,12 +762,15 @@ void LoopSimplify::verifyAnalysis() const { bool HasIndBrExiting = false; SmallVector<BasicBlock*, 8> ExitingBlocks; L->getExitingBlocks(ExitingBlocks); - for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) + for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { if (isa<IndirectBrInst>((ExitingBlocks[i])->getTerminator())) { HasIndBrExiting = true; break; } + } + assert(HasIndBrExiting && "LoopSimplify has no excuse for missing exit block info!"); + (void)HasIndBrExiting; } } diff --git a/contrib/llvm/lib/Transforms/Utils/LoopUnroll.cpp b/contrib/llvm/lib/Transforms/Utils/LoopUnroll.cpp index 6772511..62e4fa2 100644 --- a/contrib/llvm/lib/Transforms/Utils/LoopUnroll.cpp +++ b/contrib/llvm/lib/Transforms/Utils/LoopUnroll.cpp @@ -11,9 +11,6 @@ // actual pass or policy, but provides a single function to perform loop // unrolling. // -// It works best when loops have been canonicalized by the -indvars pass, -// allowing it to determine the trip counts of loops easily. -// // The process of unrolling can produce extraneous basic blocks linked with // unconditional branches. This will be corrected in the future. // @@ -24,6 +21,7 @@ #include "llvm/BasicBlock.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Support/Debug.h" @@ -31,6 +29,7 @@ #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Utils/SimplifyIndVar.h" using namespace llvm; // TODO: Should these be here or in LoopUnroll? @@ -61,7 +60,8 @@ static inline void RemapInstruction(Instruction *I, /// only has one predecessor, and that predecessor only has one successor. /// The LoopInfo Analysis that is passed will be kept consistent. /// Returns the new combined block. -static BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI) { +static BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI, + LPPassManager *LPM) { // Merge basic blocks into their predecessor if there is only one distinct // pred, and if there is only one distinct successor of the predecessor, and // if there are no PHI nodes. @@ -93,6 +93,12 @@ static BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI) { std::string OldName = BB->getName(); // Erase basic block from the function... + + // ScalarEvolution holds references to loop exit blocks. + if (ScalarEvolution *SE = LPM->getAnalysisIfAvailable<ScalarEvolution>()) { + if (Loop *L = LI->getLoopFor(BB)) + SE->forgetLoop(L); + } LI->removeBlock(BB); BB->eraseFromParent(); @@ -109,12 +115,27 @@ static BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI) { /// branch instruction. However, if the trip count (and multiple) are not known, /// loop unrolling will mostly produce more code that is no faster. /// +/// TripCount is generally defined as the number of times the loop header +/// executes. UnrollLoop relaxes the definition to permit early exits: here +/// TripCount is the iteration on which control exits LatchBlock if no early +/// exits were taken. Note that UnrollLoop assumes that the loop counter test +/// terminates LatchBlock in order to remove unnecesssary instances of the +/// test. In other words, control may exit the loop prior to TripCount +/// iterations via an early branch, but control may not exit the loop from the +/// LatchBlock's terminator prior to TripCount iterations. +/// +/// Similarly, TripMultiple divides the number of times that the LatchBlock may +/// execute without exiting the loop. +/// /// The LoopInfo Analysis that is passed will be kept consistent. /// /// If a LoopPassManager is passed in, and the loop is fully removed, it will be /// removed from the LoopPassManager as well. LPM can also be NULL. -bool llvm::UnrollLoop(Loop *L, unsigned Count, - LoopInfo *LI, LPPassManager *LPM) { +/// +/// This utility preserves LoopInfo. If DominatorTree or ScalarEvolution are +/// available it must also preserve those analyses. +bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, + unsigned TripMultiple, LoopInfo *LI, LPPassManager *LPM) { BasicBlock *Preheader = L->getLoopPreheader(); if (!Preheader) { DEBUG(dbgs() << " Can't unroll; loop preheader-insertion failed.\n"); @@ -129,14 +150,14 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, BasicBlock *Header = L->getHeader(); BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator()); - + if (!BI || BI->isUnconditional()) { // The loop-rotate pass can be helpful to avoid this in many cases. DEBUG(dbgs() << " Can't unroll; loop not terminated by a conditional branch.\n"); return false; } - + if (Header->hasAddressTaken()) { // The loop-rotate pass can be helpful to avoid this in many cases. DEBUG(dbgs() << @@ -146,16 +167,10 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, // Notify ScalarEvolution that the loop will be substantially changed, // if not outright eliminated. - if (ScalarEvolution *SE = LPM->getAnalysisIfAvailable<ScalarEvolution>()) + ScalarEvolution *SE = LPM->getAnalysisIfAvailable<ScalarEvolution>(); + if (SE) SE->forgetLoop(L); - // Find trip count - unsigned TripCount = L->getSmallConstantTripCount(); - // Find trip multiple if count is not available - unsigned TripMultiple = 1; - if (TripCount == 0) - TripMultiple = L->getSmallConstantTripMultiple(); - if (TripCount != 0) DEBUG(dbgs() << " Trip Count = " << TripCount << "\n"); if (TripMultiple != 1) @@ -208,12 +223,7 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, ValueToValueMapTy LastValueMap; std::vector<PHINode*> OrigPHINode; for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { - PHINode *PN = cast<PHINode>(I); - OrigPHINode.push_back(PN); - if (Instruction *I = - dyn_cast<Instruction>(PN->getIncomingValueForBlock(LatchBlock))) - if (L->contains(I)) - LastValueMap[I] = I; + OrigPHINode.push_back(cast<PHINode>(I)); } std::vector<BasicBlock*> Headers; @@ -221,11 +231,20 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, Headers.push_back(Header); Latches.push_back(LatchBlock); + // The current on-the-fly SSA update requires blocks to be processed in + // reverse postorder so that LastValueMap contains the correct value at each + // exit. + LoopBlocksDFS DFS(L); + DFS.perform(LI); + + // Stash the DFS iterators before adding blocks to the loop. + LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO(); + LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO(); + for (unsigned It = 1; It != Count; ++It) { std::vector<BasicBlock*> NewBlocks; - - for (std::vector<BasicBlock*>::iterator BB = LoopBlocks.begin(), - E = LoopBlocks.end(); BB != E; ++BB) { + + for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) { ValueToValueMapTy VMap; BasicBlock *New = CloneBasicBlock(*BB, VMap, "." + Twine(It)); Header->getParent()->getBasicBlockList().push_back(New); @@ -251,75 +270,55 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, L->addBasicBlockToLoop(New, LI->getBase()); - // Add phi entries for newly created values to all exit blocks except - // the successor of the latch block. The successor of the exit block will - // be updated specially after unrolling all the way. - if (*BB != LatchBlock) - for (succ_iterator SI = succ_begin(*BB), SE = succ_end(*BB); SI != SE; - ++SI) - if (!L->contains(*SI)) - for (BasicBlock::iterator BBI = (*SI)->begin(); - PHINode *phi = dyn_cast<PHINode>(BBI); ++BBI) { - Value *Incoming = phi->getIncomingValueForBlock(*BB); - phi->addIncoming(Incoming, New); - } - + // Add phi entries for newly created values to all exit blocks. + for (succ_iterator SI = succ_begin(*BB), SE = succ_end(*BB); + SI != SE; ++SI) { + if (L->contains(*SI)) + continue; + for (BasicBlock::iterator BBI = (*SI)->begin(); + PHINode *phi = dyn_cast<PHINode>(BBI); ++BBI) { + Value *Incoming = phi->getIncomingValueForBlock(*BB); + ValueToValueMapTy::iterator It = LastValueMap.find(Incoming); + if (It != LastValueMap.end()) + Incoming = It->second; + phi->addIncoming(Incoming, New); + } + } // Keep track of new headers and latches as we create them, so that // we can insert the proper branches later. if (*BB == Header) Headers.push_back(New); - if (*BB == LatchBlock) { + if (*BB == LatchBlock) Latches.push_back(New); - // Also, clear out the new latch's back edge so that it doesn't look - // like a new loop, so that it's amenable to being merged with adjacent - // blocks later on. - TerminatorInst *Term = New->getTerminator(); - assert(L->contains(Term->getSuccessor(!ContinueOnTrue))); - assert(Term->getSuccessor(ContinueOnTrue) == LoopExit); - Term->setSuccessor(!ContinueOnTrue, NULL); - } - NewBlocks.push_back(New); } - + // Remap all instructions in the most recent iteration for (unsigned i = 0; i < NewBlocks.size(); ++i) for (BasicBlock::iterator I = NewBlocks[i]->begin(), E = NewBlocks[i]->end(); I != E; ++I) ::RemapInstruction(I, LastValueMap); } - - // The latch block exits the loop. If there are any PHI nodes in the - // successor blocks, update them to use the appropriate values computed as the - // last iteration of the loop. - if (Count != 1) { - BasicBlock *LastIterationBB = cast<BasicBlock>(LastValueMap[LatchBlock]); - for (succ_iterator SI = succ_begin(LatchBlock), SE = succ_end(LatchBlock); - SI != SE; ++SI) { - for (BasicBlock::iterator BBI = (*SI)->begin(); - PHINode *PN = dyn_cast<PHINode>(BBI); ++BBI) { - Value *InVal = PN->removeIncomingValue(LatchBlock, false); - // If this value was defined in the loop, take the value defined by the - // last iteration of the loop. - if (Instruction *InValI = dyn_cast<Instruction>(InVal)) { - if (L->contains(InValI)) - InVal = LastValueMap[InVal]; - } - PN->addIncoming(InVal, LastIterationBB); - } - } - } - // Now, if we're doing complete unrolling, loop over the PHI nodes in the - // original block, setting them to their incoming values. - if (CompletelyUnroll) { - BasicBlock *Preheader = L->getLoopPreheader(); - for (unsigned i = 0, e = OrigPHINode.size(); i != e; ++i) { - PHINode *PN = OrigPHINode[i]; + // Loop over the PHI nodes in the original block, setting incoming values. + for (unsigned i = 0, e = OrigPHINode.size(); i != e; ++i) { + PHINode *PN = OrigPHINode[i]; + if (CompletelyUnroll) { PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader)); Header->getInstList().erase(PN); } + else if (Count > 1) { + Value *InVal = PN->removeIncomingValue(LatchBlock, false); + // If this value was defined in the loop, take the value defined by the + // last iteration of the loop. + if (Instruction *InValI = dyn_cast<Instruction>(InVal)) { + if (L->contains(InValI)) + InVal = LastValueMap[InVal]; + } + assert(Latches.back() == LastValueMap[LatchBlock] && "bad last latch"); + PN->addIncoming(InVal, Latches.back()); + } } // Now that all the basic blocks for the unrolled iterations are in place, @@ -351,6 +350,19 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, // iteration. Term->setSuccessor(!ContinueOnTrue, Dest); } else { + // Remove phi operands at this loop exit + if (Dest != LoopExit) { + BasicBlock *BB = Latches[i]; + for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); + SI != SE; ++SI) { + if (*SI == Headers[i]) + continue; + for (BasicBlock::iterator BBI = (*SI)->begin(); + PHINode *Phi = dyn_cast<PHINode>(BBI); ++BBI) { + Phi->removeIncomingValue(BB, false); + } + } + } // Replace the conditional branch with an unconditional one. BranchInst::Create(Dest, Term); Term->eraseFromParent(); @@ -362,11 +374,29 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, BranchInst *Term = cast<BranchInst>(Latches[i]->getTerminator()); if (Term->isUnconditional()) { BasicBlock *Dest = Term->getSuccessor(0); - if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI)) + if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI, LPM)) std::replace(Latches.begin(), Latches.end(), Dest, Fold); } } - + + // FIXME: Reconstruct dom info, because it is not preserved properly. + // Incrementally updating domtree after loop unrolling would be easy. + if (DominatorTree *DT = LPM->getAnalysisIfAvailable<DominatorTree>()) + DT->runOnFunction(*L->getHeader()->getParent()); + + // Simplify any new induction variables in the partially unrolled loop. + if (SE && !CompletelyUnroll) { + SmallVector<WeakVH, 16> DeadInsts; + simplifyLoopIVs(L, SE, LPM, DeadInsts); + + // Aggressively clean up dead instructions that simplifyLoopIVs already + // identified. Any remaining should be cleaned up below. + while (!DeadInsts.empty()) + if (Instruction *Inst = + dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val())) + RecursivelyDeleteTriviallyDeadInstructions(Inst); + } + // At this point, the code is well formed. We now do a quick sweep over the // inserted code, doing constant propagation and dead code elimination as we // go. diff --git a/contrib/llvm/lib/Transforms/Utils/LowerExpectIntrinsic.cpp b/contrib/llvm/lib/Transforms/Utils/LowerExpectIntrinsic.cpp index c1213fa..61ab3f6 100644 --- a/contrib/llvm/lib/Transforms/Utils/LowerExpectIntrinsic.cpp +++ b/contrib/llvm/lib/Transforms/Utils/LowerExpectIntrinsic.cpp @@ -58,7 +58,7 @@ bool LowerExpectIntrinsic::HandleSwitchExpect(SwitchInst *SI) { return false; LLVMContext &Context = CI->getContext(); - const Type *Int32Ty = Type::getInt32Ty(Context); + Type *Int32Ty = Type::getInt32Ty(Context); unsigned caseNo = SI->findCaseValue(ExpectedValue); std::vector<Value *> Vec; @@ -105,7 +105,7 @@ bool LowerExpectIntrinsic::HandleIfExpect(BranchInst *BI) { return false; LLVMContext &Context = CI->getContext(); - const Type *Int32Ty = Type::getInt32Ty(Context); + Type *Int32Ty = Type::getInt32Ty(Context); bool Likely = ExpectedValue->isOne(); // If expect value is equal to 1 it means that we are more likely to take diff --git a/contrib/llvm/lib/Transforms/Utils/LowerInvoke.cpp b/contrib/llvm/lib/Transforms/Utils/LowerInvoke.cpp index f77d19d..c96c8fc 100644 --- a/contrib/llvm/lib/Transforms/Utils/LowerInvoke.cpp +++ b/contrib/llvm/lib/Transforms/Utils/LowerInvoke.cpp @@ -120,18 +120,18 @@ FunctionPass *llvm::createLowerInvokePass(const TargetLowering *TLI, // doInitialization - Make sure that there is a prototype for abort in the // current module. bool LowerInvoke::doInitialization(Module &M) { - const Type *VoidPtrTy = Type::getInt8PtrTy(M.getContext()); + Type *VoidPtrTy = Type::getInt8PtrTy(M.getContext()); if (useExpensiveEHSupport) { // Insert a type for the linked list of jump buffers. unsigned JBSize = TLI ? TLI->getJumpBufSize() : 0; JBSize = JBSize ? JBSize : 200; Type *JmpBufTy = ArrayType::get(VoidPtrTy, JBSize); - JBLinkTy = StructType::createNamed(M.getContext(), "llvm.sjljeh.jmpbufty"); + JBLinkTy = StructType::create(M.getContext(), "llvm.sjljeh.jmpbufty"); Type *Elts[] = { JmpBufTy, PointerType::getUnqual(JBLinkTy) }; JBLinkTy->setBody(Elts); - const Type *PtrJBList = PointerType::getUnqual(JBLinkTy); + Type *PtrJBList = PointerType::getUnqual(JBLinkTy); // Now that we've done that, insert the jmpbuf list head global, unless it // already exists. @@ -240,14 +240,14 @@ void LowerInvoke::rewriteExpensiveInvoke(InvokeInst *II, unsigned InvokeNo, CallInst* StackSaveRet = CallInst::Create(StackSaveFn, "ssret", II); new StoreInst(StackSaveRet, StackPtr, true, II); // volatile - BasicBlock::iterator NI = II->getNormalDest()->getFirstNonPHI(); + BasicBlock::iterator NI = II->getNormalDest()->getFirstInsertionPt(); // nonvolatile. new StoreInst(Constant::getNullValue(Type::getInt32Ty(II->getContext())), InvokeNum, false, NI); - Instruction* StackPtrLoad = new LoadInst(StackPtr, "stackptr.restore", true, - II->getUnwindDest()->getFirstNonPHI() - ); + Instruction* StackPtrLoad = + new LoadInst(StackPtr, "stackptr.restore", true, + II->getUnwindDest()->getFirstInsertionPt()); CallInst::Create(StackRestoreFn, StackPtrLoad, "")->insertAfter(StackPtrLoad); // Add a switch case to our unwind block. @@ -305,7 +305,7 @@ splitLiveRangesLiveAcrossInvokes(SmallVectorImpl<InvokeInst*> &Invokes) { ++AfterAllocaInsertPt; for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; ++AI) { - const Type *Ty = AI->getType(); + Type *Ty = AI->getType(); // Aggregate types can't be cast, but are legal argument types, so we have // to handle them differently. We use an extract/insert pair as a // lightweight method to achieve the same goal. @@ -406,6 +406,7 @@ bool LowerInvoke::insertExpensiveEHSupport(Function &F) { SmallVector<ReturnInst*,16> Returns; SmallVector<UnwindInst*,16> Unwinds; SmallVector<InvokeInst*,16> Invokes; + UnreachableInst* UnreachablePlaceholder = 0; for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { @@ -455,8 +456,7 @@ bool LowerInvoke::insertExpensiveEHSupport(Function &F) { Value *Idx[] = { Constant::getNullValue(Type::getInt32Ty(F.getContext())), ConstantInt::get(Type::getInt32Ty(F.getContext()), 1) }; - OldJmpBufPtr = GetElementPtrInst::Create(JmpBuf, &Idx[0], &Idx[2], - "OldBuf", + OldJmpBufPtr = GetElementPtrInst::Create(JmpBuf, Idx, "OldBuf", EntryBB->getTerminator()); // Copy the JBListHead to the alloca. @@ -487,9 +487,10 @@ bool LowerInvoke::insertExpensiveEHSupport(Function &F) { // Insert a load in the Catch block, and a switch on its value. By default, // we go to a block that just does an unwind (which is the correct action - // for a standard call). + // for a standard call). We insert an unreachable instruction here and + // modify the block to jump to the correct unwinding pad later. BasicBlock *UnwindBB = BasicBlock::Create(F.getContext(), "unwindbb", &F); - Unwinds.push_back(new UnwindInst(F.getContext(), UnwindBB)); + UnreachablePlaceholder = new UnreachableInst(F.getContext(), UnwindBB); Value *CatchLoad = new LoadInst(InvokeNum, "invoke.num", true, CatchBB); SwitchInst *CatchSwitch = @@ -502,8 +503,7 @@ bool LowerInvoke::insertExpensiveEHSupport(Function &F) { "setjmp.cont"); Idx[1] = ConstantInt::get(Type::getInt32Ty(F.getContext()), 0); - Value *JmpBufPtr = GetElementPtrInst::Create(JmpBuf, &Idx[0], &Idx[2], - "TheJmpBuf", + Value *JmpBufPtr = GetElementPtrInst::Create(JmpBuf, Idx, "TheJmpBuf", EntryBB->getTerminator()); JmpBufPtr = new BitCastInst(JmpBufPtr, Type::getInt8PtrTy(F.getContext()), @@ -557,8 +557,7 @@ bool LowerInvoke::insertExpensiveEHSupport(Function &F) { // Get a pointer to the jmpbuf and longjmp. Value *Idx[] = { Constant::getNullValue(Type::getInt32Ty(F.getContext())), ConstantInt::get(Type::getInt32Ty(F.getContext()), 0) }; - Idx[0] = GetElementPtrInst::Create(BufPtr, &Idx[0], &Idx[2], "JmpBuf", - UnwindBlock); + Idx[0] = GetElementPtrInst::Create(BufPtr, Idx, "JmpBuf", UnwindBlock); Idx[0] = new BitCastInst(Idx[0], Type::getInt8PtrTy(F.getContext()), "tmp", UnwindBlock); @@ -580,6 +579,12 @@ bool LowerInvoke::insertExpensiveEHSupport(Function &F) { Unwinds[i]->eraseFromParent(); } + // Replace the inserted unreachable with a branch to the unwind handler. + if (UnreachablePlaceholder) { + BranchInst::Create(UnwindHandler, UnreachablePlaceholder); + UnreachablePlaceholder->eraseFromParent(); + } + // Finally, for any returns from this function, if this function contains an // invoke, restore the old jmpbuf pointer to its input value. if (OldJmpBufPtr) { diff --git a/contrib/llvm/lib/Transforms/Utils/LowerSwitch.cpp b/contrib/llvm/lib/Transforms/Utils/LowerSwitch.cpp index ed733d3..686178c 100644 --- a/contrib/llvm/lib/Transforms/Utils/LowerSwitch.cpp +++ b/contrib/llvm/lib/Transforms/Utils/LowerSwitch.cpp @@ -277,11 +277,11 @@ void LowerSwitch::processSwitchInst(SwitchInst *SI) { BasicBlock *CurBlock = SI->getParent(); BasicBlock *OrigBlock = CurBlock; Function *F = CurBlock->getParent(); - Value *Val = SI->getOperand(0); // The value we are switching on... + Value *Val = SI->getCondition(); // The value we are switching on... BasicBlock* Default = SI->getDefaultDest(); // If there is only the default destination, don't bother with the code below. - if (SI->getNumOperands() == 2) { + if (SI->getNumCases() == 1) { BranchInst::Create(SI->getDefaultDest(), CurBlock); CurBlock->getInstList().erase(SI); return; diff --git a/contrib/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/contrib/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp index e5a00f4..db3e942 100644 --- a/contrib/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ b/contrib/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -86,11 +86,15 @@ bool llvm::isAllocaPromotable(const AllocaInst *AI) { UI != UE; ++UI) { // Loop over all of the uses of the alloca const User *U = *UI; if (const LoadInst *LI = dyn_cast<LoadInst>(U)) { + // Note that atomic loads can be transformed; atomic semantics do + // not have any meaning for a local alloca. if (LI->isVolatile()) return false; } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) { if (SI->getOperand(0) == AI) return false; // Don't allow a store OF the AI, only INTO the AI. + // Note that atomic stores can be transformed; atomic semantics do + // not have any meaning for a local alloca. if (SI->isVolatile()) return false; } else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(U)) { diff --git a/contrib/llvm/lib/Transforms/Utils/SSAUpdater.cpp b/contrib/llvm/lib/Transforms/Utils/SSAUpdater.cpp index b47a7cc..fa8061c 100644 --- a/contrib/llvm/lib/Transforms/Utils/SSAUpdater.cpp +++ b/contrib/llvm/lib/Transforms/Utils/SSAUpdater.cpp @@ -16,6 +16,7 @@ #include "llvm/Instructions.h" #include "llvm/IntrinsicInst.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/TinyPtrVector.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Support/AlignOf.h" #include "llvm/Support/Allocator.h" @@ -43,7 +44,7 @@ SSAUpdater::~SSAUpdater() { /// Initialize - Reset this object to get ready for a new set of SSA /// updates with type 'Ty'. PHI nodes get a name based on 'Name'. -void SSAUpdater::Initialize(const Type *Ty, StringRef Name) { +void SSAUpdater::Initialize(Type *Ty, StringRef Name) { if (AV == 0) AV = new AvailableValsTy(); else @@ -378,8 +379,7 @@ run(const SmallVectorImpl<Instruction*> &Insts) const { // First step: bucket up uses of the alloca by the block they occur in. // This is important because we have to handle multiple defs/uses in a block // ourselves: SSAUpdater is purely for cross-block references. - // FIXME: Want a TinyVector<Instruction*> since there is often 0/1 element. - DenseMap<BasicBlock*, std::vector<Instruction*> > UsesByBlock; + DenseMap<BasicBlock*, TinyPtrVector<Instruction*> > UsesByBlock; for (unsigned i = 0, e = Insts.size(); i != e; ++i) { Instruction *User = Insts[i]; @@ -395,7 +395,7 @@ run(const SmallVectorImpl<Instruction*> &Insts) const { for (unsigned i = 0, e = Insts.size(); i != e; ++i) { Instruction *User = Insts[i]; BasicBlock *BB = User->getParent(); - std::vector<Instruction*> &BlockUses = UsesByBlock[BB]; + TinyPtrVector<Instruction*> &BlockUses = UsesByBlock[BB]; // If this block has already been processed, ignore this repeat use. if (BlockUses.empty()) continue; diff --git a/contrib/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/contrib/llvm/lib/Transforms/Utils/SimplifyCFG.cpp index 9d9c324..b8c3ab4 100644 --- a/contrib/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/contrib/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -63,6 +63,7 @@ class SimplifyCFGOpt { bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI, IRBuilder<> &Builder); + bool SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder); bool SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder); bool SimplifyUnwind(UnwindInst *UI, IRBuilder<> &Builder); bool SimplifyUnreachable(UnreachableInst *UI); @@ -322,7 +323,7 @@ static ConstantInt *GetConstantInt(Value *V, const TargetData *TD) { // This is some kind of pointer constant. Turn it into a pointer-sized // ConstantInt if possible. - const IntegerType *PtrTy = TD->getIntPtrType(V->getContext()); + IntegerType *PtrTy = TD->getIntPtrType(V->getContext()); // Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*). if (isa<ConstantPointerNull>(V)) @@ -2138,6 +2139,52 @@ static bool SimplifyBranchOnICmpChain(BranchInst *BI, const TargetData *TD, return true; } +bool SimplifyCFGOpt::SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder) { + // If this is a trivial landing pad that just continues unwinding the caught + // exception then zap the landing pad, turning its invokes into calls. + BasicBlock *BB = RI->getParent(); + LandingPadInst *LPInst = dyn_cast<LandingPadInst>(BB->getFirstNonPHI()); + if (RI->getValue() != LPInst) + // Not a landing pad, or the resume is not unwinding the exception that + // caused control to branch here. + return false; + + // Check that there are no other instructions except for debug intrinsics. + BasicBlock::iterator I = LPInst, E = RI; + while (++I != E) + if (!isa<DbgInfoIntrinsic>(I)) + return false; + + // Turn all invokes that unwind here into calls and delete the basic block. + for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) { + InvokeInst *II = cast<InvokeInst>((*PI++)->getTerminator()); + SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3); + // Insert a call instruction before the invoke. + CallInst *Call = CallInst::Create(II->getCalledValue(), Args, "", II); + Call->takeName(II); + Call->setCallingConv(II->getCallingConv()); + Call->setAttributes(II->getAttributes()); + Call->setDebugLoc(II->getDebugLoc()); + + // Anything that used the value produced by the invoke instruction now uses + // the value produced by the call instruction. Note that we do this even + // for void functions and calls with no uses so that the callgraph edge is + // updated. + II->replaceAllUsesWith(Call); + BB->removePredecessor(II->getParent()); + + // Insert a branch to the normal destination right before the invoke. + BranchInst::Create(II->getNormalDest(), II); + + // Finally, delete the invoke instruction! + II->eraseFromParent(); + } + + // The landingpad is now unreachable. Zap it. + BB->eraseFromParent(); + return true; +} + bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) { BasicBlock *BB = RI->getParent(); if (!BB->getFirstNonPHIOrDbg()->isTerminator()) return false; @@ -2244,18 +2291,34 @@ bool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) { while (UI != BB->begin()) { BasicBlock::iterator BBI = UI; --BBI; - // Do not delete instructions that can have side effects, like calls - // (which may never return) and volatile loads and stores. + // Do not delete instructions that can have side effects which might cause + // the unreachable to not be reachable; specifically, calls and volatile + // operations may have this effect. if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI)) break; - - if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) - if (SI->isVolatile()) - break; - - if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) - if (LI->isVolatile()) + + if (BBI->mayHaveSideEffects()) { + if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { + if (SI->isVolatile()) + break; + } else if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) { + if (LI->isVolatile()) + break; + } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(BBI)) { + if (RMWI->isVolatile()) + break; + } else if (AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(BBI)) { + if (CXI->isVolatile()) + break; + } else if (!isa<FenceInst>(BBI) && !isa<VAArgInst>(BBI) && + !isa<LandingPadInst>(BBI)) { break; - + } + // Note that deleting LandingPad's here is in fact okay, although it + // involves a bit of subtle reasoning. If this inst is a LandingPad, + // all the predecessors of this block will be the unwind edges of Invokes, + // and we can therefore guarantee this block will be erased. + } + // Delete this instruction (any uses are guaranteed to be dead) if (!BBI->use_empty()) BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); @@ -2707,6 +2770,71 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { return false; } +/// Check if passing a value to an instruction will cause undefined behavior. +static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) { + Constant *C = dyn_cast<Constant>(V); + if (!C) + return false; + + if (!I->hasOneUse()) // Only look at single-use instructions, for compile time + return false; + + if (C->isNullValue()) { + Instruction *Use = I->use_back(); + + // Now make sure that there are no instructions in between that can alter + // control flow (eg. calls) + for (BasicBlock::iterator i = ++BasicBlock::iterator(I); &*i != Use; ++i) + if (i == I->getParent()->end() || i->mayHaveSideEffects()) + return false; + + // Look through GEPs. A load from a GEP derived from NULL is still undefined + if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Use)) + if (GEP->getPointerOperand() == I) + return passingValueIsAlwaysUndefined(V, GEP); + + // Look through bitcasts. + if (BitCastInst *BC = dyn_cast<BitCastInst>(Use)) + return passingValueIsAlwaysUndefined(V, BC); + + // Load from null is undefined. + if (LoadInst *LI = dyn_cast<LoadInst>(Use)) + return LI->getPointerAddressSpace() == 0; + + // Store to null is undefined. + if (StoreInst *SI = dyn_cast<StoreInst>(Use)) + return SI->getPointerAddressSpace() == 0 && SI->getPointerOperand() == I; + } + return false; +} + +/// If BB has an incoming value that will always trigger undefined behavior +/// (eg. null pointer derefence), remove the branch leading here. +static bool removeUndefIntroducingPredecessor(BasicBlock *BB) { + for (BasicBlock::iterator i = BB->begin(); + PHINode *PHI = dyn_cast<PHINode>(i); ++i) + for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) + if (passingValueIsAlwaysUndefined(PHI->getIncomingValue(i), PHI)) { + TerminatorInst *T = PHI->getIncomingBlock(i)->getTerminator(); + IRBuilder<> Builder(T); + if (BranchInst *BI = dyn_cast<BranchInst>(T)) { + BB->removePredecessor(PHI->getIncomingBlock(i)); + // Turn uncoditional branches into unreachables and remove the dead + // destination from conditional branches. + if (BI->isUnconditional()) + Builder.CreateUnreachable(); + else + Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1) : + BI->getSuccessor(0)); + BI->eraseFromParent(); + return true; + } + // TODO: SwitchInst. + } + + return false; +} + bool SimplifyCFGOpt::run(BasicBlock *BB) { bool Changed = false; @@ -2730,6 +2858,9 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) { // Check for and eliminate duplicate PHI nodes in this block. Changed |= EliminateDuplicatePHINodes(BB); + // Check for and remove branches that will always cause undefined behavior. + Changed |= removeUndefIntroducingPredecessor(BB); + // Merge basic blocks into their predecessor if there is only one distinct // pred, and if there is only one distinct successor of the predecessor, and // if there are no PHI nodes. @@ -2752,6 +2883,8 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) { } else { if (SimplifyCondBranch(BI, Builder)) return true; } + } else if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator())) { + if (SimplifyResume(RI, Builder)) return true; } else if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { if (SimplifyReturn(RI, Builder)) return true; } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { diff --git a/contrib/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp b/contrib/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp new file mode 100644 index 0000000..76289c0 --- /dev/null +++ b/contrib/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp @@ -0,0 +1,432 @@ +//===-- SimplifyIndVar.cpp - Induction variable simplification ------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements induction variable simplification. It does +// not define any actual pass or policy, but provides a single function to +// simplify a loop's induction variables based on ScalarEvolution. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "indvars" + +#include "llvm/Instructions.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/IVUsers.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/SimplifyIndVar.h" +#include "llvm/Target/TargetData.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" + +using namespace llvm; + +STATISTIC(NumElimIdentity, "Number of IV identities eliminated"); +STATISTIC(NumElimOperand, "Number of IV operands folded into a use"); +STATISTIC(NumElimRem , "Number of IV remainder operations eliminated"); +STATISTIC(NumElimCmp , "Number of IV comparisons eliminated"); + +namespace { + /// SimplifyIndvar - This is a utility for simplifying induction variables + /// based on ScalarEvolution. It is the primary instrument of the + /// IndvarSimplify pass, but it may also be directly invoked to cleanup after + /// other loop passes that preserve SCEV. + class SimplifyIndvar { + Loop *L; + LoopInfo *LI; + DominatorTree *DT; + ScalarEvolution *SE; + IVUsers *IU; // NULL for DisableIVRewrite + const TargetData *TD; // May be NULL + + SmallVectorImpl<WeakVH> &DeadInsts; + + bool Changed; + + public: + SimplifyIndvar(Loop *Loop, ScalarEvolution *SE, LPPassManager *LPM, + SmallVectorImpl<WeakVH> &Dead, IVUsers *IVU = NULL) : + L(Loop), + LI(LPM->getAnalysisIfAvailable<LoopInfo>()), + SE(SE), + IU(IVU), + TD(LPM->getAnalysisIfAvailable<TargetData>()), + DeadInsts(Dead), + Changed(false) { + assert(LI && "IV simplification requires LoopInfo"); + } + + bool hasChanged() const { return Changed; } + + /// Iteratively perform simplification on a worklist of users of the + /// specified induction variable. This is the top-level driver that applies + /// all simplicitions to users of an IV. + void simplifyUsers(PHINode *CurrIV, IVVisitor *V = NULL); + + Value *foldIVUser(Instruction *UseInst, Instruction *IVOperand); + + bool eliminateIVUser(Instruction *UseInst, Instruction *IVOperand); + void eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand); + void eliminateIVRemainder(BinaryOperator *Rem, Value *IVOperand, + bool IsSigned); + }; +} + +/// foldIVUser - Fold an IV operand into its use. This removes increments of an +/// aligned IV when used by a instruction that ignores the low bits. +/// +/// IVOperand is guaranteed SCEVable, but UseInst may not be. +/// +/// Return the operand of IVOperand for this induction variable if IVOperand can +/// be folded (in case more folding opportunities have been exposed). +/// Otherwise return null. +Value *SimplifyIndvar::foldIVUser(Instruction *UseInst, Instruction *IVOperand) { + Value *IVSrc = 0; + unsigned OperIdx = 0; + const SCEV *FoldedExpr = 0; + switch (UseInst->getOpcode()) { + default: + return 0; + case Instruction::UDiv: + case Instruction::LShr: + // We're only interested in the case where we know something about + // the numerator and have a constant denominator. + if (IVOperand != UseInst->getOperand(OperIdx) || + !isa<ConstantInt>(UseInst->getOperand(1))) + return 0; + + // Attempt to fold a binary operator with constant operand. + // e.g. ((I + 1) >> 2) => I >> 2 + if (IVOperand->getNumOperands() != 2 || + !isa<ConstantInt>(IVOperand->getOperand(1))) + return 0; + + IVSrc = IVOperand->getOperand(0); + // IVSrc must be the (SCEVable) IV, since the other operand is const. + assert(SE->isSCEVable(IVSrc->getType()) && "Expect SCEVable IV operand"); + + ConstantInt *D = cast<ConstantInt>(UseInst->getOperand(1)); + if (UseInst->getOpcode() == Instruction::LShr) { + // Get a constant for the divisor. See createSCEV. + uint32_t BitWidth = cast<IntegerType>(UseInst->getType())->getBitWidth(); + if (D->getValue().uge(BitWidth)) + return 0; + + D = ConstantInt::get(UseInst->getContext(), + APInt(BitWidth, 1).shl(D->getZExtValue())); + } + FoldedExpr = SE->getUDivExpr(SE->getSCEV(IVSrc), SE->getSCEV(D)); + } + // We have something that might fold it's operand. Compare SCEVs. + if (!SE->isSCEVable(UseInst->getType())) + return 0; + + // Bypass the operand if SCEV can prove it has no effect. + if (SE->getSCEV(UseInst) != FoldedExpr) + return 0; + + DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand + << " -> " << *UseInst << '\n'); + + UseInst->setOperand(OperIdx, IVSrc); + assert(SE->getSCEV(UseInst) == FoldedExpr && "bad SCEV with folded oper"); + + ++NumElimOperand; + Changed = true; + if (IVOperand->use_empty()) + DeadInsts.push_back(IVOperand); + return IVSrc; +} + +/// eliminateIVComparison - SimplifyIVUsers helper for eliminating useless +/// comparisons against an induction variable. +void SimplifyIndvar::eliminateIVComparison(ICmpInst *ICmp, Value *IVOperand) { + unsigned IVOperIdx = 0; + ICmpInst::Predicate Pred = ICmp->getPredicate(); + if (IVOperand != ICmp->getOperand(0)) { + // Swapped + assert(IVOperand == ICmp->getOperand(1) && "Can't find IVOperand"); + IVOperIdx = 1; + Pred = ICmpInst::getSwappedPredicate(Pred); + } + + // Get the SCEVs for the ICmp operands. + const SCEV *S = SE->getSCEV(ICmp->getOperand(IVOperIdx)); + const SCEV *X = SE->getSCEV(ICmp->getOperand(1 - IVOperIdx)); + + // Simplify unnecessary loops away. + const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent()); + S = SE->getSCEVAtScope(S, ICmpLoop); + X = SE->getSCEVAtScope(X, ICmpLoop); + + // If the condition is always true or always false, replace it with + // a constant value. + if (SE->isKnownPredicate(Pred, S, X)) + ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext())); + else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X)) + ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext())); + else + return; + + DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n'); + ++NumElimCmp; + Changed = true; + DeadInsts.push_back(ICmp); +} + +/// eliminateIVRemainder - SimplifyIVUsers helper for eliminating useless +/// remainder operations operating on an induction variable. +void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem, + Value *IVOperand, + bool IsSigned) { + // We're only interested in the case where we know something about + // the numerator. + if (IVOperand != Rem->getOperand(0)) + return; + + // Get the SCEVs for the ICmp operands. + const SCEV *S = SE->getSCEV(Rem->getOperand(0)); + const SCEV *X = SE->getSCEV(Rem->getOperand(1)); + + // Simplify unnecessary loops away. + const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent()); + S = SE->getSCEVAtScope(S, ICmpLoop); + X = SE->getSCEVAtScope(X, ICmpLoop); + + // i % n --> i if i is in [0,n). + if ((!IsSigned || SE->isKnownNonNegative(S)) && + SE->isKnownPredicate(IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, + S, X)) + Rem->replaceAllUsesWith(Rem->getOperand(0)); + else { + // (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n). + const SCEV *LessOne = + SE->getMinusSCEV(S, SE->getConstant(S->getType(), 1)); + if (IsSigned && !SE->isKnownNonNegative(LessOne)) + return; + + if (!SE->isKnownPredicate(IsSigned ? + ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, + LessOne, X)) + return; + + ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ, + Rem->getOperand(0), Rem->getOperand(1)); + SelectInst *Sel = + SelectInst::Create(ICmp, + ConstantInt::get(Rem->getType(), 0), + Rem->getOperand(0), "tmp", Rem); + Rem->replaceAllUsesWith(Sel); + } + + // Inform IVUsers about the new users. + if (IU) { + if (Instruction *I = dyn_cast<Instruction>(Rem->getOperand(0))) + IU->AddUsersIfInteresting(I); + } + DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n'); + ++NumElimRem; + Changed = true; + DeadInsts.push_back(Rem); +} + +/// eliminateIVUser - Eliminate an operation that consumes a simple IV and has +/// no observable side-effect given the range of IV values. +/// IVOperand is guaranteed SCEVable, but UseInst may not be. +bool SimplifyIndvar::eliminateIVUser(Instruction *UseInst, + Instruction *IVOperand) { + if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) { + eliminateIVComparison(ICmp, IVOperand); + return true; + } + if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) { + bool IsSigned = Rem->getOpcode() == Instruction::SRem; + if (IsSigned || Rem->getOpcode() == Instruction::URem) { + eliminateIVRemainder(Rem, IVOperand, IsSigned); + return true; + } + } + + // Eliminate any operation that SCEV can prove is an identity function. + if (!SE->isSCEVable(UseInst->getType()) || + (UseInst->getType() != IVOperand->getType()) || + (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand))) + return false; + + DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst << '\n'); + + UseInst->replaceAllUsesWith(IVOperand); + ++NumElimIdentity; + Changed = true; + DeadInsts.push_back(UseInst); + return true; +} + +/// pushIVUsers - Add all uses of Def to the current IV's worklist. +/// +static void pushIVUsers( + Instruction *Def, + SmallPtrSet<Instruction*,16> &Simplified, + SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) { + + for (Value::use_iterator UI = Def->use_begin(), E = Def->use_end(); + UI != E; ++UI) { + Instruction *User = cast<Instruction>(*UI); + + // Avoid infinite or exponential worklist processing. + // Also ensure unique worklist users. + // If Def is a LoopPhi, it may not be in the Simplified set, so check for + // self edges first. + if (User != Def && Simplified.insert(User)) + SimpleIVUsers.push_back(std::make_pair(User, Def)); + } +} + +/// isSimpleIVUser - Return true if this instruction generates a simple SCEV +/// expression in terms of that IV. +/// +/// This is similar to IVUsers' isInteresting() but processes each instruction +/// non-recursively when the operand is already known to be a simpleIVUser. +/// +static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE) { + if (!SE->isSCEVable(I->getType())) + return false; + + // Get the symbolic expression for this instruction. + const SCEV *S = SE->getSCEV(I); + + // Only consider affine recurrences. + const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S); + if (AR && AR->getLoop() == L) + return true; + + return false; +} + +/// simplifyUsers - Iteratively perform simplification on a worklist of users +/// of the specified induction variable. Each successive simplification may push +/// more users which may themselves be candidates for simplification. +/// +/// This algorithm does not require IVUsers analysis. Instead, it simplifies +/// instructions in-place during analysis. Rather than rewriting induction +/// variables bottom-up from their users, it transforms a chain of IVUsers +/// top-down, updating the IR only when it encouters a clear optimization +/// opportunitiy. +/// +/// Once DisableIVRewrite is default, LSR will be the only client of IVUsers. +/// +void SimplifyIndvar::simplifyUsers(PHINode *CurrIV, IVVisitor *V) { + if (!SE->isSCEVable(CurrIV->getType())) + return; + + // Instructions processed by SimplifyIndvar for CurrIV. + SmallPtrSet<Instruction*,16> Simplified; + + // Use-def pairs if IV users waiting to be processed for CurrIV. + SmallVector<std::pair<Instruction*, Instruction*>, 8> SimpleIVUsers; + + // Push users of the current LoopPhi. In rare cases, pushIVUsers may be + // called multiple times for the same LoopPhi. This is the proper thing to + // do for loop header phis that use each other. + pushIVUsers(CurrIV, Simplified, SimpleIVUsers); + + while (!SimpleIVUsers.empty()) { + std::pair<Instruction*, Instruction*> UseOper = + SimpleIVUsers.pop_back_val(); + // Bypass back edges to avoid extra work. + if (UseOper.first == CurrIV) continue; + + Instruction *IVOperand = UseOper.second; + for (unsigned N = 0; IVOperand; ++N) { + assert(N <= Simplified.size() && "runaway iteration"); + + Value *NewOper = foldIVUser(UseOper.first, IVOperand); + if (!NewOper) + break; // done folding + IVOperand = dyn_cast<Instruction>(NewOper); + } + if (!IVOperand) + continue; + + if (eliminateIVUser(UseOper.first, IVOperand)) { + pushIVUsers(IVOperand, Simplified, SimpleIVUsers); + continue; + } + CastInst *Cast = dyn_cast<CastInst>(UseOper.first); + if (V && Cast) { + V->visitCast(Cast); + continue; + } + if (isSimpleIVUser(UseOper.first, L, SE)) { + pushIVUsers(UseOper.first, Simplified, SimpleIVUsers); + } + } +} + +namespace llvm { + +/// simplifyUsersOfIV - Simplify instructions that use this induction variable +/// by using ScalarEvolution to analyze the IV's recurrence. +bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, LPPassManager *LPM, + SmallVectorImpl<WeakVH> &Dead, IVVisitor *V) +{ + LoopInfo *LI = &LPM->getAnalysis<LoopInfo>(); + SimplifyIndvar SIV(LI->getLoopFor(CurrIV->getParent()), SE, LPM, Dead); + SIV.simplifyUsers(CurrIV, V); + return SIV.hasChanged(); +} + +/// simplifyLoopIVs - Simplify users of induction variables within this +/// loop. This does not actually change or add IVs. +bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, LPPassManager *LPM, + SmallVectorImpl<WeakVH> &Dead) { + bool Changed = false; + for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) { + Changed |= simplifyUsersOfIV(cast<PHINode>(I), SE, LPM, Dead); + } + return Changed; +} + +/// simplifyIVUsers - Perform simplification on instructions recorded by the +/// IVUsers pass. +/// +/// This is the old approach to IV simplification to be replaced by +/// SimplifyLoopIVs. +bool simplifyIVUsers(IVUsers *IU, ScalarEvolution *SE, LPPassManager *LPM, + SmallVectorImpl<WeakVH> &Dead) { + SimplifyIndvar SIV(IU->getLoop(), SE, LPM, Dead); + + // Each round of simplification involves a round of eliminating operations + // followed by a round of widening IVs. A single IVUsers worklist is used + // across all rounds. The inner loop advances the user. If widening exposes + // more uses, then another pass through the outer loop is triggered. + for (IVUsers::iterator I = IU->begin(); I != IU->end(); ++I) { + Instruction *UseInst = I->getUser(); + Value *IVOperand = I->getOperandValToReplace(); + + if (ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) { + SIV.eliminateIVComparison(ICmp, IVOperand); + continue; + } + if (BinaryOperator *Rem = dyn_cast<BinaryOperator>(UseInst)) { + bool IsSigned = Rem->getOpcode() == Instruction::SRem; + if (IsSigned || Rem->getOpcode() == Instruction::URem) { + SIV.eliminateIVRemainder(Rem, IVOperand, IsSigned); + continue; + } + } + } + return SIV.hasChanged(); +} + +} // namespace llvm diff --git a/contrib/llvm/lib/Transforms/Utils/ValueMapper.cpp b/contrib/llvm/lib/Transforms/Utils/ValueMapper.cpp index 973b105..fc2538d 100644 --- a/contrib/llvm/lib/Transforms/Utils/ValueMapper.cpp +++ b/contrib/llvm/lib/Transforms/Utils/ValueMapper.cpp @@ -183,10 +183,9 @@ void llvm::RemapInstruction(Instruction *I, ValueToValueMapTy &VMap, } } - // Remap attached metadata. Don't bother remapping DebugLoc, it can never - // have mappings to do. + // Remap attached metadata. SmallVector<std::pair<unsigned, MDNode *>, 4> MDs; - I->getAllMetadataOtherThanDebugLoc(MDs); + I->getAllMetadata(MDs); for (SmallVectorImpl<std::pair<unsigned, MDNode *> >::iterator MI = MDs.begin(), ME = MDs.end(); MI != ME; ++MI) { MDNode *Old = MI->second; |
