83#define DEBUG_TYPE "loop-flatten"
85STATISTIC(NumFlattened,
"Number of loops flattened");
89 cl::desc(
"Limit on the cost of instructions that can be repeated due to "
95 cl::desc(
"Assume that the product of the two iteration "
96 "trip counts will never overflow"));
100 cl::desc(
"Widen the loop induction variables, if possible, so "
101 "overflow checks won't reject flattening"));
113 Loop *OuterLoop =
nullptr;
114 Loop *InnerLoop =
nullptr;
116 PHINode *InnerInductionPHI =
nullptr;
117 PHINode *OuterInductionPHI =
nullptr;
121 Value *InnerTripCount =
nullptr;
122 Value *OuterTripCount =
nullptr;
139 bool Widened =
false;
142 PHINode *NarrowInnerInductionPHI =
nullptr;
143 PHINode *NarrowOuterInductionPHI =
nullptr;
147 FlattenInfo(
Loop *OL,
Loop *IL) : OuterLoop(OL), InnerLoop(IL){};
149 bool isNarrowInductionPhi(
PHINode *Phi) {
153 return NarrowInnerInductionPHI == Phi || NarrowOuterInductionPHI == Phi;
155 bool isInnerLoopIncrement(
User *U) {
156 return InnerIncrement == U;
158 bool isOuterLoopIncrement(
User *U) {
159 return OuterIncrement == U;
161 bool isInnerLoopTest(
User *U) {
166 for (
User *U : OuterInductionPHI->
users()) {
167 if (isOuterLoopIncrement(U))
170 auto IsValidOuterPHIUses = [&] (
User *U) ->
bool {
172 if (!ValidOuterPHIUses.
count(U)) {
173 LLVM_DEBUG(
dbgs() <<
"Did not match expected pattern, bailing\n");
180 if (
auto *V = dyn_cast<TruncInst>(U)) {
181 for (
auto *K : V->users()) {
182 if (!IsValidOuterPHIUses(K))
188 if (!IsValidOuterPHIUses(U))
194 bool matchLinearIVUser(
User *U,
Value *InnerTripCount,
197 Value *MatchedMul =
nullptr;
198 Value *MatchedItCount =
nullptr;
222 return !isInstructionTriviallyDead(cast<Instruction>(U));
230 if (Widened && IsAdd &&
231 (isa<SExtInst>(MatchedItCount) || isa<ZExtInst>(MatchedItCount))) {
233 "Unexpected type mismatch in types after widening");
234 MatchedItCount = isa<SExtInst>(MatchedItCount)
235 ? dyn_cast<SExtInst>(MatchedItCount)->getOperand(0)
236 : dyn_cast<ZExtInst>(MatchedItCount)->getOperand(0);
240 InnerTripCount->
dump());
242 if ((IsAdd || IsAddTrunc) && MatchedItCount == InnerTripCount) {
244 ValidOuterPHIUses.
insert(MatchedMul);
249 LLVM_DEBUG(
dbgs() <<
"Did not match expected pattern, bailing\n");
254 Value *SExtInnerTripCount = InnerTripCount;
256 (isa<SExtInst>(InnerTripCount) || isa<ZExtInst>(InnerTripCount)))
257 SExtInnerTripCount = cast<Instruction>(InnerTripCount)->getOperand(0);
259 for (
User *U : InnerInductionPHI->
users()) {
261 if (isInnerLoopIncrement(U)) {
262 LLVM_DEBUG(
dbgs() <<
"Use is inner loop increment, continuing\n");
268 if (isa<TruncInst>(U)) {
278 if (isInnerLoopTest(U)) {
283 if (!matchLinearIVUser(U, SExtInnerTripCount, ValidOuterPHIUses)) {
298 IterationInstructions.
insert(Increment);
316 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
317 LLVM_DEBUG(
dbgs() <<
"Backedge-taken count is not predictable\n");
325 const SCEV *SCEVTripCount =
329 if (SCEVRHS == SCEVTripCount)
333 const SCEV *BackedgeTCExt =
nullptr;
335 const SCEV *SCEVTripCountExt;
340 if (SCEVRHS != BackedgeTCExt && SCEVRHS != SCEVTripCountExt) {
347 if (SCEVRHS == BackedgeTCExt || SCEVRHS == BackedgeTakenCount) {
352 IterationInstructions);
363 auto *TripCountInst = dyn_cast<Instruction>(
RHS);
364 if (!TripCountInst) {
368 if ((!isa<ZExtInst>(TripCountInst) && !isa<SExtInst>(TripCountInst)) ||
369 SE->
getSCEV(TripCountInst->getOperand(0)) != SCEVTripCount) {
370 LLVM_DEBUG(
dbgs() <<
"Could not find valid extended trip count\n");
425 if (!Compare || !IsValidPredicate(Compare->getUnsignedPredicate()) ||
426 Compare->hasNUsesOrMore(2)) {
431 IterationInstructions.
insert(BackBranch);
433 IterationInstructions.
insert(Compare);
442 if ((Compare->getOperand(0) != Increment || !Increment->hasNUses(2)) &&
443 !Increment->hasNUses(1)) {
452 Value *
RHS = Compare->getOperand(1);
455 Increment, BackBranch, SE, IsWidened);
474 SafeOuterPHIs.
insert(FI.OuterInductionPHI);
478 for (
PHINode &InnerPHI : FI.InnerLoop->getHeader()->phis()) {
481 if (&InnerPHI == FI.InnerInductionPHI)
483 if (FI.isNarrowInductionPhi(&InnerPHI))
488 assert(InnerPHI.getNumIncomingValues() == 2);
489 Value *PreHeaderValue =
490 InnerPHI.getIncomingValueForBlock(FI.InnerLoop->getLoopPreheader());
492 InnerPHI.getIncomingValueForBlock(FI.InnerLoop->getLoopLatch());
497 PHINode *OuterPHI = dyn_cast<PHINode>(PreHeaderValue);
498 if (!OuterPHI || OuterPHI->
getParent() != FI.OuterLoop->getHeader()) {
507 PHINode *LCSSAPHI = dyn_cast<PHINode>(
518 dbgs() <<
"LCSSA PHI incoming value does not match latch value\n");
525 SafeOuterPHIs.
insert(OuterPHI);
526 FI.InnerPHIsToTransform.insert(&InnerPHI);
529 for (
PHINode &OuterPHI : FI.OuterLoop->getHeader()->phis()) {
530 if (FI.isNarrowInductionPhi(&OuterPHI))
532 if (!SafeOuterPHIs.
count(&OuterPHI)) {
533 LLVM_DEBUG(
dbgs() <<
"found unsafe PHI in outer loop: "; OuterPHI.dump());
552 for (
auto *
B : FI.OuterLoop->getBlocks()) {
553 if (FI.InnerLoop->contains(
B))
557 if (!isa<PHINode>(&
I) && !
I.isTerminator() &&
559 LLVM_DEBUG(
dbgs() <<
"Cannot flatten because instruction may have "
568 if (IterationInstructions.
count(&
I))
584 RepeatedInstrCost +=
Cost;
588 LLVM_DEBUG(
dbgs() <<
"Cost of instructions that will be repeated: "
589 << RepeatedInstrCost <<
"\n");
593 LLVM_DEBUG(
dbgs() <<
"checkOuterLoopInsts: not profitable, bailing.\n");
614 if (!FI.checkInnerInductionPhiUsers(ValidOuterPHIUses))
619 if (!FI.checkOuterInductionPhiUsers(ValidOuterPHIUses))
623 dbgs() <<
"Found " << FI.LinearIVUses.size()
624 <<
" value(s) that can be replaced:\n";
625 for (
Value *V : FI.LinearIVUses) {
636 Function *
F = FI.OuterLoop->getHeader()->getParent();
641 return OverflowResult::NeverOverflows;
646 FI.InnerTripCount, FI.OuterTripCount,
DL, AC,
647 FI.OuterLoop->getLoopPreheader()->getTerminator(), DT);
648 if (OR != OverflowResult::MayOverflow)
651 for (
Value *V : FI.LinearIVUses) {
653 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(U)) {
655 auto *GEPUserInst = cast<Instruction>(GEPUser);
656 if (!isa<LoadInst>(GEPUserInst) &&
657 !(isa<StoreInst>(GEPUserInst) &&
658 GEP == GEPUserInst->getOperand(1)))
667 if (
GEP->isInBounds() &&
669 DL.getPointerTypeSizeInBits(
GEP->getType())) {
671 dbgs() <<
"use of linear IV would be UB if overflow occurred: ";
673 return OverflowResult::NeverOverflows;
680 return OverflowResult::MayOverflow;
688 FI.InnerInductionPHI, FI.InnerTripCount,
689 FI.InnerIncrement, FI.InnerBranch, SE, FI.Widened))
692 FI.OuterInductionPHI, FI.OuterTripCount,
693 FI.OuterIncrement, FI.OuterBranch, SE, FI.Widened))
698 if (!FI.OuterLoop->isLoopInvariant(FI.InnerTripCount)) {
702 if (!FI.OuterLoop->isLoopInvariant(FI.OuterTripCount)) {
711 if (FI.InnerInductionPHI->getType() != FI.OuterInductionPHI->getType())
733 Function *
F = FI.OuterLoop->getHeader()->getParent();
734 LLVM_DEBUG(
dbgs() <<
"Checks all passed, doing the transformation\n");
738 FI.InnerLoop->getHeader());
740 Remark <<
"Flattened into outer loop";
744 Value *NewTripCount = BinaryOperator::CreateMul(
745 FI.InnerTripCount, FI.OuterTripCount,
"flatten.tripcount",
746 FI.OuterLoop->getLoopPreheader()->getTerminator());
748 NewTripCount->
dump());
752 FI.InnerInductionPHI->removeIncomingValue(FI.InnerLoop->getLoopLatch());
757 PHI->removeIncomingValue(FI.InnerLoop->getLoopLatch());
761 cast<User>(FI.OuterBranch->getCondition())->setOperand(1, NewTripCount);
764 BasicBlock *InnerExitBlock = FI.InnerLoop->getExitBlock();
765 BasicBlock *InnerExitingBlock = FI.InnerLoop->getExitingBlock();
770 DT->
deleteEdge(InnerExitingBlock, FI.InnerLoop->getHeader());
772 MSSAU->
removeEdge(InnerExitingBlock, FI.InnerLoop->getHeader());
777 for (
Value *V : FI.LinearIVUses) {
778 Value *OuterValue = FI.OuterInductionPHI;
780 OuterValue =
Builder.CreateTrunc(FI.OuterInductionPHI, V->
getType(),
794 LI->
erase(FI.InnerLoop);
811 Module *M = FI.InnerLoop->getHeader()->getParent()->getParent();
812 auto &
DL = M->getDataLayout();
813 auto *InnerType = FI.InnerInductionPHI->getType();
814 auto *OuterType = FI.OuterInductionPHI->getType();
815 unsigned MaxLegalSize =
DL.getLargestLegalIntTypeSizeInBits();
816 auto *MaxLegalType =
DL.getLargestLegalIntType(M->getContext());
821 if (InnerType != OuterType ||
822 InnerType->getScalarSizeInBits() >= MaxLegalSize ||
823 MaxLegalType->getScalarSizeInBits() <
824 InnerType->getScalarSizeInBits() * 2) {
831 unsigned ElimExt = 0;
832 unsigned Widened = 0;
847 if (!CreateWideIV({FI.InnerInductionPHI, MaxLegalType,
false},
Deleted))
852 FI.InnerPHIsToTransform.insert(FI.InnerInductionPHI);
854 if (!CreateWideIV({FI.OuterInductionPHI, MaxLegalType,
false},
Deleted))
857 assert(Widened &&
"Widened IV expected");
861 FI.NarrowInnerInductionPHI = FI.InnerInductionPHI;
862 FI.NarrowOuterInductionPHI = FI.OuterInductionPHI;
873 dbgs() <<
"Loop flattening running on outer loop "
874 << FI.OuterLoop->getHeader()->getName() <<
" and inner loop "
875 << FI.InnerLoop->getHeader()->getName() <<
" in "
876 << FI.OuterLoop->getHeader()->getParent()->getName() <<
"\n");
895 if (FI.Widened && !CanFlatten)
908 if (OR == OverflowResult::AlwaysOverflowsHigh ||
909 OR == OverflowResult::AlwaysOverflowsLow) {
910 LLVM_DEBUG(
dbgs() <<
"Multiply would always overflow, so not profitable\n");
912 }
else if (OR == OverflowResult::MayOverflow) {
913 LLVM_DEBUG(
dbgs() <<
"Multiply might overflow, not flattening\n");
917 LLVM_DEBUG(
dbgs() <<
"Multiply cannot overflow, modifying loop in-place\n");
924 bool Changed =
false;
929 FlattenInfo FI(OuterLoop, InnerLoop);
939 bool Changed =
false;
941 std::optional<MemorySSAUpdater> MSSAU;
953 MSSAU ? &*MSSAU :
nullptr);
989char LoopFlattenLegacyPass::ID = 0;
998 return new LoopFlattenLegacyPass();
1001bool LoopFlattenLegacyPass::runOnFunction(
Function &
F) {
1002 ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1003 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1004 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1006 auto &TTIP = getAnalysis<TargetTransformInfoWrapperPass>();
1007 auto *
TTI = &TTIP.getTTI(
F);
1008 auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
1009 auto *MSSA = getAnalysisIfAvailable<MemorySSAWrapperPass>();
1011 std::optional<MemorySSAUpdater> MSSAU;
1015 bool Changed =
false;
1016 for (
Loop *L : *LI) {
1019 Flatten(*LN, DT, LI, SE, AC,
TTI,
nullptr, MSSAU ? &*MSSAU :
nullptr);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static bool runOnFunction(Function &F, bool PostInlining)
static bool CanWidenIV(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)
static bool verifyTripCount(Value *RHS, Loop *L, SmallPtrSetImpl< Instruction * > &IterationInstructions, PHINode *&InductionPHI, Value *&TripCount, BinaryOperator *&Increment, BranchInst *&BackBranch, ScalarEvolution *SE, bool IsWidened)
static bool FlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI, LPMUpdater *U, MemorySSAUpdater *MSSAU)
static cl::opt< bool > WidenIV("loop-flatten-widen-iv", cl::Hidden, cl::init(true), cl::desc("Widen the loop induction variables, if possible, so " "overflow checks won't reject flattening"))
static bool setLoopComponents(Value *&TC, Value *&TripCount, BinaryOperator *&Increment, SmallPtrSetImpl< Instruction * > &IterationInstructions)
static bool DoFlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI, LPMUpdater *U, MemorySSAUpdater *MSSAU)
static bool checkIVUsers(FlattenInfo &FI)
static bool CanFlattenLoopPair(FlattenInfo &FI, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, const TargetTransformInfo *TTI)
bool Flatten(LoopNest &LN, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, TargetTransformInfo *TTI, LPMUpdater *U, MemorySSAUpdater *MSSAU)
static bool findLoopComponents(Loop *L, SmallPtrSetImpl< Instruction * > &IterationInstructions, PHINode *&InductionPHI, Value *&TripCount, BinaryOperator *&Increment, BranchInst *&BackBranch, ScalarEvolution *SE, bool IsWidened)
static OverflowResult checkOverflow(FlattenInfo &FI, DominatorTree *DT, AssumptionCache *AC)
static bool checkPHIs(FlattenInfo &FI, const TargetTransformInfo *TTI)
static cl::opt< unsigned > RepeatedInstructionThreshold("loop-flatten-cost-threshold", cl::Hidden, cl::init(2), cl::desc("Limit on the cost of instructions that can be repeated due to " "loop flattening"))
static cl::opt< bool > AssumeNoOverflow("loop-flatten-assume-no-overflow", cl::Hidden, cl::init(false), cl::desc("Assume that the product of the two iteration " "trip counts will never overflow"))
static bool checkOuterLoopInsts(FlattenInfo &FI, SmallPtrSetImpl< Instruction * > &IterationInstructions, const TargetTransformInfo *TTI)
This file defines the interface for the loop nest analysis.
This header provides classes for managing a pipeline of passes over loops in LLVM IR.
Module.h This file contains the declarations for the Module class.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Virtual Register Rewriter
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Value * getCondition() const
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_ULT
unsigned less than
This is the shared class of boolean and integer constants.
IntegerType * getType() const
getType - Specialize the getType() method to always return an IntegerType, which reduces the amount o...
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
const APInt & getValue() const
Return the constant as an APInt value reference.
A parsed version of the target data layout string in and methods for querying it.
void deleteEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge deletion and update the tree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionPass class - This class is used to implement most global optimizations.
This instruction compares its operands according to the predicate given to the constructor.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
const BasicBlock * getParent() const
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
void markLoopAsDeleted(Loop &L, llvm::StringRef Name)
Loop passes should use this method to indicate they have deleted a loop from the nest.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
PreservedAnalyses run(LoopNest &LN, LoopAnalysisManager &LAM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
This class represents a loop nest and can be used to query its properties.
ArrayRef< Loop * > getLoops() const
Get the loops in the nest.
static std::unique_ptr< LoopNest > getLoopNest(Loop &Root, ScalarEvolution &SE)
Construct a LoopNest object.
Represents a single loop in the control flow graph.
bool isCanonical(ScalarEvolution &SE) const
Return true if the loop induction variable starts at zero and increments by one each time through the...
ICmpInst * getLatchCmpInst() const
Get the latch condition instruction.
StringRef getName() const
PHINode * getInductionVariable(ScalarEvolution &SE) const
Return the loop induction variable if found, else return nullptr.
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
An analysis that produces MemorySSA for a function.
void removeEdge(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To following an edge deletion between From and To.
Legacy analysis pass which computes MemorySSA.
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
A Module instance is used to store all the information related to an LLVM module.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Value * hasConstantValue() const
If the specified PHI node always merges together the same value, return the value,...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
This class uses information about analyze scalars to rewrite expressions in canonical form.
This class represents an analyzed expression in the program.
The main scalar evolution driver.
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
const SCEV * getTripCountFromExitCount(const SCEV *ExitCount, bool Extend=true)
Convert from an "exit count" (i.e.
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
unsigned getIntegerBitWidth() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
user_iterator user_begin()
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
LLVMContext & getContext() const
All values hold a context through their type.
void dump() const
Support for debugging, callable in GDB: V->dump()
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Mul, true > m_c_Mul(const LHS &L, const RHS &R)
Matches a Mul with LHS and RHS in either order.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
PHINode * createWideIV(const WideIVInfo &WI, LoopInfo *LI, ScalarEvolution *SE, SCEVExpander &Rewriter, DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, unsigned &NumElimExt, unsigned &NumWidened, bool HasGuards, bool UsePostIncrementRanges)
Widen Induction Variables - Extend the width of an IV to cover its widest uses.
bool isGuaranteedToExecuteForEveryIteration(const Instruction *I, const Loop *L)
Return true if this function can prove that the instruction I is executed for every iteration of the ...
void initializeLoopFlattenLegacyPassPass(PassRegistry &)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
FunctionPass * createLoopFlattenPass()
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
bool VerifyMemorySSA
Enables verification of MemorySSA.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
If the specified value is an effectively dead PHI node, due to being a def-use chain of single-use no...
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
TargetTransformInfo & TTI
Collect information about induction variables that are used by sign/zero extend operations.