aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Utils/LoopUtils.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Utils/LoopUtils.cpp')
-rw-r--r--lib/Transforms/Utils/LoopUtils.cpp276
1 files changed, 253 insertions, 23 deletions
diff --git a/lib/Transforms/Utils/LoopUtils.cpp b/lib/Transforms/Utils/LoopUtils.cpp
index 5cbde94a98ed..e03880526bfa 100644
--- a/lib/Transforms/Utils/LoopUtils.cpp
+++ b/lib/Transforms/Utils/LoopUtils.cpp
@@ -12,13 +12,13 @@
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Debug.h"
-#include "llvm/Analysis/ScalarEvolution.h"
-#include "llvm/Analysis/ScalarEvolutionExpressions.h"
-#include "llvm/IR/Module.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
using namespace llvm;
@@ -34,6 +34,124 @@ 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;
+ unsigned DstSize = RT->getPrimitiveSizeInBits();
+ 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 instruction.
+ CastInst *Cast = dyn_cast<CastInst>(J);
+ bool IsSExtInst = isa<SExtInst>(J);
+ if (!Cast || !Cast->hasOneUse() || !(isa<ZExtInst>(J) || IsSExtInst))
+ return false;
+
+ // Ensure the source type of the extend is no larger than the reduction
+ // type. It is not necessary for the types to be identical.
+ unsigned SrcSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
+ if (SrcSize > DstSize)
+ 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, if the source type of the extend matches the reduction type,
+ // add the extend to CI so that we can avoid accounting for it in the
+ // cost model.
+ if (SrcSize == DstSize)
+ CI.insert(Cast);
+ }
+ }
+ return true;
+}
+
bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
Loop *TheLoop, bool HasFunNoNaNAttr,
RecurrenceDescriptor &RedDes) {
@@ -68,10 +186,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 +250,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 +275,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 +337,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,9 +352,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());
-
+ RecurrenceDescriptor RD(
+ RdxStart, ExitInstruction, Kind, ReduxDesc.getMinMaxKind(),
+ ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
RedDes = RD;
return true;
@@ -263,14 +415,14 @@ RecurrenceDescriptor::InstDesc
RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
InstDesc &Prev, bool HasFunNoNaNAttr) {
bool FP = I->getType()->isFloatingPointTy();
- bool FastMath = FP && I->hasUnsafeAlgebra();
+ Instruction *UAI = Prev.getUnsafeAlgebraInst();
+ if (!UAI && FP && !I->hasUnsafeAlgebra())
+ UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
+
switch (I->getOpcode()) {
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:
@@ -284,10 +436,10 @@ RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
case Instruction::Xor:
return InstDesc(Kind == RK_IntegerXor, I);
case Instruction::FMul:
- return InstDesc(Kind == RK_FloatMult && FastMath, I);
+ return InstDesc(Kind == RK_FloatMult, I, UAI);
case Instruction::FSub:
case Instruction::FAdd:
- return InstDesc(Kind == RK_FloatAdd && FastMath, I);
+ return InstDesc(Kind == RK_FloatAdd, I, UAI);
case Instruction::FCmp:
case Instruction::ICmp:
case Instruction::Select:
@@ -442,6 +594,13 @@ Value *RecurrenceDescriptor::createMinMaxOp(IRBuilder<> &Builder,
break;
}
+ // We only match FP sequences with unsafe algebra, so we can unconditionally
+ // set it on any generated instructions.
+ IRBuilder<>::FastMathFlagGuard FMFG(Builder);
+ FastMathFlags FMF;
+ FMF.setUnsafeAlgebra();
+ Builder.SetFastMathFlags(FMF);
+
Value *Cmp;
if (RK == MRK_FloatMin || RK == MRK_FloatMax)
Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
@@ -452,8 +611,54 @@ Value *RecurrenceDescriptor::createMinMaxOp(IRBuilder<> &Builder,
return Select;
}
-bool llvm::isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
- ConstantInt *&StepValue) {
+InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K,
+ ConstantInt *Step)
+ : StartValue(Start), IK(K), StepValue(Step) {
+ assert(IK != IK_NoInduction && "Not an induction");
+ assert(StartValue && "StartValue is null");
+ assert(StepValue && !StepValue->isZero() && "StepValue is zero");
+ assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
+ "StartValue is not a pointer for pointer induction");
+ assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) &&
+ "StartValue is not an integer for integer induction");
+ assert(StepValue->getType()->isIntegerTy() &&
+ "StepValue is not an integer");
+}
+
+int InductionDescriptor::getConsecutiveDirection() const {
+ if (StepValue && (StepValue->isOne() || StepValue->isMinusOne()))
+ return StepValue->getSExtValue();
+ return 0;
+}
+
+Value *InductionDescriptor::transform(IRBuilder<> &B, Value *Index) const {
+ switch (IK) {
+ case IK_IntInduction:
+ assert(Index->getType() == StartValue->getType() &&
+ "Index type does not match StartValue type");
+ if (StepValue->isMinusOne())
+ return B.CreateSub(StartValue, Index);
+ if (!StepValue->isOne())
+ Index = B.CreateMul(Index, StepValue);
+ return B.CreateAdd(StartValue, Index);
+
+ case IK_PtrInduction:
+ assert(Index->getType() == StepValue->getType() &&
+ "Index type does not match StepValue type");
+ if (StepValue->isMinusOne())
+ Index = B.CreateNeg(Index);
+ else if (!StepValue->isOne())
+ Index = B.CreateMul(Index, StepValue);
+ return B.CreateGEP(nullptr, StartValue, Index);
+
+ case IK_NoInduction:
+ return nullptr;
+ }
+ llvm_unreachable("invalid enum");
+}
+
+bool InductionDescriptor::isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
+ InductionDescriptor &D) {
Type *PhiTy = Phi->getType();
// We only handle integer and pointer inductions variables.
if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
@@ -467,6 +672,10 @@ bool llvm::isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
return false;
}
+ assert(AR->getLoop()->getHeader() == Phi->getParent() &&
+ "PHI is an AddRec for a different loop?!");
+ Value *StartValue =
+ Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
const SCEV *Step = AR->getStepRecurrence(*SE);
// Calculate the pointer stride and check if it is consecutive.
const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
@@ -475,7 +684,7 @@ bool llvm::isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
ConstantInt *CV = C->getValue();
if (PhiTy->isIntegerTy()) {
- StepValue = CV;
+ D = InductionDescriptor(StartValue, IK_IntInduction, CV);
return true;
}
@@ -494,6 +703,27 @@ bool llvm::isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
int64_t CVSize = CV->getSExtValue();
if (CVSize % Size)
return false;
- StepValue = ConstantInt::getSigned(CV->getType(), CVSize / Size);
+ auto *StepValue = ConstantInt::getSigned(CV->getType(), CVSize / Size);
+
+ D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue);
return true;
}
+
+/// \brief Returns the instructions that use values defined in the loop.
+SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
+ SmallVector<Instruction *, 8> UsedOutside;
+
+ for (auto *Block : L->getBlocks())
+ // FIXME: I believe that this could use copy_if if the Inst reference could
+ // be adapted into a pointer.
+ for (auto &Inst : *Block) {
+ auto Users = Inst.users();
+ if (std::any_of(Users.begin(), Users.end(), [&](User *U) {
+ auto *Use = cast<Instruction>(U);
+ return !L->contains(Use->getParent());
+ }))
+ UsedOutside.push_back(&Inst);
+ }
+
+ return UsedOutside;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-11 07:22:14 +0000