summaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/IndVarSimplify.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Scalar/IndVarSimplify.cpp')
-rw-r--r--lib/Transforms/Scalar/IndVarSimplify.cpp129
1 files changed, 93 insertions, 36 deletions
diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index 10782963177c..74d6014d3e3d 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -25,27 +25,54 @@
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Scalar/IndVarSimplify.h"
+#include "llvm/ADT/APFloat.h"
+#include "llvm/ADT/APInt.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/None.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
-#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
+#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/CFG.h"
+#include "llvm/IR/Constant.h"
+#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/InstrTypes.h"
+#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
-#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Operator.h"
+#include "llvm/IR/PassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
+#include "llvm/IR/Use.h"
+#include "llvm/IR/User.h"
+#include "llvm/IR/Value.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
@@ -53,6 +80,10 @@
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SimplifyIndVar.h"
+#include <cassert>
+#include <cstdint>
+#include <utility>
+
using namespace llvm;
#define DEBUG_TYPE "indvars"
@@ -91,6 +122,7 @@ DisableLFTR("disable-lftr", cl::Hidden, cl::init(false),
cl::desc("Disable Linear Function Test Replace optimization"));
namespace {
+
struct RewritePhi;
class IndVarSimplify {
@@ -131,7 +163,8 @@ public:
bool run(Loop *L);
};
-}
+
+} // end anonymous namespace
/// Return true if the SCEV expansion generated by the rewriter can replace the
/// original value. SCEV guarantees that it produces the same value, but the way
@@ -251,7 +284,6 @@ static bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) {
/// is converted into
/// for(int i = 0; i < 10000; ++i)
/// bar((double)i);
-///
void IndVarSimplify::handleFloatingPointIV(Loop *L, PHINode *PN) {
unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
unsigned BackEdge = IncomingEdge^1;
@@ -305,7 +337,6 @@ void IndVarSimplify::handleFloatingPointIV(Loop *L, PHINode *PN) {
L->contains(TheBr->getSuccessor(1))))
return;
-
// If it isn't a comparison with an integer-as-fp (the exit value), we can't
// transform it.
ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1));
@@ -373,7 +404,6 @@ void IndVarSimplify::handleFloatingPointIV(Loop *L, PHINode *PN) {
// transform the IV.
if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue)
return;
-
} else {
// If we have a negative stride, we require the init to be greater than the
// exit value.
@@ -452,7 +482,6 @@ void IndVarSimplify::rewriteNonIntegerIVs(Loop *L) {
// First step. Check to see if there are any floating-point recurrences.
// If there are, change them into integer recurrences, permitting analysis by
// the SCEV routines.
- //
BasicBlock *Header = L->getHeader();
SmallVector<WeakTrackingVH, 8> PHIs;
@@ -472,18 +501,26 @@ void IndVarSimplify::rewriteNonIntegerIVs(Loop *L) {
}
namespace {
+
// Collect information about PHI nodes which can be transformed in
// rewriteLoopExitValues.
struct RewritePhi {
PHINode *PN;
- unsigned Ith; // Ith incoming value.
- Value *Val; // Exit value after expansion.
- bool HighCost; // High Cost when expansion.
+
+ // Ith incoming value.
+ unsigned Ith;
+
+ // Exit value after expansion.
+ Value *Val;
+
+ // High Cost when expansion.
+ bool HighCost;
RewritePhi(PHINode *P, unsigned I, Value *V, bool H)
: PN(P), Ith(I), Val(V), HighCost(H) {}
};
-}
+
+} // end anonymous namespace
Value *IndVarSimplify::expandSCEVIfNeeded(SCEVExpander &Rewriter, const SCEV *S,
Loop *L, Instruction *InsertPt,
@@ -747,7 +784,6 @@ void IndVarSimplify::rewriteFirstIterationLoopExitValues(Loop *L) {
/// aggressively.
bool IndVarSimplify::canLoopBeDeleted(
Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
-
BasicBlock *Preheader = L->getLoopPreheader();
// If there is no preheader, the loop will not be deleted.
if (!Preheader)
@@ -790,7 +826,9 @@ bool IndVarSimplify::canLoopBeDeleted(
}
for (auto *BB : L->blocks())
- if (any_of(*BB, [](Instruction &I) { return I.mayHaveSideEffects(); }))
+ if (llvm::any_of(*BB, [](Instruction &I) {
+ return I.mayHaveSideEffects();
+ }))
return false;
return true;
@@ -801,15 +839,21 @@ bool IndVarSimplify::canLoopBeDeleted(
//===----------------------------------------------------------------------===//
namespace {
+
// Collect information about induction variables that are used by sign/zero
// extend operations. This information is recorded by CollectExtend and provides
// the input to WidenIV.
struct WideIVInfo {
PHINode *NarrowIV = nullptr;
- Type *WidestNativeType = nullptr; // Widest integer type created [sz]ext
- bool IsSigned = false; // Was a sext user seen before a zext?
+
+ // Widest integer type created [sz]ext
+ Type *WidestNativeType = nullptr;
+
+ // Was a sext user seen before a zext?
+ bool IsSigned = false;
};
-}
+
+} // end anonymous namespace
/// Update information about the induction variable that is extended by this
/// sign or zero extend operation. This is used to determine the final width of
@@ -885,7 +929,6 @@ struct NarrowIVDefUse {
/// creating any new induction variables. To do this, it creates a new phi of
/// the wider type and redirects all users, either removing extends or inserting
/// truncs whenever we stop propagating the type.
-///
class WidenIV {
// Parameters
PHINode *OrigPhi;
@@ -902,22 +945,24 @@ class WidenIV {
bool HasGuards;
// Result
- PHINode *WidePhi;
- Instruction *WideInc;
- const SCEV *WideIncExpr;
+ PHINode *WidePhi = nullptr;
+ Instruction *WideInc = nullptr;
+ const SCEV *WideIncExpr = nullptr;
SmallVectorImpl<WeakTrackingVH> &DeadInsts;
SmallPtrSet<Instruction *,16> Widened;
SmallVector<NarrowIVDefUse, 8> NarrowIVUsers;
enum ExtendKind { ZeroExtended, SignExtended, Unknown };
+
// A map tracking the kind of extension used to widen each narrow IV
// and narrow IV user.
// Key: pointer to a narrow IV or IV user.
// Value: the kind of extension used to widen this Instruction.
DenseMap<AssertingVH<Instruction>, ExtendKind> ExtendKindMap;
- typedef std::pair<AssertingVH<Value>, AssertingVH<Instruction>> DefUserPair;
+ using DefUserPair = std::pair<AssertingVH<Value>, AssertingVH<Instruction>>;
+
// A map with control-dependent ranges for post increment IV uses. The key is
// a pair of IV def and a use of this def denoting the context. The value is
// a ConstantRange representing possible values of the def at the given
@@ -935,6 +980,7 @@ class WidenIV {
void calculatePostIncRanges(PHINode *OrigPhi);
void calculatePostIncRange(Instruction *NarrowDef, Instruction *NarrowUser);
+
void updatePostIncRangeInfo(Value *Def, Instruction *UseI, ConstantRange R) {
DefUserPair Key(Def, UseI);
auto It = PostIncRangeInfos.find(Key);
@@ -950,8 +996,7 @@ public:
bool HasGuards)
: OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),
L(LI->getLoopFor(OrigPhi->getParent())), SE(SEv), DT(DTree),
- HasGuards(HasGuards), WidePhi(nullptr), WideInc(nullptr),
- WideIncExpr(nullptr), DeadInsts(DI) {
+ HasGuards(HasGuards), DeadInsts(DI) {
assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV");
ExtendKindMap[OrigPhi] = WI.IsSigned ? SignExtended : ZeroExtended;
}
@@ -969,7 +1014,7 @@ protected:
ExtendKind getExtendKind(Instruction *I);
- typedef std::pair<const SCEVAddRecExpr *, ExtendKind> WidenedRecTy;
+ using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;
WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);
@@ -984,7 +1029,8 @@ protected:
void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef);
};
-} // anonymous namespace
+
+} // end anonymous namespace
/// Perform a quick domtree based check for loop invariance assuming that V is
/// used within the loop. LoopInfo::isLoopInvariant() seems gratuitous for this
@@ -1182,7 +1228,6 @@ const SCEV *WidenIV::getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
/// operands is an AddRec for this loop, return the AddRec and the kind of
/// extension used.
WidenIV::WidenedRecTy WidenIV::getExtendedOperandRecurrence(NarrowIVDefUse DU) {
-
// Handle the common case of add<nsw/nuw>
const unsigned OpCode = DU.NarrowUse->getOpcode();
// Only Add/Sub/Mul instructions supported yet.
@@ -1310,7 +1355,7 @@ bool WidenIV::widenLoopCompare(NarrowIVDefUse DU) {
Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
unsigned CastWidth = SE->getTypeSizeInBits(Op->getType());
unsigned IVWidth = SE->getTypeSizeInBits(WideType);
- assert (CastWidth <= IVWidth && "Unexpected width while widening compare.");
+ assert(CastWidth <= IVWidth && "Unexpected width while widening compare.");
// Widen the compare instruction.
IRBuilder<> Builder(
@@ -1461,7 +1506,6 @@ Instruction *WidenIV::widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) {
}
/// Add eligible users of NarrowDef to NarrowIVUsers.
-///
void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef);
bool NonNegativeDef =
@@ -1494,7 +1538,6 @@ void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
///
/// It would be simpler to delete uses as they are processed, but we must avoid
/// invalidating SCEV expressions.
-///
PHINode *WidenIV::createWideIV(SCEVExpander &Rewriter) {
// Is this phi an induction variable?
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi));
@@ -1581,6 +1624,15 @@ PHINode *WidenIV::createWideIV(SCEVExpander &Rewriter) {
if (DU.NarrowDef->use_empty())
DeadInsts.emplace_back(DU.NarrowDef);
}
+
+ // Attach any debug information to the new PHI. Since OrigPhi and WidePHI
+ // evaluate the same recurrence, we can just copy the debug info over.
+ SmallVector<DbgValueInst *, 1> DbgValues;
+ llvm::findDbgValues(DbgValues, OrigPhi);
+ auto *MDPhi = MetadataAsValue::get(WidePhi->getContext(),
+ ValueAsMetadata::get(WidePhi));
+ for (auto &DbgValue : DbgValues)
+ DbgValue->setOperand(0, MDPhi);
return WidePhi;
}
@@ -1696,12 +1748,12 @@ void WidenIV::calculatePostIncRanges(PHINode *OrigPhi) {
// Live IV Reduction - Minimize IVs live across the loop.
//===----------------------------------------------------------------------===//
-
//===----------------------------------------------------------------------===//
// Simplification of IV users based on SCEV evaluation.
//===----------------------------------------------------------------------===//
namespace {
+
class IndVarSimplifyVisitor : public IVVisitor {
ScalarEvolution *SE;
const TargetTransformInfo *TTI;
@@ -1721,14 +1773,14 @@ public:
// Implement the interface used by simplifyUsersOfIV.
void visitCast(CastInst *Cast) override { visitIVCast(Cast, WI, SE, TTI); }
};
-}
+
+} // end anonymous namespace
/// Iteratively perform simplification on a worklist of IV users. Each
/// successive simplification may push more users which may themselves be
/// candidates for simplification.
///
/// Sign/Zero extend elimination is interleaved with IV simplification.
-///
void IndVarSimplify::simplifyAndExtend(Loop *L,
SCEVExpander &Rewriter,
LoopInfo *LI) {
@@ -1759,7 +1811,8 @@ void IndVarSimplify::simplifyAndExtend(Loop *L,
// Information about sign/zero extensions of CurrIV.
IndVarSimplifyVisitor Visitor(CurrIV, SE, TTI, DT);
- Changed |= simplifyUsersOfIV(CurrIV, SE, DT, LI, DeadInsts, &Visitor);
+ Changed |=
+ simplifyUsersOfIV(CurrIV, SE, DT, LI, DeadInsts, Rewriter, &Visitor);
if (Visitor.WI.WidestNativeType) {
WideIVs.push_back(Visitor.WI);
@@ -2501,8 +2554,10 @@ PreservedAnalyses IndVarSimplifyPass::run(Loop &L, LoopAnalysisManager &AM,
}
namespace {
+
struct IndVarSimplifyLegacyPass : public LoopPass {
static char ID; // Pass identification, replacement for typeid
+
IndVarSimplifyLegacyPass() : LoopPass(ID) {
initializeIndVarSimplifyLegacyPassPass(*PassRegistry::getPassRegistry());
}
@@ -2529,9 +2584,11 @@ struct IndVarSimplifyLegacyPass : public LoopPass {
getLoopAnalysisUsage(AU);
}
};
-}
+
+} // end anonymous namespace
char IndVarSimplifyLegacyPass::ID = 0;
+
INITIALIZE_PASS_BEGIN(IndVarSimplifyLegacyPass, "indvars",
"Induction Variable Simplification", false, false)
INITIALIZE_PASS_DEPENDENCY(LoopPass)
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-06 16:26:32 +0000