//
// header:
// br %cond, label %if.then, label %if.else
-// / \
-// / \
-// / \
+// + +
+// + +
+// + +
// if.then: if.else:
// %lt = load %addr_l %le = load %addr_l
// <use %lt> <use %le>
// <...> <...>
// store %st, %addr_s store %se, %addr_s
// br label %if.end br label %if.end
-// \ /
-// \ /
-// \ /
+// + +
+// + +
+// + +
// if.end ("footer"):
// <...>
//
// header:
// %l = load %addr_l
// br %cond, label %if.then, label %if.else
-// / \
-// / \
-// / \
+// + +
+// + +
+// + +
// if.then: if.else:
// <use %l> <use %l>
// <...> <...>
// br label %if.end br label %if.end
-// \ /
-// \ /
-// \ /
+// + +
+// + +
+// + +
// if.end ("footer"):
// %s.sink = phi [%st, if.then], [%se, if.else]
// <...>
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CFG.h"
+#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
-#include "llvm/Target/TargetLibraryInfo.h"
+#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
#include <vector>
+
using namespace llvm;
#define DEBUG_TYPE "mldst-motion"
//===----------------------------------------------------------------------===//
// MergedLoadStoreMotion Pass
//===----------------------------------------------------------------------===//
-static cl::opt<bool>
-EnableMLSM("mlsm", cl::desc("Enable motion of merged load and store"),
- cl::init(true));
namespace {
class MergedLoadStoreMotion : public FunctionPass {
public:
static char ID; // Pass identification, replacement for typeid
- explicit MergedLoadStoreMotion(void)
+ MergedLoadStoreMotion()
: FunctionPass(ID), MD(nullptr), MagicCompileTimeControl(250) {
initializeMergedLoadStoreMotionPass(*PassRegistry::getPassRegistry());
}
private:
// This transformation requires dominator postdominator info
void getAnalysisUsage(AnalysisUsage &AU) const override {
- AU.addRequired<TargetLibraryInfo>();
- AU.addRequired<MemoryDependenceAnalysis>();
- AU.addRequired<AliasAnalysis>();
- AU.addPreserved<AliasAnalysis>();
+ AU.setPreservesCFG();
+ AU.addRequired<TargetLibraryInfoWrapperPass>();
+ AU.addRequired<AAResultsWrapperPass>();
+ AU.addPreserved<GlobalsAAWrapperPass>();
+ AU.addPreserved<MemoryDependenceAnalysis>();
}
// Helper routines
BasicBlock *getDiamondTail(BasicBlock *BB);
bool isDiamondHead(BasicBlock *BB);
// Routines for hoisting loads
- bool isLoadHoistBarrier(Instruction *Inst);
+ bool isLoadHoistBarrierInRange(const Instruction& Start,
+ const Instruction& End,
+ LoadInst* LI);
LoadInst *canHoistFromBlock(BasicBlock *BB, LoadInst *LI);
void hoistInstruction(BasicBlock *BB, Instruction *HoistCand,
Instruction *ElseInst);
// Routines for sinking stores
StoreInst *canSinkFromBlock(BasicBlock *BB, StoreInst *SI);
PHINode *getPHIOperand(BasicBlock *BB, StoreInst *S0, StoreInst *S1);
- bool isStoreSinkBarrier(Instruction *Inst);
+ bool isStoreSinkBarrierInRange(const Instruction &Start,
+ const Instruction &End, MemoryLocation Loc);
bool sinkStore(BasicBlock *BB, StoreInst *SinkCand, StoreInst *ElseInst);
bool mergeStores(BasicBlock *BB);
// The mergeLoad/Store algorithms could have Size0 * Size1 complexity,
};
char MergedLoadStoreMotion::ID = 0;
-}
+} // anonymous namespace
///
/// \brief createMergedLoadStoreMotionPass - The public interface to this file.
INITIALIZE_PASS_BEGIN(MergedLoadStoreMotion, "mldst-motion",
"MergedLoadStoreMotion", false, false)
INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis)
-INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
-INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
+INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
INITIALIZE_PASS_END(MergedLoadStoreMotion, "mldst-motion",
"MergedLoadStoreMotion", false, false)
/// being loaded or protect against the load from happening
/// it is considered a hoist barrier.
///
-bool MergedLoadStoreMotion::isLoadHoistBarrier(Instruction *Inst) {
- // FIXME: A call with no side effects should not be a barrier.
- // Aren't all such calls covered by mayHaveSideEffects() below?
- // Then this check can be removed.
- if (isa<CallInst>(Inst))
- return true;
- if (isa<TerminatorInst>(Inst))
- return true;
- // Note: mayHaveSideEffects covers all instructions that could
- // trigger a change to state. Eg. in-flight stores have to be executed
- // before ordered loads or fences, calls could invoke functions that store
- // data to memory etc.
- if (Inst->mayHaveSideEffects()) {
- return true;
- }
- DEBUG(dbgs() << "No Hoist Barrier\n");
- return false;
+bool MergedLoadStoreMotion::isLoadHoistBarrierInRange(const Instruction& Start,
+ const Instruction& End,
+ LoadInst* LI) {
+ MemoryLocation Loc = MemoryLocation::get(LI);
+ return AA->canInstructionRangeModRef(Start, End, Loc, MRI_Mod);
}
///
/// and it can be hoisted from \p BB, return that load.
/// Otherwise return Null.
///
-LoadInst *MergedLoadStoreMotion::canHoistFromBlock(BasicBlock *BB,
- LoadInst *LI) {
- LoadInst *I = nullptr;
- assert(isa<LoadInst>(LI));
- if (LI->isUsedOutsideOfBlock(LI->getParent()))
- return nullptr;
+LoadInst *MergedLoadStoreMotion::canHoistFromBlock(BasicBlock *BB1,
+ LoadInst *Load0) {
- for (BasicBlock::iterator BBI = BB->begin(), BBE = BB->end(); BBI != BBE;
+ for (BasicBlock::iterator BBI = BB1->begin(), BBE = BB1->end(); BBI != BBE;
++BBI) {
- Instruction *Inst = BBI;
+ Instruction *Inst = &*BBI;
// Only merge and hoist loads when their result in used only in BB
- if (isLoadHoistBarrier(Inst))
- break;
- if (!isa<LoadInst>(Inst))
- continue;
- if (Inst->isUsedOutsideOfBlock(Inst->getParent()))
+ if (!isa<LoadInst>(Inst) || Inst->isUsedOutsideOfBlock(BB1))
continue;
- AliasAnalysis::Location LocLI = AA->getLocation(LI);
- AliasAnalysis::Location LocInst = AA->getLocation((LoadInst *)Inst);
- if (AA->isMustAlias(LocLI, LocInst) && LI->getType() == Inst->getType()) {
- I = (LoadInst *)Inst;
- break;
+ LoadInst *Load1 = dyn_cast<LoadInst>(Inst);
+ BasicBlock *BB0 = Load0->getParent();
+
+ MemoryLocation Loc0 = MemoryLocation::get(Load0);
+ MemoryLocation Loc1 = MemoryLocation::get(Load1);
+ if (AA->isMustAlias(Loc0, Loc1) && Load0->isSameOperationAs(Load1) &&
+ !isLoadHoistBarrierInRange(BB1->front(), *Load1, Load1) &&
+ !isLoadHoistBarrierInRange(BB0->front(), *Load0, Load0)) {
+ return Load1;
}
}
- return I;
+ return nullptr;
}
///
// Intersect optional metadata.
HoistCand->intersectOptionalDataWith(ElseInst);
- HoistCand->dropUnknownMetadata();
+ HoistCand->dropUnknownNonDebugMetadata();
// Prepend point for instruction insert
Instruction *HoistPt = BB->getTerminator();
// Merged instruction
Instruction *HoistedInst = HoistCand->clone();
- // Notify AA of the new value.
- if (isa<LoadInst>(HoistCand))
- AA->copyValue(HoistCand, HoistedInst);
-
// Hoist instruction.
HoistedInst->insertBefore(HoistPt);
int NLoads = 0;
for (BasicBlock::iterator BBI = Succ0->begin(), BBE = Succ0->end();
BBI != BBE;) {
-
- Instruction *I = BBI;
+ Instruction *I = &*BBI;
++BBI;
- if (isLoadHoistBarrier(I))
- break;
// Only move non-simple (atomic, volatile) loads.
- if (!isa<LoadInst>(I))
- continue;
-
- LoadInst *L0 = (LoadInst *)I;
- if (!L0->isSimple())
+ LoadInst *L0 = dyn_cast<LoadInst>(I);
+ if (!L0 || !L0->isSimple() || L0->isUsedOutsideOfBlock(Succ0))
continue;
++NLoads;
}
///
-/// \brief True when instruction is sink barrier for a store
+/// \brief True when instruction is a sink barrier for a store
+/// located in Loc
///
-bool MergedLoadStoreMotion::isStoreSinkBarrier(Instruction *Inst) {
- if (isa<CallInst>(Inst))
- return true;
- if (isa<TerminatorInst>(Inst) && !isa<BranchInst>(Inst))
- return true;
- // Note: mayHaveSideEffects covers all instructions that could
- // trigger a change to state. Eg. in-flight stores have to be executed
- // before ordered loads or fences, calls could invoke functions that store
- // data to memory etc.
- if (!isa<StoreInst>(Inst) && Inst->mayHaveSideEffects()) {
- return true;
- }
- DEBUG(dbgs() << "No Sink Barrier\n");
- return false;
+/// Whenever an instruction could possibly read or modify the
+/// value being stored or protect against the store from
+/// happening it is considered a sink barrier.
+///
+bool MergedLoadStoreMotion::isStoreSinkBarrierInRange(const Instruction &Start,
+ const Instruction &End,
+ MemoryLocation Loc) {
+ return AA->canInstructionRangeModRef(Start, End, Loc, MRI_ModRef);
}
///
///
/// \return The store in \p when it is safe to sink. Otherwise return Null.
///
-StoreInst *MergedLoadStoreMotion::canSinkFromBlock(BasicBlock *BB,
- StoreInst *SI) {
- StoreInst *I = 0;
- DEBUG(dbgs() << "can Sink? : "; SI->dump(); dbgs() << "\n");
- for (BasicBlock::reverse_iterator RBI = BB->rbegin(), RBE = BB->rend();
+StoreInst *MergedLoadStoreMotion::canSinkFromBlock(BasicBlock *BB1,
+ StoreInst *Store0) {
+ DEBUG(dbgs() << "can Sink? : "; Store0->dump(); dbgs() << "\n");
+ BasicBlock *BB0 = Store0->getParent();
+ for (BasicBlock::reverse_iterator RBI = BB1->rbegin(), RBE = BB1->rend();
RBI != RBE; ++RBI) {
Instruction *Inst = &*RBI;
- // Only move loads if they are used in the block.
- if (isStoreSinkBarrier(Inst))
- break;
- if (isa<StoreInst>(Inst)) {
- AliasAnalysis::Location LocSI = AA->getLocation(SI);
- AliasAnalysis::Location LocInst = AA->getLocation((StoreInst *)Inst);
- if (AA->isMustAlias(LocSI, LocInst)) {
- I = (StoreInst *)Inst;
- break;
- }
+ if (!isa<StoreInst>(Inst))
+ continue;
+
+ StoreInst *Store1 = cast<StoreInst>(Inst);
+
+ MemoryLocation Loc0 = MemoryLocation::get(Store0);
+ MemoryLocation Loc1 = MemoryLocation::get(Store1);
+ if (AA->isMustAlias(Loc0, Loc1) && Store0->isSameOperationAs(Store1) &&
+ !isStoreSinkBarrierInRange(*(std::next(BasicBlock::iterator(Store1))),
+ BB1->back(), Loc1) &&
+ !isStoreSinkBarrierInRange(*(std::next(BasicBlock::iterator(Store0))),
+ BB0->back(), Loc0)) {
+ return Store1;
}
}
- return I;
+ return nullptr;
}
///
PHINode *MergedLoadStoreMotion::getPHIOperand(BasicBlock *BB, StoreInst *S0,
StoreInst *S1) {
// Create a phi if the values mismatch.
- PHINode *NewPN = 0;
+ PHINode *NewPN = nullptr;
Value *Opd1 = S0->getValueOperand();
Value *Opd2 = S1->getValueOperand();
if (Opd1 != Opd2) {
NewPN = PHINode::Create(Opd1->getType(), 2, Opd2->getName() + ".sink",
- BB->begin());
+ &BB->front());
NewPN->addIncoming(Opd1, S0->getParent());
NewPN->addIncoming(Opd2, S1->getParent());
- if (NewPN->getType()->getScalarType()->isPointerTy()) {
- // Notify AA of the new value.
- AA->copyValue(Opd1, NewPN);
- AA->copyValue(Opd2, NewPN);
- // AA needs to be informed when a PHI-use of the pointer value is added
- for (unsigned I = 0, E = NewPN->getNumIncomingValues(); I != E; ++I) {
- unsigned J = PHINode::getOperandNumForIncomingValue(I);
- AA->addEscapingUse(NewPN->getOperandUse(J));
- }
- if (MD)
- MD->invalidateCachedPointerInfo(NewPN);
- }
+ if (MD && NewPN->getType()->getScalarType()->isPointerTy())
+ MD->invalidateCachedPointerInfo(NewPN);
}
return NewPN;
}
BasicBlock::iterator InsertPt = BB->getFirstInsertionPt();
// Intersect optional metadata.
S0->intersectOptionalDataWith(S1);
- S0->dropUnknownMetadata();
+ S0->dropUnknownNonDebugMetadata();
// Create the new store to be inserted at the join point.
StoreInst *SNew = (StoreInst *)(S0->clone());
Instruction *ANew = A0->clone();
- AA->copyValue(S0, SNew);
- SNew->insertBefore(InsertPt);
+ SNew->insertBefore(&*InsertPt);
ANew->insertBefore(SNew);
assert(S0->getParent() == A0->getParent());
Instruction *I = &*RBI;
++RBI;
- if (isStoreSinkBarrier(I))
- break;
+
// Sink move non-simple (atomic, volatile) stores
if (!isa<StoreInst>(I))
continue;
}
return MergedStores;
}
+
///
/// \brief Run the transformation for each function
///
bool MergedLoadStoreMotion::runOnFunction(Function &F) {
- MD = &getAnalysis<MemoryDependenceAnalysis>();
- AA = &getAnalysis<AliasAnalysis>();
+ MD = getAnalysisIfAvailable<MemoryDependenceAnalysis>();
+ AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
bool Changed = false;
- if (!EnableMLSM)
- return false;
DEBUG(dbgs() << "Instruction Merger\n");
// Merge unconditional branches, allowing PRE to catch more
// optimization opportunities.
for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
- BasicBlock *BB = FI++;
+ BasicBlock *BB = &*FI++;
// Hoist equivalent loads and sink stores
// outside diamonds when possible
- // Run outside core GVN
if (isDiamondHead(BB)) {
Changed |= mergeLoads(BB);
Changed |= mergeStores(getDiamondTail(BB));
projects / oota-llvm.git / blobdiff