MaxInc("max-reroll-increment", cl::init(2048), cl::Hidden,
cl::desc("The maximum increment for loop rerolling"));
+static cl::opt<unsigned>
+NumToleratedFailedMatches("reroll-num-tolerated-failed-matches", cl::init(400),
+ cl::Hidden,
+ cl::desc("The maximum number of failures to tolerate"
+ " during fuzzy matching. (default: 400)"));
+
// This loop re-rolling transformation aims to transform loops like this:
//
// int foo(int a);
AliasAnalysis *AA;
LoopInfo *LI;
ScalarEvolution *SE;
- const DataLayout *DL;
TargetLibraryInfo *TLI;
DominatorTree *DT;
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)
+ : Parent(Parent), L(L), SE(SE), AA(AA), TLI(TLI), IV(IV) {}
/// Stage 1: Find all the DAG roots for the induction variable.
bool findRoots();
const SmallInstructionSet &Final,
DenseSet<Instruction *> &Users);
- UsesTy::iterator nextInstr(int Val, UsesTy &In, UsesTy::iterator I);
+ UsesTy::iterator nextInstr(int Val, UsesTy &In,
+ const SmallInstructionSet &Exclude,
+ UsesTy::iterator *StartI=nullptr);
bool isBaseInst(Instruction *I);
bool isRootInst(Instruction *I);
+ bool instrDependsOn(Instruction *I,
+ UsesTy::iterator Start,
+ UsesTy::iterator End);
LoopReroll *Parent;
ScalarEvolution *SE;
AliasAnalysis *AA;
TargetLibraryInfo *TLI;
- const DataLayout *DL;
// The loop induction variable.
Instruction *IV;
// (including the PHI), except for the last value (which is used by the PHI
// and also outside the loop).
Instruction *C = Instructions.front();
+ if (C->user_empty())
+ return;
do {
C = cast<Instruction>(*C->user_begin());
if (Roots.empty())
return false;
-
- assert(Roots.find(0) == Roots.end() && "Didn't expect a zero index!");
// If we found non-loop-inc, non-root users of Base, assume they are
// for the zeroth root index. This is because "add %a, 0" gets optimized
// away.
- if (BaseUsers.size())
+ if (BaseUsers.size()) {
+ if (Roots.find(0) != Roots.end()) {
+ DEBUG(dbgs() << "LRR: Multiple roots found for base - aborting!\n");
+ return false;
+ }
Roots[0] = Base;
+ }
// Calculate the number of users of the base, or lowest indexed, iteration.
unsigned NumBaseUses = BaseUsers.size();
}
+/// Get the next instruction in "In" that is a member of set Val.
+/// Start searching from StartI, and do not return anything in Exclude.
+/// If StartI is not given, start from In.begin().
LoopReroll::DAGRootTracker::UsesTy::iterator
LoopReroll::DAGRootTracker::nextInstr(int Val, UsesTy &In,
- UsesTy::iterator I) {
- while (I != In.end() && I->second.test(Val) == 0)
+ const SmallInstructionSet &Exclude,
+ UsesTy::iterator *StartI) {
+ UsesTy::iterator I = StartI ? *StartI : In.begin();
+ while (I != In.end() && (I->second.test(Val) == 0 ||
+ Exclude.count(I->first) != 0))
++I;
return I;
}
return false;
}
+/// Return true if instruction I depends on any instruction between
+/// Start and End.
+bool LoopReroll::DAGRootTracker::instrDependsOn(Instruction *I,
+ UsesTy::iterator Start,
+ UsesTy::iterator End) {
+ for (auto *U : I->users()) {
+ for (auto It = Start; It != End; ++It)
+ if (U == It->first)
+ 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
DenseMap<Value *, Value *> BaseMap;
// Compare iteration Iter to the base.
- auto BaseIt = nextInstr(0, Uses, Uses.begin());
- auto RootIt = nextInstr(Iter, Uses, Uses.begin());
+ SmallInstructionSet Visited;
+ auto BaseIt = nextInstr(0, Uses, Visited);
+ auto RootIt = nextInstr(Iter, Uses, Visited);
auto LastRootIt = Uses.begin();
while (BaseIt != Uses.end() && RootIt != Uses.end()) {
// Skip over the IV or root instructions; only match their users.
bool Continue = false;
if (isBaseInst(BaseInst)) {
- BaseIt = nextInstr(0, Uses, ++BaseIt);
+ Visited.insert(BaseInst);
+ BaseIt = nextInstr(0, Uses, Visited);
Continue = true;
}
if (isRootInst(RootInst)) {
LastRootIt = RootIt;
- RootIt = nextInstr(Iter, Uses, ++RootIt);
+ Visited.insert(RootInst);
+ RootIt = nextInstr(Iter, Uses, Visited);
Continue = true;
}
if (Continue) continue;
+ if (!BaseInst->isSameOperationAs(RootInst)) {
+ // Last chance saloon. We don't try and solve the full isomorphism
+ // problem, but try and at least catch the case where two instructions
+ // *of different types* are round the wrong way. We won't be able to
+ // efficiently tell, given two ADD instructions, which way around we
+ // should match them, but given an ADD and a SUB, we can at least infer
+ // which one is which.
+ //
+ // This should allow us to deal with a greater subset of the isomorphism
+ // problem. It does however change a linear algorithm into a quadratic
+ // one, so limit the number of probes we do.
+ auto TryIt = RootIt;
+ unsigned N = NumToleratedFailedMatches;
+ while (TryIt != Uses.end() &&
+ !BaseInst->isSameOperationAs(TryIt->first) &&
+ N--) {
+ ++TryIt;
+ TryIt = nextInstr(Iter, Uses, Visited, &TryIt);
+ }
+
+ if (TryIt == Uses.end() || TryIt == RootIt ||
+ instrDependsOn(TryIt->first, RootIt, TryIt)) {
+ DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst <<
+ " vs. " << *RootInst << "\n");
+ return false;
+ }
+
+ RootIt = TryIt;
+ RootInst = TryIt->first;
+ }
+
// All instructions between the last root and this root
- // 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.
- for (; LastRootIt != RootIt; ++LastRootIt) {
+ //
+ // 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
+ // do anything.
+ for (; LastRootIt < RootIt; ++LastRootIt) {
Instruction *I = LastRootIt->first;
if (LastRootIt->second.find_first() < (int)Iter)
continue;
// 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;
}
- if (!BaseInst->isSameOperationAs(RootInst)) {
- DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst <<
- " vs. " << *RootInst << "\n");
- return false;
- }
-
// Make sure that this instruction, which is in the use set of this
// root instruction, does not also belong to the base set or the set of
// some other root instruction.
// 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");
BaseMap.insert(std::make_pair(RootInst, BaseInst));
LastRootIt = RootIt;
- BaseIt = nextInstr(0, Uses, ++BaseIt);
- RootIt = nextInstr(Iter, Uses, ++RootIt);
+ Visited.insert(BaseInst);
+ Visited.insert(RootInst);
+ BaseIt = nextInstr(0, Uses, Visited);
+ RootIt = nextInstr(Iter, Uses, Visited);
}
assert (BaseIt == Uses.end() && RootIt == Uses.end() &&
"Mismatched set sizes!");
++J;
}
+ const DataLayout &DL = Header->getModule()->getDataLayout();
// We need to create a new induction variable for each different BaseInst.
for (auto &DRS : RootSets) {
SE->getConstant(RealIVSCEV->getType(), 1),
L, SCEV::FlagAnyWrap));
{ // Limit the lifetime of SCEVExpander.
- SCEVExpander Expander(*SE, "reroll");
+ SCEVExpander Expander(*SE, DL, "reroll");
Value *NewIV = Expander.expandCodeFor(H, IV->getType(), Header->begin());
for (auto &KV : Uses) {
}
}
- 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);
if (!DAGRoots.findRoots())
return false;
LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
SE = &getAnalysis<ScalarEvolution>();
TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
- DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
- DL = DLP ? &DLP->getDataLayout() : nullptr;
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
BasicBlock *Header = L->getHeader();
projects / oota-llvm.git / blobdiff