summaryrefslogtreecommitdiffstats
path: root/llvm/lib
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib')
-rw-r--r--llvm/lib/Transforms/Utils/LoopUtils.cpp168
-rw-r--r--llvm/lib/Transforms/Vectorize/LoopVectorize.cpp78
2 files changed, 214 insertions, 32 deletions
diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp
index ef82801a8f6..785e2d4917f 100644
--- a/llvm/lib/Transforms/Utils/LoopUtils.cpp
+++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp
@@ -34,6 +34,116 @@ bool RecurrenceDescriptor::areAllUsesIn(Instruction *I,
return true;
}
+bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurrenceKind Kind) {
+ switch (Kind) {
+ default:
+ break;
+ case RK_IntegerAdd:
+ case RK_IntegerMult:
+ case RK_IntegerOr:
+ case RK_IntegerAnd:
+ case RK_IntegerXor:
+ case RK_IntegerMinMax:
+ return true;
+ }
+ return false;
+}
+
+bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) {
+ return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
+}
+
+bool RecurrenceDescriptor::isArithmeticRecurrenceKind(RecurrenceKind Kind) {
+ switch (Kind) {
+ default:
+ break;
+ case RK_IntegerAdd:
+ case RK_IntegerMult:
+ case RK_FloatAdd:
+ case RK_FloatMult:
+ return true;
+ }
+ return false;
+}
+
+Instruction *
+RecurrenceDescriptor::lookThroughAnd(PHINode *Phi, Type *&RT,
+ SmallPtrSetImpl<Instruction *> &Visited,
+ SmallPtrSetImpl<Instruction *> &CI) {
+ if (!Phi->hasOneUse())
+ return Phi;
+
+ const APInt *M = nullptr;
+ Instruction *I, *J = cast<Instruction>(Phi->use_begin()->getUser());
+
+ // Matches either I & 2^x-1 or 2^x-1 & I. If we find a match, we update RT
+ // with a new integer type of the corresponding bit width.
+ if (match(J, m_CombineOr(m_And(m_Instruction(I), m_APInt(M)),
+ m_And(m_APInt(M), m_Instruction(I))))) {
+ int32_t Bits = (*M + 1).exactLogBase2();
+ if (Bits > 0) {
+ RT = IntegerType::get(Phi->getContext(), Bits);
+ Visited.insert(Phi);
+ CI.insert(J);
+ return J;
+ }
+ }
+ return Phi;
+}
+
+bool RecurrenceDescriptor::getSourceExtensionKind(
+ Instruction *Start, Instruction *Exit, Type *RT, bool &IsSigned,
+ SmallPtrSetImpl<Instruction *> &Visited,
+ SmallPtrSetImpl<Instruction *> &CI) {
+
+ SmallVector<Instruction *, 8> Worklist;
+ bool FoundOneOperand = false;
+ Worklist.push_back(Exit);
+
+ // Traverse the instructions in the reduction expression, beginning with the
+ // exit value.
+ while (!Worklist.empty()) {
+ Instruction *I = Worklist.pop_back_val();
+ for (Use &U : I->operands()) {
+
+ // Terminate the traversal if the operand is not an instruction, or we
+ // reach the starting value.
+ Instruction *J = dyn_cast<Instruction>(U.get());
+ if (!J || J == Start)
+ continue;
+
+ // Otherwise, investigate the operation if it is also in the expression.
+ if (Visited.count(J)) {
+ Worklist.push_back(J);
+ continue;
+ }
+
+ // If the operand is not in Visited, it is not a reduction operation, but
+ // it does feed into one. Make sure it is either a single-use sign- or
+ // zero-extend of the recurrence type.
+ CastInst *Cast = dyn_cast<CastInst>(J);
+ bool IsSExtInst = isa<SExtInst>(J);
+ if (!Cast || !Cast->hasOneUse() || Cast->getSrcTy() != RT ||
+ !(isa<ZExtInst>(J) || IsSExtInst))
+ return false;
+
+ // Furthermore, ensure that all such extends are of the same kind.
+ if (FoundOneOperand) {
+ if (IsSigned != IsSExtInst)
+ return false;
+ } else {
+ FoundOneOperand = true;
+ IsSigned = IsSExtInst;
+ }
+
+ // Lastly, add the sign- or zero-extend to CI so that we can avoid
+ // accounting for it in the cost model.
+ CI.insert(Cast);
+ }
+ }
+ return true;
+}
+
bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
Loop *TheLoop, bool HasFunNoNaNAttr,
RecurrenceDescriptor &RedDes) {
@@ -68,10 +178,32 @@ bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
unsigned NumCmpSelectPatternInst = 0;
InstDesc ReduxDesc(false, nullptr);
+ // Data used for determining if the recurrence has been type-promoted.
+ Type *RecurrenceType = Phi->getType();
+ SmallPtrSet<Instruction *, 4> CastInsts;
+ Instruction *Start = Phi;
+ bool IsSigned = false;
+
SmallPtrSet<Instruction *, 8> VisitedInsts;
SmallVector<Instruction *, 8> Worklist;
- Worklist.push_back(Phi);
- VisitedInsts.insert(Phi);
+
+ // Return early if the recurrence kind does not match the type of Phi. If the
+ // recurrence kind is arithmetic, we attempt to look through AND operations
+ // resulting from the type promotion performed by InstCombine. Vector
+ // operations are not limited to the legal integer widths, so we may be able
+ // to evaluate the reduction in the narrower width.
+ if (RecurrenceType->isFloatingPointTy()) {
+ if (!isFloatingPointRecurrenceKind(Kind))
+ return false;
+ } else {
+ if (!isIntegerRecurrenceKind(Kind))
+ return false;
+ if (isArithmeticRecurrenceKind(Kind))
+ Start = lookThroughAnd(Phi, RecurrenceType, VisitedInsts, CastInsts);
+ }
+
+ Worklist.push_back(Start);
+ VisitedInsts.insert(Start);
// A value in the reduction can be used:
// - By the reduction:
@@ -110,10 +242,14 @@ bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
!VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
return false;
- // Any reduction instruction must be of one of the allowed kinds.
- ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
- if (!ReduxDesc.isRecurrence())
- return false;
+ // Any reduction instruction must be of one of the allowed kinds. We ignore
+ // the starting value (the Phi or an AND instruction if the Phi has been
+ // type-promoted).
+ if (Cur != Start) {
+ ReduxDesc = isRecurrenceInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
+ if (!ReduxDesc.isRecurrence())
+ return false;
+ }
// A reduction operation must only have one use of the reduction value.
if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax &&
@@ -131,7 +267,7 @@ bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
++NumCmpSelectPatternInst;
// Check whether we found a reduction operator.
- FoundReduxOp |= !IsAPhi;
+ FoundReduxOp |= !IsAPhi && Cur != Start;
// Process users of current instruction. Push non-PHI nodes after PHI nodes
// onto the stack. This way we are going to have seen all inputs to PHI
@@ -193,6 +329,14 @@ bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
return false;
+ // If we think Phi may have been type-promoted, we also need to ensure that
+ // all source operands of the reduction are either SExtInsts or ZEstInsts. If
+ // so, we will be able to evaluate the reduction in the narrower bit width.
+ if (Start != Phi)
+ if (!getSourceExtensionKind(Start, ExitInstruction, RecurrenceType,
+ IsSigned, VisitedInsts, CastInsts))
+ return false;
+
// We found a reduction var if we have reached the original phi node and we
// only have a single instruction with out-of-loop users.
@@ -200,10 +344,9 @@ bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
// is saved as part of the RecurrenceDescriptor.
// Save the description of this reduction variable.
- RecurrenceDescriptor RD(RdxStart, ExitInstruction, Kind,
- ReduxDesc.getMinMaxKind(),
- ReduxDesc.getUnsafeAlgebraInst());
-
+ RecurrenceDescriptor RD(
+ RdxStart, ExitInstruction, Kind, ReduxDesc.getMinMaxKind(),
+ ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
RedDes = RD;
return true;
@@ -272,9 +415,6 @@ RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
default:
return InstDesc(false, I);
case Instruction::PHI:
- if (FP &&
- (Kind != RK_FloatMult && Kind != RK_FloatAdd && Kind != RK_FloatMinMax))
- return InstDesc(false, I);
return InstDesc(I, Prev.getMinMaxKind());
case Instruction::Sub:
case Instruction::Add:
diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
index c34d85ecafa..6fc1aaab6e1 100644
--- a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
+++ b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
@@ -1308,11 +1308,10 @@ public:
LoopVectorizationLegality *Legal,
const TargetTransformInfo &TTI,
const TargetLibraryInfo *TLI, AssumptionCache *AC,
- const Function *F, const LoopVectorizeHints *Hints)
+ const Function *F, const LoopVectorizeHints *Hints,
+ SmallPtrSetImpl<const Value *> &ValuesToIgnore)
: TheLoop(L), SE(SE), LI(LI), Legal(Legal), TTI(TTI), TLI(TLI),
- TheFunction(F), Hints(Hints) {
- CodeMetrics::collectEphemeralValues(L, AC, EphValues);
- }
+ TheFunction(F), Hints(Hints), ValuesToIgnore(ValuesToIgnore) {}
/// Information about vectorization costs
struct VectorizationFactor {
@@ -1381,9 +1380,6 @@ private:
emitAnalysisDiag(TheFunction, TheLoop, *Hints, Message);
}
- /// Values used only by @llvm.assume calls.
- SmallPtrSet<const Value *, 32> EphValues;
-
/// The loop that we evaluate.
Loop *TheLoop;
/// Scev analysis.
@@ -1399,6 +1395,8 @@ private:
const Function *TheFunction;
// Loop Vectorize Hint.
const LoopVectorizeHints *Hints;
+ // Values to ignore in the cost model.
+ const SmallPtrSetImpl<const Value *> &ValuesToIgnore;
};
/// \brief This holds vectorization requirements that must be verified late in
@@ -1643,8 +1641,19 @@ struct LoopVectorize : public FunctionPass {
return false;
}
+ // Collect values we want to ignore in the cost model. This includes
+ // type-promoting instructions we identified during reduction detection.
+ SmallPtrSet<const Value *, 32> ValuesToIgnore;
+ CodeMetrics::collectEphemeralValues(L, AC, ValuesToIgnore);
+ for (auto &Reduction : *LVL.getReductionVars()) {
+ RecurrenceDescriptor &RedDes = Reduction.second;
+ SmallPtrSetImpl<Instruction *> &Casts = RedDes.getCastInsts();
+ ValuesToIgnore.insert(Casts.begin(), Casts.end());
+ }
+
// Use the cost model.
- LoopVectorizationCostModel CM(L, SE, LI, &LVL, *TTI, TLI, AC, F, &Hints);
+ LoopVectorizationCostModel CM(L, SE, LI, &LVL, *TTI, TLI, AC, F, &Hints,
+ ValuesToIgnore);
// Check the function attributes to find out if this function should be
// optimized for size.
@@ -3234,12 +3243,11 @@ void InnerLoopVectorizer::vectorizeLoop() {
// instructions.
Builder.SetInsertPoint(LoopMiddleBlock->getFirstInsertionPt());
- VectorParts RdxParts;
+ VectorParts RdxParts, &RdxExitVal = getVectorValue(LoopExitInst);
setDebugLocFromInst(Builder, LoopExitInst);
for (unsigned part = 0; part < UF; ++part) {
// This PHINode contains the vectorized reduction variable, or
// the initial value vector, if we bypass the vector loop.
- VectorParts &RdxExitVal = getVectorValue(LoopExitInst);
PHINode *NewPhi = Builder.CreatePHI(VecTy, 2, "rdx.vec.exit.phi");
Value *StartVal = (part == 0) ? VectorStart : Identity;
for (unsigned I = 1, E = LoopBypassBlocks.size(); I != E; ++I)
@@ -3249,6 +3257,28 @@ void InnerLoopVectorizer::vectorizeLoop() {
RdxParts.push_back(NewPhi);
}
+ // If the vector reduction can be performed in a smaller type, we truncate
+ // then extend the loop exit value to enable InstCombine to evaluate the
+ // entire expression in the smaller type.
+ if (VF > 1 && RdxPhi->getType() != RdxDesc.getRecurrenceType()) {
+ Type *RdxVecTy = VectorType::get(RdxDesc.getRecurrenceType(), VF);
+ Builder.SetInsertPoint(LoopVectorBody.back()->getTerminator());
+ for (unsigned part = 0; part < UF; ++part) {
+ Value *Trunc = Builder.CreateTrunc(RdxExitVal[part], RdxVecTy);
+ Value *Extnd = RdxDesc.isSigned() ? Builder.CreateSExt(Trunc, VecTy)
+ : Builder.CreateZExt(Trunc, VecTy);
+ for (Value::user_iterator UI = RdxExitVal[part]->user_begin();
+ UI != RdxExitVal[part]->user_end();)
+ if (*UI != Trunc)
+ (*UI++)->replaceUsesOfWith(RdxExitVal[part], Extnd);
+ else
+ ++UI;
+ }
+ Builder.SetInsertPoint(LoopMiddleBlock->getFirstInsertionPt());
+ for (unsigned part = 0; part < UF; ++part)
+ RdxParts[part] = Builder.CreateTrunc(RdxParts[part], RdxVecTy);
+ }
+
// Reduce all of the unrolled parts into a single vector.
Value *ReducedPartRdx = RdxParts[0];
unsigned Op = RecurrenceDescriptor::getRecurrenceBinOp(RK);
@@ -3299,6 +3329,14 @@ void InnerLoopVectorizer::vectorizeLoop() {
// The result is in the first element of the vector.
ReducedPartRdx = Builder.CreateExtractElement(TmpVec,
Builder.getInt32(0));
+
+ // If the reduction can be performed in a smaller type, we need to extend
+ // the reduction to the wider type before we branch to the original loop.
+ if (RdxPhi->getType() != RdxDesc.getRecurrenceType())
+ ReducedPartRdx =
+ RdxDesc.isSigned()
+ ? Builder.CreateSExt(ReducedPartRdx, RdxPhi->getType())
+ : Builder.CreateZExt(ReducedPartRdx, RdxPhi->getType());
}
// Create a phi node that merges control-flow from the backedge-taken check
@@ -4652,18 +4690,22 @@ unsigned LoopVectorizationCostModel::getWidestType() {
for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
Type *T = it->getType();
- // Ignore ephemeral values.
- if (EphValues.count(it))
+ // Skip ignored values.
+ if (ValuesToIgnore.count(it))
continue;
// Only examine Loads, Stores and PHINodes.
if (!isa<LoadInst>(it) && !isa<StoreInst>(it) && !isa<PHINode>(it))
continue;
- // Examine PHI nodes that are reduction variables.
- if (PHINode *PN = dyn_cast<PHINode>(it))
+ // Examine PHI nodes that are reduction variables. Update the type to
+ // account for the recurrence type.
+ if (PHINode *PN = dyn_cast<PHINode>(it)) {
if (!Legal->getReductionVars()->count(PN))
continue;
+ RecurrenceDescriptor RdxDesc = (*Legal->getReductionVars())[PN];
+ T = RdxDesc.getRecurrenceType();
+ }
// Examine the stored values.
if (StoreInst *ST = dyn_cast<StoreInst>(it))
@@ -4924,8 +4966,8 @@ LoopVectorizationCostModel::calculateRegisterUsage() {
// Ignore instructions that are never used within the loop.
if (!Ends.count(I)) continue;
- // Ignore ephemeral values.
- if (EphValues.count(I))
+ // Skip ignored values.
+ if (ValuesToIgnore.count(I))
continue;
// Remove all of the instructions that end at this location.
@@ -4968,8 +5010,8 @@ unsigned LoopVectorizationCostModel::expectedCost(unsigned VF) {
if (isa<DbgInfoIntrinsic>(it))
continue;
- // Ignore ephemeral values.
- if (EphValues.count(it))
+ // Skip ignored values.
+ if (ValuesToIgnore.count(it))
continue;
unsigned C = getInstructionCost(it, VF);
OpenPOWER on IntegriCloud