//
// 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.
//
//===----------------------------------------------------------------------===//
//
STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk");
STATISTIC(NumPromoted , "Number of memory locations promoted to registers");
-namespace {
- cl::opt<bool>
- DisablePromotion("disable-licm-promotion", cl::Hidden,
- cl::desc("Disable memory promotion in LICM pass"));
+static cl::opt<bool>
+DisablePromotion("disable-licm-promotion", cl::Hidden,
+ cl::desc("Disable memory promotion in LICM pass"));
+namespace {
struct VISIBILITY_HIDDEN LICM : public LoopPass {
static char ID; // Pass identification, replacement for typeid
LICM() : LoopPass((intptr_t)&ID) {}
}
bool doFinalization() {
+ // Free the values stored in the map
+ for (std::map<Loop *, AliasSetTracker *>::iterator
+ I = LoopToAliasMap.begin(), E = LoopToAliasMap.end(); I != E; ++I)
+ delete I->second;
+
LoopToAliasMap.clear();
return false;
}
std::vector<std::pair<AllocaInst*, Value*> > &PromotedValues,
std::map<Value*, AllocaInst*> &Val2AlMap);
};
-
- char LICM::ID = 0;
- RegisterPass<LICM> X("licm", "Loop Invariant Code Motion");
}
+char LICM::ID = 0;
+static RegisterPass<LICM> X("licm", "Loop Invariant Code Motion");
+
LoopPass *llvm::createLICMPass() { return new LICM(); }
/// Hoist expressions out of the specified loop. Note, alias info for inner
// 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->getTargetData().getTypeStoreSize(LI->getType());
return !pointerInvalidatedByLoop(LI->getOperand(0), Size);
} else if (CallInst *CI = dyn_cast<CallInst>(&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
// nodes in it.
I.removeFromParent();
- BasicBlock::iterator InsertPt = ExitBlocks[0]->begin();
- while (isa<PHINode>(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 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<PHINode>(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
// 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<BasicBlock*> ProcessedBlocks;
+ SmallPtrSet<BasicBlock*, 16> ProcessedBlocks;
SmallVector<BasicBlock*, 8> 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<PHINode>(*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<PointerType>(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 (isa<PointerType>(LI->getType()))
+ 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.
std::map<Value*, AllocaInst*> &ValueToAllocaMap) {
Instruction *FnStart = CurLoop->getHeader()->getParent()->begin()->begin();
- SmallVector<Instruction *, 4> LoopExits;
- SmallVector<BasicBlock *, 4> Blocks;
- CurLoop->getExitingBlocks(Blocks);
- for (SmallVector<BasicBlock *, 4>::iterator BI = Blocks.begin(),
- BE = Blocks.end(); BI != BE; ++BI) {
- BasicBlock *BB = *BI;
- LoopExits.push_back(BB->getTerminator());
- }
+ SmallVector<BasicBlock*, 4> ExitingBlocks;
+ CurLoop->getExitingBlocks(ExitingBlocks);
// Loop over all of the alias sets in the tracker object.
for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end();
// 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()->first))
+ continue;
+
+ assert(!AS.empty() &&
+ "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.
+ {
bool PointerOk = true;
for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I)
if (V->getType() != I->first->getType()) {
PointerOk = false;
break;
}
+ if (!PointerOk)
+ continue;
+ }
- // Do not promote null values because it may be unsafe to do so.
- if (isa<ConstantPointerNull>(V))
- PointerOk = false;
-
- if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(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<ConstantPointerNull>(GEP->getOperand(0)))
- PointerOk = false;
-
- // If GEP is use is not dominating loop exit then promoting
- // GEP 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<Instruction>(*UI);
- if (!Use)
- continue;
- for (SmallVector<Instruction *, 4>::iterator
- ExitI = LoopExits.begin(), ExitE = LoopExits.end();
- ExitI != ExitE; ++ExitI) {
- Instruction *Ex = *ExitI;
- if (!DT->dominates(Use, Ex)){
- PointerOk = false;
- break;
- }
- }
-
- if (!PointerOk)
- break;
- }
+ // 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<Instruction>(*UI);
+ if (!Use || !CurLoop->contains(Use->getParent()))
+ continue;
+
+ if (!isa<LoadInst>(Use) && !isa<StoreInst>(Use)) {
+ InvalidInst = true;
+ break;
}
+
+ if (!GuaranteedToExecute)
+ GuaranteedToExecute = isSafeToExecuteUnconditionally(*Use);
+ }
- if (PointerOk) {
- const Type *Ty = cast<PointerType>(V->getType())->getElementType();
- AllocaInst *AI = new AllocaInst(Ty, 0, V->getName()+".tmp", FnStart);
- PromotedValues.push_back(std::make_pair(AI, V));
+ // 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<PointerType>(V->getType())->getElementType();
+ AllocaInst *AI = new AllocaInst(Ty, 0, V->getName()+".tmp", FnStart);
+ PromotedValues.push_back(std::make_pair(AI, V));
- // Update the AST and alias analysis.
- CurAST->copyValue(V, AI);
+ // Update the AST and alias analysis.
+ CurAST->copyValue(V, AI);
- for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I)
- ValueToAllocaMap.insert(std::make_pair(I->first, AI));
+ for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I)
+ ValueToAllocaMap.insert(std::make_pair(I->first, AI));
- DOUT << "LICM: Promoting value: " << *V << "\n";
- }
- }
+ DOUT << "LICM: Promoting value: " << *V << "\n";
}
}
projects / oota-llvm.git / blobdiff