#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Instructions.h"
+#include "llvm/LLVMContext.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.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 <algorithm>
DisablePromotion("disable-licm-promotion", cl::Hidden,
cl::desc("Disable memory promotion in LICM pass"));
+// This feature is currently disabled by default because CodeGen is not yet
+// capable of rematerializing these constants in PIC mode, so it can lead to
+// degraded performance. Compile test/CodeGen/X86/remat-constant.ll with
+// -relocation-model=pic to see an example of this.
+static cl::opt<bool>
+EnableLICMConstantMotion("enable-licm-constant-variables", cl::Hidden,
+ cl::desc("Enable hoisting/sinking of constant "
+ "global variables"));
+
namespace {
struct VISIBILITY_HIDDEN 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);
char LICM::ID = 0;
static RegisterPass<LICM> X("licm", "Loop Invariant Code Motion");
-LoopPass *llvm::createLICMPass() { return new LICM(); }
+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
// Because subloops have already been incorporated into AST, we skip blocks in
// subloops.
//
- for (std::vector<BasicBlock*>::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
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 (EnableLICMConstantMotion &&
+ 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())
++NumSunk;
Changed = true;
+ LLVMContext &Context = I.getContext();
+
// The case where there is only a single exit node of this loop is common
// enough that we handle it as a special (more efficient) case. It is more
// efficient to handle because there are no PHI nodes that need to be placed.
// Instruction is not used, just delete it.
CurAST->deleteValue(&I);
if (!I.use_empty()) // If I has users in unreachable blocks, eliminate.
- I.replaceAllUsesWith(UndefValue::get(I.getType()));
+ I.replaceAllUsesWith(Context.getUndef(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<PHINode>(InsertPt)) ++InsertPt;
+ BasicBlock::iterator InsertPt = ExitBlocks[0]->getFirstNonPHI();
ExitBlocks[0]->getInstList().insert(InsertPt, &I);
}
} 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.
- I.replaceAllUsesWith(UndefValue::get(I.getType()));
+ I.replaceAllUsesWith(Context.getUndef(I.getType()));
I.eraseFromParent();
} else {
// Otherwise, if we have multiple exits, use the PromoteMem2Reg function to
// 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
ExitBlock->getInstList().insert(InsertPt, &I);
New = &I;
} else {
- New = I.clone();
+ New = I.clone(Context);
CurAST->copyValue(&I, New);
if (!I.getName().empty())
New->setName(I.getName()+".le");
if (AI) {
std::vector<AllocaInst*> Allocas;
Allocas.push_back(AI);
- PromoteMemToReg(Allocas, *DT, *DF, CurAST);
+ PromoteMemToReg(Allocas, *DT, *DF, Context, CurAST);
}
}
}
/// 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(errs() << "LICM hoisting to " << Preheader->getName() << ": " << I);
// Remove the instruction from its current basic block... but don't delete the
// instruction.
///
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
if (Inst.getParent() == CurLoop->getHeader())
return true;
- // It's always safe to load from a global or alloca.
- if (isa<LoadInst>(Inst))
- if (isa<AllocationInst>(Inst.getOperand(0)) ||
- isa<GlobalVariable>(Inst.getOperand(0)))
- return true;
-
// Get the exit blocks for the current loop.
SmallVector<BasicBlock*, 8> ExitBlocks;
CurLoop->getExitBlocks(ExitBlocks);
// Scan the basic blocks in the loop, replacing uses of our pointers with
// uses of the allocas in question.
//
- const std::vector<BasicBlock*> &LoopBBs = CurLoop->getBlocks();
- for (std::vector<BasicBlock*>::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<LoadInst>(II)) {
std::map<Value*, AllocaInst*>::iterator
I = ValueToAllocaMap.find(L->getOperand(0));
continue;
// 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.
+ BasicBlock::iterator BI = ExitBlocks[i]->getFirstNonPHI();
Instruction *InsertPos = BI;
unsigned PVN = 0;
for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) {
PromotedAllocas.reserve(PromotedValues.size());
for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i)
PromotedAllocas.push_back(PromotedValues[i].first);
- PromoteMemToReg(PromotedAllocas, *DT, *DF, CurAST);
+ PromoteMemToReg(PromotedAllocas, *DT, *DF, Preheader->getContext(), CurAST);
}
/// FindPromotableValuesInLoop - Check the current loop for stores to definite
std::map<Value*, AllocaInst*> &ValueToAllocaMap) {
Instruction *FnStart = CurLoop->getHeader()->getParent()->begin()->begin();
- 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();
I != E; ++I) {
// 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))
+ 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()->first;
+ 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
{
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;
}
CurAST->copyValue(V, AI);
for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I)
- ValueToAllocaMap.insert(std::make_pair(I->first, AI));
+ ValueToAllocaMap.insert(std::make_pair(I->getValue(), AI));
DOUT << "LICM: Promoting value: " << *V << "\n";
}