#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
-#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
bool runOnLoop(Loop *L, LPPassManager &LPM) override;
void getAnalysisUsage(AnalysisUsage &AU) const override {
- AU.addRequired<AliasAnalysis>();
+ AU.addRequired<AAResultsWrapperPass>();
AU.addRequired<LoopInfoWrapperPass>();
AU.addPreserved<LoopInfoWrapperPass>();
AU.addRequired<DominatorTreeWrapperPass>();
AU.addPreserved<DominatorTreeWrapperPass>();
- AU.addRequired<ScalarEvolution>();
+ AU.addRequired<ScalarEvolutionWrapperPass>();
AU.addRequired<TargetLibraryInfoWrapperPass>();
}
AliasAnalysis *AA;
LoopInfo *LI;
ScalarEvolution *SE;
- const DataLayout *DL;
TargetLibraryInfo *TLI;
DominatorTree *DT;
typedef SmallVector<Instruction *, 16> SmallInstructionVector;
typedef SmallSet<Instruction *, 16> SmallInstructionSet;
- // A chain of isomorphic instructions, indentified by a single-use PHI,
+ // Map between induction variable and its increment
+ DenseMap<Instruction *, int64_t> IVToIncMap;
+
+ // A chain of isomorphic instructions, identified by a single-use PHI
// representing a reduction. Only the last value may be used outside the
// loop.
struct SimpleLoopReduction {
// The functions below can be called after we've finished processing all
// instructions in the loop, and we know which reductions were selected.
- // Is the provided instruction the PHI of a reduction selected for
- // rerolling?
- bool isSelectedPHI(Instruction *J) {
- if (!isa<PHINode>(J))
- return false;
-
- for (DenseSet<int>::iterator RI = Reds.begin(), RIE = Reds.end();
- RI != RIE; ++RI) {
- int i = *RI;
- if (cast<Instruction>(J) == PossibleReds[i].getPHI())
- return true;
- }
-
- return false;
- }
-
bool validateSelected();
void replaceSelected();
// x[i*3+1] = y2
// x[i*3+2] = y3
//
- // Base instruction -> i*3
+ // Base instruction -> i*3
// +---+----+
// / | \
// ST[y1] +1 +2 <-- Roots
struct DAGRootTracker {
DAGRootTracker(LoopReroll *Parent, Loop *L, Instruction *IV,
ScalarEvolution *SE, AliasAnalysis *AA,
- TargetLibraryInfo *TLI, const DataLayout *DL)
- : Parent(Parent), L(L), SE(SE), AA(AA), TLI(TLI),
- DL(DL), IV(IV) {
- }
+ TargetLibraryInfo *TLI,
+ DenseMap<Instruction *, int64_t> &IncrMap)
+ : Parent(Parent), L(L), SE(SE), AA(AA), TLI(TLI), IV(IV),
+ IVToIncMap(IncrMap) {}
/// Stage 1: Find all the DAG roots for the induction variable.
bool findRoots();
ScalarEvolution *SE;
AliasAnalysis *AA;
TargetLibraryInfo *TLI;
- const DataLayout *DL;
// The loop induction variable.
Instruction *IV;
// Loop step amount.
- uint64_t Inc;
+ int64_t Inc;
// Loop reroll count; if Inc == 1, this records the scaling applied
// to the indvar: a[i*2+0] = ...; a[i*2+1] = ... ;
// If Inc is not 1, Scale = Inc.
// they are used in (or specially, IL_All for instructions
// used in the loop increment mechanism).
UsesTy Uses;
+ // Map between induction variable and its increment
+ DenseMap<Instruction *, int64_t> &IVToIncMap;
};
void collectPossibleIVs(Loop *L, SmallInstructionVector &PossibleIVs);
char LoopReroll::ID = 0;
INITIALIZE_PASS_BEGIN(LoopReroll, "loop-reroll", "Reroll loops", false, false)
-INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_END(LoopReroll, "loop-reroll", "Reroll loops", false, false)
continue;
if (const SCEVAddRecExpr *PHISCEV =
- dyn_cast<SCEVAddRecExpr>(SE->getSCEV(I))) {
+ dyn_cast<SCEVAddRecExpr>(SE->getSCEV(&*I))) {
if (PHISCEV->getLoop() != L)
continue;
if (!PHISCEV->isAffine())
continue;
if (const SCEVConstant *IncSCEV =
dyn_cast<SCEVConstant>(PHISCEV->getStepRecurrence(*SE))) {
- if (!IncSCEV->getValue()->getValue().isStrictlyPositive())
+ const APInt &AInt = IncSCEV->getValue()->getValue().abs();
+ if (IncSCEV->getValue()->isZero() || AInt.uge(MaxInc))
continue;
- if (IncSCEV->getValue()->uge(MaxInc))
- continue;
-
- DEBUG(dbgs() << "LRR: Possible IV: " << *I << " = " <<
- *PHISCEV << "\n");
- PossibleIVs.push_back(I);
+ IVToIncMap[&*I] = IncSCEV->getValue()->getSExtValue();
+ DEBUG(dbgs() << "LRR: Possible IV: " << *I << " = " << *PHISCEV
+ << "\n");
+ PossibleIVs.push_back(&*I);
}
}
}
if (!I->getType()->isSingleValueType())
continue;
- SimpleLoopReduction SLR(I, L);
+ SimpleLoopReduction SLR(&*I, L);
if (!SLR.valid())
continue;
}
}
- int64_t V = CI->getValue().getSExtValue();
+ int64_t V = std::abs(CI->getValue().getSExtValue());
if (Roots.find(V) != Roots.end())
// No duplicates, please.
return false;
- // FIXME: Add support for negative values.
- if (V < 0) {
- DEBUG(dbgs() << "LRR: Aborting due to negative value: " << V << "\n");
- return false;
- }
-
Roots[V] = cast<Instruction>(I);
}
unsigned NumBaseUses = BaseUsers.size();
if (NumBaseUses == 0)
NumBaseUses = Roots.begin()->second->getNumUses();
-
+
// Check that every node has the same number of users.
for (auto &KV : Roots) {
if (KV.first == 0)
}
}
- return true;
+ return true;
}
bool LoopReroll::DAGRootTracker::
if (!collectPossibleRoots(IVU, V))
return false;
- // If we didn't get a root for index zero, then IVU must be
+ // If we didn't get a root for index zero, then IVU must be
// subsumed.
if (V.find(0) == V.end())
SubsumedInsts.insert(IVU);
}
bool LoopReroll::DAGRootTracker::findRoots() {
-
- const SCEVAddRecExpr *RealIVSCEV = cast<SCEVAddRecExpr>(SE->getSCEV(IV));
- Inc = cast<SCEVConstant>(RealIVSCEV->getOperand(1))->
- getValue()->getZExtValue();
+ Inc = IVToIncMap[IV];
assert(RootSets.empty() && "Unclean state!");
- if (Inc == 1) {
+ if (std::abs(Inc) == 1) {
for (auto *IVU : IV->users()) {
if (isLoopIncrement(IVU, IV))
LoopIncs.push_back(cast<Instruction>(IVU));
return false;
}
+static bool isIgnorableInst(const Instruction *I) {
+ if (isa<DbgInfoIntrinsic>(I))
+ return true;
+ const IntrinsicInst* II = dyn_cast<IntrinsicInst>(I);
+ if (!II)
+ return false;
+ switch (II->getIntrinsicID()) {
+ default:
+ return false;
+ case llvm::Intrinsic::annotation:
+ case Intrinsic::ptr_annotation:
+ case Intrinsic::var_annotation:
+ // TODO: the following intrinsics may also be whitelisted:
+ // lifetime_start, lifetime_end, invariant_start, invariant_end
+ return true;
+ }
+ return false;
+}
+
bool LoopReroll::DAGRootTracker::validate(ReductionTracker &Reductions) {
// We now need to check for equivalence of the use graph of each root with
// that of the primary induction variable (excluding the roots). Our goal
// Make sure all instructions in the loop are in one and only one
// set.
for (auto &KV : Uses) {
- if (KV.second.count() != 1) {
+ if (KV.second.count() != 1 && !isIgnorableInst(KV.first)) {
DEBUG(dbgs() << "LRR: Aborting - instruction is not used in 1 iteration: "
<< *KV.first << " (#uses=" << KV.second.count() << ")\n");
return false;
" vs. " << *RootInst << "\n");
return false;
}
-
+
RootIt = TryIt;
RootInst = TryIt->first;
}
// All instructions between the last root and this root
- // may belong to some other iteration. If they belong to a
+ // may belong to some other iteration. If they belong to a
// future iteration, then they're dangerous to alias with.
- //
+ //
// Note that because we allow a limited amount of flexibility in the order
// that we visit nodes, LastRootIt might be *before* RootIt, in which
// case we've already checked this set of instructions so we shouldn't
// needed because otherwise isSafeToSpeculativelyExecute returns
// false on PHI nodes.
if (!isa<PHINode>(I) && !isSimpleLoadStore(I) &&
- !isSafeToSpeculativelyExecute(I, DL))
+ !isSafeToSpeculativelyExecute(I))
// Intervening instructions cause side effects.
FutureSideEffects = true;
}
// side effects, and this instruction might also, then we can't reorder
// them, and this matching fails. As an exception, we allow the alias
// set tracker to handle regular (simple) load/store dependencies.
- if (FutureSideEffects &&
- ((!isSimpleLoadStore(BaseInst) &&
- !isSafeToSpeculativelyExecute(BaseInst, DL)) ||
- (!isSimpleLoadStore(RootInst) &&
- !isSafeToSpeculativelyExecute(RootInst, DL)))) {
+ if (FutureSideEffects && ((!isSimpleLoadStore(BaseInst) &&
+ !isSafeToSpeculativelyExecute(BaseInst)) ||
+ (!isSimpleLoadStore(RootInst) &&
+ !isSafeToSpeculativelyExecute(RootInst)))) {
DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst <<
" vs. " << *RootInst <<
" (side effects prevent reordering)\n");
++J;
}
+ bool Negative = IVToIncMap[IV] < 0;
+ const DataLayout &DL = Header->getModule()->getDataLayout();
// We need to create a new induction variable for each different BaseInst.
for (auto &DRS : RootSets) {
const SCEVAddRecExpr *RealIVSCEV =
cast<SCEVAddRecExpr>(SE->getSCEV(DRS.BaseInst));
const SCEV *Start = RealIVSCEV->getStart();
- const SCEVAddRecExpr *H = cast<SCEVAddRecExpr>
- (SE->getAddRecExpr(Start,
- SE->getConstant(RealIVSCEV->getType(), 1),
- L, SCEV::FlagAnyWrap));
+ const SCEVAddRecExpr *H = cast<SCEVAddRecExpr>(SE->getAddRecExpr(
+ Start, SE->getConstant(RealIVSCEV->getType(), Negative ? -1 : 1), L,
+ SCEV::FlagAnyWrap));
{ // Limit the lifetime of SCEVExpander.
- SCEVExpander Expander(*SE, "reroll");
- Value *NewIV = Expander.expandCodeFor(H, IV->getType(), Header->begin());
+ SCEVExpander Expander(*SE, DL, "reroll");
+ Value *NewIV = Expander.expandCodeFor(H, IV->getType(), &Header->front());
for (auto &KV : Uses) {
if (KV.second.find_first() == 0)
const SCEV *ICSCEV = RealIVSCEV->evaluateAtIteration(IterCount, *SE);
// Iteration count SCEV minus 1
- const SCEV *ICMinus1SCEV =
- SE->getMinusSCEV(ICSCEV, SE->getConstant(ICSCEV->getType(), 1));
+ const SCEV *ICMinus1SCEV = SE->getMinusSCEV(
+ ICSCEV, SE->getConstant(ICSCEV->getType(), Negative ? -1 : 1));
Value *ICMinus1; // Iteration count minus 1
if (isa<SCEVConstant>(ICMinus1SCEV)) {
}
}
- SimplifyInstructionsInBlock(Header, DL, TLI);
+ SimplifyInstructionsInBlock(Header, TLI);
DeleteDeadPHIs(Header, TLI);
}
bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header,
const SCEV *IterCount,
ReductionTracker &Reductions) {
- DAGRootTracker DAGRoots(this, L, IV, SE, AA, TLI, DL);
+ DAGRootTracker DAGRoots(this, L, IV, SE, AA, TLI, IVToIncMap);
if (!DAGRoots.findRoots())
return false;
DEBUG(dbgs() << "LRR: Found all root induction increments for: " <<
*IV << "\n");
-
+
if (!DAGRoots.validate(Reductions))
return false;
if (!Reductions.validateSelected())
if (skipOptnoneFunction(L))
return false;
- AA = &getAnalysis<AliasAnalysis>();
+ AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
- SE = &getAnalysis<ScalarEvolution>();
+ SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
- DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
- DL = DLP ? &DLP->getDataLayout() : nullptr;
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
BasicBlock *Header = L->getHeader();
return Changed;
const SCEV *LIBETC = SE->getBackedgeTakenCount(L);
- const SCEV *IterCount =
- SE->getAddExpr(LIBETC, SE->getConstant(LIBETC->getType(), 1));
+ const SCEV *IterCount = SE->getAddExpr(LIBETC, SE->getOne(LIBETC->getType()));
DEBUG(dbgs() << "LRR: iteration count = " << *IterCount << "\n");
// First, we need to find the induction variable with respect to which we can
// reroll (there may be several possible options).
SmallInstructionVector PossibleIVs;
+ IVToIncMap.clear();
collectPossibleIVs(L, PossibleIVs);
if (PossibleIVs.empty()) {
projects / oota-llvm.git / blobdiff