STATISTIC(NumReduced , "Number of GEPs strength reduced");
STATISTIC(NumInserted, "Number of PHIs inserted");
STATISTIC(NumVariable, "Number of PHIs with variable strides");
-STATISTIC(NumEliminated , "Number of strides eliminated");
-STATISTIC(NumShadow , "Number of Shdow IVs optimized");
+STATISTIC(NumEliminated, "Number of strides eliminated");
+STATISTIC(NumShadow, "Number of Shadow IVs optimized");
namespace {
public:
static char ID; // Pass ID, replacement for typeid
explicit LoopStrengthReduce(const TargetLowering *tli = NULL) :
- LoopPass((intptr_t)&ID), TLI(tli) {
+ LoopPass(&ID), TLI(tli) {
}
bool runOnLoop(Loop *L, LPPassManager &LPM);
AU.addRequired<DominatorTree>();
AU.addRequired<TargetData>();
AU.addRequired<ScalarEvolution>();
+ AU.addPreserved<ScalarEvolution>();
}
/// getCastedVersionOf - Return the specified value casted to uintptr_t.
/// OptimizeShadowIV - If IV is used in a int-to-float cast
/// inside the loop then try to eliminate the cast opeation.
void OptimizeShadowIV(Loop *L);
+
+ /// OptimizeSMax - Rewrite the loop's terminating condition
+ /// if it uses an smax computation.
+ ICmpInst *OptimizeSMax(Loop *L, ICmpInst *Cond,
+ IVStrideUse* &CondUse);
+
bool FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse,
- const SCEVHandle *&CondStride);
+ const SCEVHandle *&CondStride);
bool RequiresTypeConversion(const Type *Ty, const Type *NewTy);
unsigned CheckForIVReuse(bool, bool, const SCEVHandle&,
IVExpr&, const Type*,
// Check stride constant and the comparision constant signs to detect
// overflow.
- if (ICmpInst::isSignedPredicate(Predicate) &&
- (CmpVal & SignBit) != (CmpSSInt & SignBit))
+ if ((CmpVal & SignBit) != (CmpSSInt & SignBit))
return Cond;
// Look for a suitable stride / iv as replacement.
return Cond;
}
+/// OptimizeSMax - Rewrite the loop's terminating condition if it uses
+/// an smax computation.
+///
+/// This is a narrow solution to a specific, but acute, problem. For loops
+/// like this:
+///
+/// i = 0;
+/// do {
+/// p[i] = 0.0;
+/// } while (++i < n);
+///
+/// where the comparison is signed, the trip count isn't just 'n', because
+/// 'n' could be negative. And unfortunately this can come up even for loops
+/// where the user didn't use a C do-while loop. For example, seemingly
+/// well-behaved top-test loops will commonly be lowered like this:
+//
+/// if (n > 0) {
+/// i = 0;
+/// do {
+/// p[i] = 0.0;
+/// } while (++i < n);
+/// }
+///
+/// and then it's possible for subsequent optimization to obscure the if
+/// test in such a way that indvars can't find it.
+///
+/// When indvars can't find the if test in loops like this, it creates a
+/// signed-max expression, which allows it to give the loop a canonical
+/// induction variable:
+///
+/// i = 0;
+/// smax = n < 1 ? 1 : n;
+/// do {
+/// p[i] = 0.0;
+/// } while (++i != smax);
+///
+/// Canonical induction variables are necessary because the loop passes
+/// are designed around them. The most obvious example of this is the
+/// LoopInfo analysis, which doesn't remember trip count values. It
+/// expects to be able to rediscover the trip count each time it is
+/// needed, and it does this using a simple analyis that only succeeds if
+/// the loop has a canonical induction variable.
+///
+/// However, when it comes time to generate code, the maximum operation
+/// can be quite costly, especially if it's inside of an outer loop.
+///
+/// This function solves this problem by detecting this type of loop and
+/// rewriting their conditions from ICMP_NE back to ICMP_SLT, and deleting
+/// the instructions for the maximum computation.
+///
+ICmpInst *LoopStrengthReduce::OptimizeSMax(Loop *L, ICmpInst *Cond,
+ IVStrideUse* &CondUse) {
+ // Check that the loop matches the pattern we're looking for.
+ if (Cond->getPredicate() != CmpInst::ICMP_EQ &&
+ Cond->getPredicate() != CmpInst::ICMP_NE)
+ return Cond;
+
+ SelectInst *Sel = dyn_cast<SelectInst>(Cond->getOperand(1));
+ if (!Sel || !Sel->hasOneUse()) return Cond;
+
+ SCEVHandle IterationCount = SE->getIterationCount(L);
+ if (isa<SCEVCouldNotCompute>(IterationCount))
+ return Cond;
+ SCEVHandle One = SE->getIntegerSCEV(1, IterationCount->getType());
+
+ // Adjust for an annoying getIterationCount quirk.
+ IterationCount = SE->getAddExpr(IterationCount, One);
+
+ // Check for a max calculation that matches the pattern.
+ SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(IterationCount);
+ if (!SMax || SMax != SE->getSCEV(Sel)) return Cond;
+
+ SCEVHandle SMaxLHS = SMax->getOperand(0);
+ SCEVHandle SMaxRHS = SMax->getOperand(1);
+ if (!SMaxLHS || SMaxLHS != One) return Cond;
+
+ // Check the relevant induction variable for conformance to
+ // the pattern.
+ SCEVHandle IV = SE->getSCEV(Cond->getOperand(0));
+ SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(IV);
+ if (!AR || !AR->isAffine() ||
+ AR->getStart() != One ||
+ AR->getStepRecurrence(*SE) != One)
+ return Cond;
+
+ // Check the right operand of the select, and remember it, as it will
+ // be used in the new comparison instruction.
+ Value *NewRHS = 0;
+ if (SE->getSCEV(Sel->getOperand(1)) == SMaxRHS)
+ NewRHS = Sel->getOperand(1);
+ else if (SE->getSCEV(Sel->getOperand(2)) == SMaxRHS)
+ NewRHS = Sel->getOperand(2);
+ if (!NewRHS) return Cond;
+
+ // Ok, everything looks ok to change the condition into an SLT or SGE and
+ // delete the max calculation.
+ ICmpInst *NewCond =
+ new ICmpInst(Cond->getPredicate() == CmpInst::ICMP_NE ?
+ CmpInst::ICMP_SLT :
+ CmpInst::ICMP_SGE,
+ Cond->getOperand(0), NewRHS, "scmp", Cond);
+
+ // Delete the max calculation instructions.
+ SE->deleteValueFromRecords(Cond);
+ Cond->replaceAllUsesWith(NewCond);
+ Cond->eraseFromParent();
+ Instruction *Cmp = cast<Instruction>(Sel->getOperand(0));
+ SE->deleteValueFromRecords(Sel);
+ Sel->eraseFromParent();
+ if (Cmp->use_empty()) {
+ SE->deleteValueFromRecords(Cmp);
+ Cmp->eraseFromParent();
+ }
+ CondUse->User = NewCond;
+ return NewCond;
+}
+
/// OptimizeShadowIV - If IV is used in a int-to-float cast
/// inside the loop then try to eliminate the cast opeation.
void LoopStrengthReduce::OptimizeShadowIV(Loop *L) {
+ SCEVHandle IterationCount = SE->getIterationCount(L);
+ if (isa<SCEVCouldNotCompute>(IterationCount))
+ return;
+
for (unsigned Stride = 0, e = StrideOrder.size(); Stride != e;
++Stride) {
std::map<SCEVHandle, IVUsersOfOneStride>::iterator SI =
IVUsesByStride.find(StrideOrder[Stride]);
assert(SI != IVUsesByStride.end() && "Stride doesn't exist!");
-
+ if (!isa<SCEVConstant>(SI->first))
+ continue;
+
for (std::vector<IVStrideUse>::iterator UI = SI->second.Users.begin(),
E = SI->second.Users.end(); UI != E; /* empty */) {
std::vector<IVStrideUse>::iterator CandidateUI = UI;
- UI++;
+ ++UI;
Instruction *ShadowUse = CandidateUI->User;
const Type *DestTy = NULL;
/* If shadow use is a int->float cast then insert a second IV
- to elminate this cast.
+ to eliminate this cast.
for (unsigned i = 0; i < n; ++i)
foo((double)i);
- is trnasformed into
+ is transformed into
double d = 0.0;
for (unsigned i = 0; i < n; ++i, ++d)
foo(d);
*/
- UIToFPInst *UCast = dyn_cast<UIToFPInst>(CandidateUI->User);
- if (UCast)
+ if (UIToFPInst *UCast = dyn_cast<UIToFPInst>(CandidateUI->User))
DestTy = UCast->getDestTy();
- else {
- SIToFPInst *SCast = dyn_cast<SIToFPInst>(CandidateUI->User);
- if (!SCast) continue;
+ else if (SIToFPInst *SCast = dyn_cast<SIToFPInst>(CandidateUI->User))
DestTy = SCast->getDestTy();
+ if (!DestTy) continue;
+
+ if (TLI) {
+ /* If target does not support DestTy natively then do not apply
+ this transformation. */
+ MVT DVT = TLI->getValueType(DestTy);
+ if (!TLI->isTypeLegal(DVT)) continue;
}
-
+
PHINode *PH = dyn_cast<PHINode>(ShadowUse->getOperand(0));
if (!PH) continue;
if (PH->getNumIncomingValues() != 2) continue;
+ const Type *SrcTy = PH->getType();
+ int Mantissa = DestTy->getFPMantissaWidth();
+ if (Mantissa == -1) continue;
+ if ((int)TD->getTypeSizeInBits(SrcTy) > Mantissa)
+ continue;
+
unsigned Entry, Latch;
if (PH->getIncomingBlock(0) == L->getLoopPreheader()) {
Entry = 0;
if (!C) continue;
- /* create new icnrement. '++d' in above example. */
+ /* Add new PHINode. */
+ PHINode *NewPH = PHINode::Create(DestTy, "IV.S.", PH);
+
+ /* create new increment. '++d' in above example. */
ConstantFP *CFP = ConstantFP::get(DestTy, C->getZExtValue());
BinaryOperator *NewIncr =
BinaryOperator::Create(Incr->getOpcode(),
- NewInit, CFP, "IV.S.next.", Incr);
+ NewPH, CFP, "IV.S.next.", Incr);
- /* Add new PHINode. */
- PHINode *NewPH = PHINode::Create(DestTy, "IV.S.", PH);
NewPH->addIncoming(NewInit, PH->getIncomingBlock(Entry));
NewPH->addIncoming(NewIncr, PH->getIncomingBlock(Latch));
/* Remove cast operation */
+ SE->deleteValueFromRecords(ShadowUse);
ShadowUse->replaceAllUsesWith(NewPH);
ShadowUse->eraseFromParent();
SI->second.Users.erase(CandidateUI);
if (!FindIVUserForCond(Cond, CondUse, CondStride))
return; // setcc doesn't use the IV.
+ // If the trip count is computed in terms of an smax (due to ScalarEvolution
+ // being unable to find a sufficient guard, for example), change the loop
+ // comparison to use SLT instead of NE.
+ Cond = OptimizeSMax(L, Cond, CondUse);
+
// If possible, change stride and operands of the compare instruction to
// eliminate one stride.
Cond = ChangeCompareStride(L, Cond, CondUse, CondStride);
}
DeleteTriviallyDeadInstructions(DeadInsts);
}
-
return Changed;
}
projects / oota-llvm.git / blobdiff