//
// 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
while (isa<PHINode>(InsertPt)) ++InsertPt;
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.
// 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;
- }
+ // If one use of value V inside the loop is safe then it is OK to promote
+ // this value. On the otherside if there is not any unsafe use inside the
+ // loop then also it is OK to promote this value. Otherwise it is
+ // unsafe to promote this value.
+ bool oneSafeUse = false;
+ bool oneUnsafeUse = false;
+ for(Value::use_iterator UI = V->use_begin(), UE = V->use_end();
+ UI != UE; ++UI) {
+ Instruction *Use = dyn_cast<Instruction>(*UI);
+ if (!Use || !CurLoop->contains(Use->getParent()))
+ continue;
+
+ for (SmallVector<Instruction *, 4>::iterator
+ ExitI = LoopExits.begin(), ExitE = LoopExits.end();
+ ExitI != ExitE; ++ExitI) {
+ Instruction *Ex = *ExitI;
+ if (!isa<PHINode>(Use) && DT->dominates(Use, Ex)) {
+ oneSafeUse = true;
+ break;
+ } else
+ oneUnsafeUse = true;
}
- 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 (oneSafeUse)
+ break;
+ }
- // Update the AST and alias analysis.
- CurAST->copyValue(V, AI);
+ if (!oneSafeUse && oneUnsafeUse)
+ 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));
- 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->first, AI));
+
+ DOUT << "LICM: Promoting value: " << *V << "\n";
}
}