X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FLICM.cpp;h=d7ace342fcba272622a54632e9e8de2e62b1ae42;hb=c6a669b6e7fb13669abefa62c6ac4f871b84bb0b;hp=e461c887ea2b36afd56fffe608c7d5fc0a1039da;hpb=798b4afd48ebc0acc165789ab913ccd28466ef68;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp index e461c887ea2..d7ace342fcb 100644 --- a/lib/Transforms/Scalar/LICM.cpp +++ b/lib/Transforms/Scalar/LICM.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -35,6 +35,7 @@ #include "llvm/Transforms/Scalar.h" #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" +#include "llvm/IntrinsicInst.h" #include "llvm/Instructions.h" #include "llvm/Target/TargetData.h" #include "llvm/Analysis/LoopInfo.h" @@ -45,8 +46,8 @@ #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Transforms/Utils/PromoteMemToReg.h" #include "llvm/Support/CFG.h" -#include "llvm/Support/Compiler.h" #include "llvm/Support/CommandLine.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Support/Debug.h" #include "llvm/ADT/Statistic.h" #include @@ -58,14 +59,14 @@ STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk"); STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk"); STATISTIC(NumPromoted , "Number of memory locations promoted to registers"); -namespace { - cl::opt - DisablePromotion("disable-licm-promotion", cl::Hidden, - cl::desc("Disable memory promotion in LICM pass")); +static cl::opt +DisablePromotion("disable-licm-promotion", cl::Hidden, + cl::desc("Disable memory promotion in LICM pass")); - struct VISIBILITY_HIDDEN LICM : public LoopPass { +namespace { + struct LICM : public LoopPass { static char ID; // Pass identification, replacement for typeid - LICM() : LoopPass((intptr_t)&ID) {} + LICM() : LoopPass(&ID) {} virtual bool runOnLoop(Loop *L, LPPassManager &LPM); @@ -81,9 +82,15 @@ namespace { AU.addRequired(); AU.addPreserved(); AU.addPreserved(); + AU.addPreservedID(LoopSimplifyID); } bool doFinalization() { + // Free the values stored in the map + for (std::map::iterator + I = LoopToAliasMap.begin(), E = LoopToAliasMap.end(); I != E; ++I) + delete I->second; + LoopToAliasMap.clear(); return false; } @@ -153,16 +160,17 @@ namespace { // Because the exit block is not in the loop, we know we have to get _at // least_ its immediate dominator. - do { - // Get next Immediate Dominator. - IDom = IDom->getIDom(); - + IDom = IDom->getIDom(); + + while (IDom && IDom != BlockInLoopNode) { // If we have got to the header of the loop, then the instructions block // did not dominate the exit node, so we can't hoist it. if (IDom->getBlock() == LoopHeader) return false; - } while (IDom != BlockInLoopNode); + // Get next Immediate Dominator. + IDom = IDom->getIDom(); + }; return true; } @@ -211,12 +219,12 @@ namespace { std::vector > &PromotedValues, std::map &Val2AlMap); }; - - char LICM::ID = 0; - RegisterPass X("licm", "Loop Invariant Code Motion"); } -LoopPass *llvm::createLICMPass() { return new LICM(); } +char LICM::ID = 0; +static RegisterPass X("licm", "Loop Invariant Code Motion"); + +Pass *llvm::createLICMPass() { return new LICM(); } /// Hoist expressions out of the specified loop. Note, alias info for inner /// loop is not preserved so it is not a good idea to run LICM multiple @@ -247,16 +255,17 @@ bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { // Get the preheader block to move instructions into... Preheader = L->getLoopPreheader(); - assert(Preheader&&"Preheader insertion pass guarantees we have a preheader!"); // Loop over the body of this loop, looking for calls, invokes, and stores. // Because subloops have already been incorporated into AST, we skip blocks in // subloops. // - for (std::vector::const_iterator I = L->getBlocks().begin(), - E = L->getBlocks().end(); I != E; ++I) - if (LI->getLoopFor(*I) == L) // Ignore blocks in subloops... - CurAST->add(**I); // Incorporate the specified basic block + for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); + I != E; ++I) { + BasicBlock *BB = *I; + if (LI->getLoopFor(BB) == L) // Ignore blocks in subloops... + CurAST->add(*BB); // Incorporate the specified basic block + } // We want to visit all of the instructions in this loop... that are not parts // of our subloops (they have already had their invariants hoisted out of @@ -268,12 +277,14 @@ bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { // us to sink instructions in one pass, without iteration. After sinking // instructions, we perform another pass to hoist them out of the loop. // - SinkRegion(DT->getNode(L->getHeader())); - HoistRegion(DT->getNode(L->getHeader())); + if (L->hasDedicatedExits()) + SinkRegion(DT->getNode(L->getHeader())); + if (Preheader) + HoistRegion(DT->getNode(L->getHeader())); // Now that all loop invariants have been removed from the loop, promote any // memory references to scalars that we can... - if (!DisablePromotion) + if (!DisablePromotion && Preheader && L->hasDedicatedExits()) PromoteValuesInLoop(); // Clear out loops state information for the next iteration @@ -321,7 +332,6 @@ void LICM::SinkRegion(DomTreeNode *N) { } } - /// HoistRegion - Walk the specified region of the CFG (defined by all blocks /// dominated by the specified block, and that are in the current loop) in depth /// first order w.r.t the DominatorTree. This allows us to visit definitions @@ -363,31 +373,34 @@ bool LICM::canSinkOrHoistInst(Instruction &I) { if (LI->isVolatile()) return false; // Don't hoist volatile loads! + // Loads from constant memory are always safe to move, even if they end up + // in the same alias set as something that ends up being modified. + if (AA->pointsToConstantMemory(LI->getOperand(0))) + return true; + // Don't hoist loads which have may-aliased stores in loop. unsigned Size = 0; if (LI->getType()->isSized()) - Size = AA->getTargetData().getTypeSize(LI->getType()); + Size = AA->getTypeStoreSize(LI->getType()); return !pointerInvalidatedByLoop(LI->getOperand(0), Size); } else if (CallInst *CI = dyn_cast(&I)) { // Handle obvious cases efficiently. - if (Function *Callee = CI->getCalledFunction()) { - AliasAnalysis::ModRefBehavior Behavior =AA->getModRefBehavior(Callee, CI); - if (Behavior == AliasAnalysis::DoesNotAccessMemory) - return true; - else if (Behavior == AliasAnalysis::OnlyReadsMemory) { - // If this call only reads from memory and there are no writes to memory - // in the loop, we can hoist or sink the call as appropriate. - bool FoundMod = false; - for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); - I != E; ++I) { - AliasSet &AS = *I; - if (!AS.isForwardingAliasSet() && AS.isMod()) { - FoundMod = true; - break; - } + AliasAnalysis::ModRefBehavior Behavior = AA->getModRefBehavior(CI); + if (Behavior == AliasAnalysis::DoesNotAccessMemory) + return true; + else if (Behavior == AliasAnalysis::OnlyReadsMemory) { + // If this call only reads from memory and there are no writes to memory + // in the loop, we can hoist or sink the call as appropriate. + bool FoundMod = false; + for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); + I != E; ++I) { + AliasSet &AS = *I; + if (!AS.isForwardingAliasSet() && AS.isMod()) { + FoundMod = true; + break; } - if (!FoundMod) return true; } + if (!FoundMod) return true; } // FIXME: This should use mod/ref information to see if we can hoist or sink @@ -416,7 +429,7 @@ bool LICM::isNotUsedInLoop(Instruction &I) { if (PN->getIncomingValue(i) == &I) if (CurLoop->contains(PN->getIncomingBlock(i))) return false; - } else if (CurLoop->contains(User->getParent())) { + } else if (CurLoop->contains(User)) { return false; } } @@ -444,7 +457,7 @@ bool LICM::isLoopInvariantInst(Instruction &I) { /// position, and may either delete it or move it to outside of the loop. /// void LICM::sink(Instruction &I) { - DOUT << "LICM sinking instruction: " << I; + DEBUG(dbgs() << "LICM sinking instruction: " << I); SmallVector ExitBlocks; CurLoop->getExitBlocks(ExitBlocks); @@ -461,22 +474,26 @@ void LICM::sink(Instruction &I) { if (!isExitBlockDominatedByBlockInLoop(ExitBlocks[0], I.getParent())) { // Instruction is not used, just delete it. CurAST->deleteValue(&I); - if (!I.use_empty()) // If I has users in unreachable blocks, eliminate. + // If I has users in unreachable blocks, eliminate. + // If I is not void type then replaceAllUsesWith undef. + // This allows ValueHandlers and custom metadata to adjust itself. + if (!I.getType()->isVoidTy()) I.replaceAllUsesWith(UndefValue::get(I.getType())); I.eraseFromParent(); } else { // Move the instruction to the start of the exit block, after any PHI // nodes in it. I.removeFromParent(); - - BasicBlock::iterator InsertPt = ExitBlocks[0]->begin(); - while (isa(InsertPt)) ++InsertPt; + BasicBlock::iterator InsertPt = ExitBlocks[0]->getFirstNonPHI(); ExitBlocks[0]->getInstList().insert(InsertPt, &I); } - } else if (ExitBlocks.size() == 0) { + } else if (ExitBlocks.empty()) { // The instruction is actually dead if there ARE NO exit blocks. CurAST->deleteValue(&I); - if (!I.use_empty()) // If I has users in unreachable blocks, eliminate. + // If I has users in unreachable blocks, eliminate. + // If I is not void type then replaceAllUsesWith undef. + // This allows ValueHandlers and custom metadata to adjust itself. + if (!I.getType()->isVoidTy()) I.replaceAllUsesWith(UndefValue::get(I.getType())); I.eraseFromParent(); } else { @@ -487,7 +504,7 @@ void LICM::sink(Instruction &I) { // Firstly, we create a stack object to hold the value... AllocaInst *AI = 0; - if (I.getType() != Type::VoidTy) { + if (!I.getType()->isVoidTy()) { AI = new AllocaInst(I.getType(), 0, I.getName(), I.getParent()->getParent()->getEntryBlock().begin()); CurAST->add(AI); @@ -539,8 +556,7 @@ void LICM::sink(Instruction &I) { // If we haven't already processed this exit block, do so now. if (InsertedBlocks.insert(ExitBlock).second) { // Insert the code after the last PHI node... - BasicBlock::iterator InsertPt = ExitBlock->begin(); - while (isa(InsertPt)) ++InsertPt; + BasicBlock::iterator InsertPt = ExitBlock->getFirstNonPHI(); // If this is the first exit block processed, just move the original // instruction, otherwise clone the original instruction and insert @@ -583,7 +599,8 @@ void LICM::sink(Instruction &I) { /// that is safe to hoist, this instruction is called to do the dirty work. /// void LICM::hoist(Instruction &I) { - DOUT << "LICM hoisting to " << Preheader->getName() << ": " << I; + DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " + << I << "\n"); // Remove the instruction from its current basic block... but don't delete the // instruction. @@ -604,7 +621,8 @@ void LICM::hoist(Instruction &I) { /// bool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) { // If it is not a trapping instruction, it is always safe to hoist. - if (!Inst.isTrapping()) return true; + if (Inst.isSafeToSpeculativelyExecute()) + return true; // Otherwise we have to check to make sure that the instruction dominates all // of the exit blocks. If it doesn't, then there is a path out of the loop @@ -616,12 +634,6 @@ bool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) { if (Inst.getParent() == CurLoop->getHeader()) return true; - // It's always safe to load from a global or alloca. - if (isa(Inst)) - if (isa(Inst.getOperand(0)) || - isa(Inst.getOperand(0))) - return true; - // Get the exit blocks for the current loop. SmallVector ExitBlocks; CurLoop->getExitBlocks(ExitBlocks); @@ -666,7 +678,7 @@ void LICM::PromoteValuesInLoop() { // If we are promoting a pointer value, update alias information for the // inserted load. Value *LoadValue = 0; - if (isa(cast(Ptr->getType())->getElementType())) { + if (cast(Ptr->getType())->getElementType()->isPointerTy()) { // Locate a load or store through the pointer, and assign the same value // to LI as we are loading or storing. Since we know that the value is // stored in this loop, this will always succeed. @@ -697,12 +709,11 @@ void LICM::PromoteValuesInLoop() { // Scan the basic blocks in the loop, replacing uses of our pointers with // uses of the allocas in question. // - const std::vector &LoopBBs = CurLoop->getBlocks(); - for (std::vector::const_iterator I = LoopBBs.begin(), - E = LoopBBs.end(); I != E; ++I) { + for (Loop::block_iterator I = CurLoop->block_begin(), + E = CurLoop->block_end(); I != E; ++I) { + BasicBlock *BB = *I; // Rewrite all loads and stores in the block of the pointer... - for (BasicBlock::iterator II = (*I)->begin(), E = (*I)->end(); - II != E; ++II) { + for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ++II) { if (LoadInst *L = dyn_cast(II)) { std::map::iterator I = ValueToAllocaMap.find(L->getOperand(0)); @@ -723,30 +734,30 @@ void LICM::PromoteValuesInLoop() { // want to insert one copy of the code in each exit block, though the loop may // exit to the same block more than once. // - std::set ProcessedBlocks; + SmallPtrSet ProcessedBlocks; SmallVector ExitBlocks; CurLoop->getExitBlocks(ExitBlocks); - for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) - if (ProcessedBlocks.insert(ExitBlocks[i]).second) { - // Copy all of the allocas into their memory locations. - BasicBlock::iterator BI = ExitBlocks[i]->begin(); - while (isa(*BI)) - ++BI; // Skip over all of the phi nodes in the block. - Instruction *InsertPos = BI; - unsigned PVN = 0; - for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) { - // Load from the alloca. - LoadInst *LI = new LoadInst(PromotedValues[i].first, "", InsertPos); - - // If this is a pointer type, update alias info appropriately. - if (isa(LI->getType())) - CurAST->copyValue(PointerValueNumbers[PVN++], LI); - - // Store into the memory we promoted. - new StoreInst(LI, PromotedValues[i].second, InsertPos); - } + for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { + if (!ProcessedBlocks.insert(ExitBlocks[i])) + continue; + + // Copy all of the allocas into their memory locations. + BasicBlock::iterator BI = ExitBlocks[i]->getFirstNonPHI(); + Instruction *InsertPos = BI; + unsigned PVN = 0; + for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) { + // Load from the alloca. + LoadInst *LI = new LoadInst(PromotedValues[i].first, "", InsertPos); + + // If this is a pointer type, update alias info appropriately. + if (LI->getType()->isPointerTy()) + CurAST->copyValue(PointerValueNumbers[PVN++], LI); + + // Store into the memory we promoted. + new StoreInst(LI, PromotedValues[i].second, InsertPos); } + } // Now that we have done the deed, use the mem2reg functionality to promote // all of the new allocas we just created into real SSA registers. @@ -768,15 +779,6 @@ void LICM::FindPromotableValuesInLoop( std::map &ValueToAllocaMap) { Instruction *FnStart = CurLoop->getHeader()->getParent()->begin()->begin(); - SmallVector LoopExits; - SmallVector Blocks; - CurLoop->getExitingBlocks(Blocks); - for (SmallVector::iterator BI = Blocks.begin(), - BE = Blocks.end(); BI != BE; ++BI) { - BasicBlock *BB = *BI; - LoopExits.push_back(BB->getTerminator()); - } - // Loop over all of the alias sets in the tracker object. for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); I != E; ++I) { @@ -784,72 +786,76 @@ void LICM::FindPromotableValuesInLoop( // We can promote this alias set if it has a store, if it is a "Must" alias // set, if the pointer is loop invariant, and if we are not eliminating any // volatile loads or stores. - if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias() && - !AS.isVolatile() && CurLoop->isLoopInvariant(AS.begin()->first)) { - assert(AS.begin() != AS.end() && - "Must alias set should have at least one pointer element in it!"); - Value *V = AS.begin()->first; - - // Check that all of the pointers in the alias set have the same type. We - // cannot (yet) promote a memory location that is loaded and stored in - // different sizes. + if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() || + AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue())) + continue; + + assert(!AS.empty() && + "Must alias set should have at least one pointer element in it!"); + Value *V = AS.begin()->getValue(); + + // Check that all of the pointers in the alias set have the same type. We + // cannot (yet) promote a memory location that is loaded and stored in + // different sizes. + { bool PointerOk = true; for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) - if (V->getType() != I->first->getType()) { + if (V->getType() != I->getValue()->getType()) { PointerOk = false; break; } + if (!PointerOk) + continue; + } - // Do not promote null values because it may be unsafe to do so. - if (isa(V)) - PointerOk = false; - - if (GetElementPtrInst *GEP = dyn_cast(V)) { - // If GEP base is NULL then the calculated address used by Store or - // Load instruction is invalid. Do not promote this value because - // it may expose load and store instruction that are covered by - // condition which may not yet folded. - if (isa(GEP->getOperand(0))) - PointerOk = false; + // It isn't safe to promote a load/store from the loop if the load/store is + // conditional. For example, turning: + // + // for () { if (c) *P += 1; } + // + // into: + // + // tmp = *P; for () { if (c) tmp +=1; } *P = tmp; + // + // is not safe, because *P may only be valid to access if 'c' is true. + // + // It is safe to promote P if all uses are direct load/stores and if at + // least one is guaranteed to be executed. + bool GuaranteedToExecute = false; + bool InvalidInst = false; + for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); + UI != UE; ++UI) { + // Ignore instructions not in this loop. + Instruction *Use = dyn_cast(*UI); + if (!Use || !CurLoop->contains(Use)) + continue; + + if (!isa(Use) && !isa(Use)) { + InvalidInst = true; + break; } - - // If value V use is not dominating loop exit then promoting - // it may expose unsafe load and store instructions unconditinally. - if (PointerOk) - for(Value::use_iterator UI = V->use_begin(), UE = V->use_end(); - UI != UE && PointerOk; ++UI) { - Instruction *Use = dyn_cast(*UI); - if (!Use || !CurLoop->contains(Use->getParent())) - continue; - for (SmallVector::iterator - ExitI = LoopExits.begin(), ExitE = LoopExits.end(); - ExitI != ExitE; ++ExitI) { - Instruction *Ex = *ExitI; - if (!DT->dominates(Use, Ex)){ - PointerOk = false; - break; - } - } - - if (!PointerOk) - break; - } - - if (PointerOk) { - const Type *Ty = cast(V->getType())->getElementType(); - AllocaInst *AI = new AllocaInst(Ty, 0, V->getName()+".tmp", FnStart); - PromotedValues.push_back(std::make_pair(AI, V)); + if (!GuaranteedToExecute) + GuaranteedToExecute = isSafeToExecuteUnconditionally(*Use); + } - // Update the AST and alias analysis. - CurAST->copyValue(V, AI); + // If there is an non-load/store instruction in the loop, we can't promote + // it. If there isn't a guaranteed-to-execute instruction, we can't + // promote. + if (InvalidInst || !GuaranteedToExecute) + continue; + + const Type *Ty = cast(V->getType())->getElementType(); + AllocaInst *AI = new AllocaInst(Ty, 0, V->getName()+".tmp", FnStart); + PromotedValues.push_back(std::make_pair(AI, V)); - for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) - ValueToAllocaMap.insert(std::make_pair(I->first, AI)); + // Update the AST and alias analysis. + CurAST->copyValue(V, AI); - DOUT << "LICM: Promoting value: " << *V << "\n"; - } - } + for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) + ValueToAllocaMap.insert(std::make_pair(I->getValue(), AI)); + + DEBUG(dbgs() << "LICM: Promoting value: " << *V << "\n"); } }