10b57cec5SDimitry Andric //===- llvm/Transforms/Utils/UnrollLoop.h - Unrolling utilities -*- C++ -*-===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // This file defines some loop unrolling utilities. It does not define any 100b57cec5SDimitry Andric // actual pass or policy, but provides a single function to perform loop 110b57cec5SDimitry Andric // unrolling. 120b57cec5SDimitry Andric // 130b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 140b57cec5SDimitry Andric 150b57cec5SDimitry Andric #ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H 160b57cec5SDimitry Andric #define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H 170b57cec5SDimitry Andric 180b57cec5SDimitry Andric #include "llvm/ADT/DenseMap.h" 190b57cec5SDimitry Andric #include "llvm/Analysis/TargetTransformInfo.h" 2081ad6265SDimitry Andric #include "llvm/Support/InstructionCost.h" 210b57cec5SDimitry Andric 220b57cec5SDimitry Andric namespace llvm { 230b57cec5SDimitry Andric 240b57cec5SDimitry Andric class AssumptionCache; 250b57cec5SDimitry Andric class BasicBlock; 260b57cec5SDimitry Andric class BlockFrequencyInfo; 270b57cec5SDimitry Andric class DependenceInfo; 280b57cec5SDimitry Andric class DominatorTree; 290b57cec5SDimitry Andric class Loop; 300b57cec5SDimitry Andric class LoopInfo; 310b57cec5SDimitry Andric class MDNode; 320b57cec5SDimitry Andric class ProfileSummaryInfo; 330b57cec5SDimitry Andric class OptimizationRemarkEmitter; 340b57cec5SDimitry Andric class ScalarEvolution; 355ffd83dbSDimitry Andric class StringRef; 365ffd83dbSDimitry Andric class Value; 370b57cec5SDimitry Andric 380b57cec5SDimitry Andric using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>; 390b57cec5SDimitry Andric 400b57cec5SDimitry Andric /// @{ 410b57cec5SDimitry Andric /// Metadata attribute names 420b57cec5SDimitry Andric const char *const LLVMLoopUnrollFollowupAll = "llvm.loop.unroll.followup_all"; 430b57cec5SDimitry Andric const char *const LLVMLoopUnrollFollowupUnrolled = 440b57cec5SDimitry Andric "llvm.loop.unroll.followup_unrolled"; 450b57cec5SDimitry Andric const char *const LLVMLoopUnrollFollowupRemainder = 460b57cec5SDimitry Andric "llvm.loop.unroll.followup_remainder"; 470b57cec5SDimitry Andric /// @} 480b57cec5SDimitry Andric 490b57cec5SDimitry Andric const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB, 500b57cec5SDimitry Andric BasicBlock *ClonedBB, LoopInfo *LI, 510b57cec5SDimitry Andric NewLoopsMap &NewLoops); 520b57cec5SDimitry Andric 530b57cec5SDimitry Andric /// Represents the result of a \c UnrollLoop invocation. 540b57cec5SDimitry Andric enum class LoopUnrollResult { 550b57cec5SDimitry Andric /// The loop was not modified. 560b57cec5SDimitry Andric Unmodified, 570b57cec5SDimitry Andric 580b57cec5SDimitry Andric /// The loop was partially unrolled -- we still have a loop, but with a 590b57cec5SDimitry Andric /// smaller trip count. We may also have emitted epilogue loop if the loop 600b57cec5SDimitry Andric /// had a non-constant trip count. 610b57cec5SDimitry Andric PartiallyUnrolled, 620b57cec5SDimitry Andric 630b57cec5SDimitry Andric /// The loop was fully unrolled into straight-line code. We no longer have 640b57cec5SDimitry Andric /// any back-edges. 650b57cec5SDimitry Andric FullyUnrolled 660b57cec5SDimitry Andric }; 670b57cec5SDimitry Andric 680b57cec5SDimitry Andric struct UnrollLoopOptions { 690b57cec5SDimitry Andric unsigned Count; 700b57cec5SDimitry Andric bool Force; 71fe6060f1SDimitry Andric bool Runtime; 720b57cec5SDimitry Andric bool AllowExpensiveTripCount; 730b57cec5SDimitry Andric bool UnrollRemainder; 740b57cec5SDimitry Andric bool ForgetAllSCEV; 750b57cec5SDimitry Andric }; 760b57cec5SDimitry Andric 770b57cec5SDimitry Andric LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, 780b57cec5SDimitry Andric ScalarEvolution *SE, DominatorTree *DT, 795ffd83dbSDimitry Andric AssumptionCache *AC, 805ffd83dbSDimitry Andric const llvm::TargetTransformInfo *TTI, 815ffd83dbSDimitry Andric OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, 825ffd83dbSDimitry Andric Loop **RemainderLoop = nullptr); 830b57cec5SDimitry Andric 845ffd83dbSDimitry Andric bool UnrollRuntimeLoopRemainder( 855ffd83dbSDimitry Andric Loop *L, unsigned Count, bool AllowExpensiveTripCount, 865ffd83dbSDimitry Andric bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, 875ffd83dbSDimitry Andric LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, 885ffd83dbSDimitry Andric const TargetTransformInfo *TTI, bool PreserveLCSSA, 890b57cec5SDimitry Andric Loop **ResultLoop = nullptr); 900b57cec5SDimitry Andric 910b57cec5SDimitry Andric LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, 920b57cec5SDimitry Andric unsigned TripMultiple, bool UnrollRemainder, 930b57cec5SDimitry Andric LoopInfo *LI, ScalarEvolution *SE, 940b57cec5SDimitry Andric DominatorTree *DT, AssumptionCache *AC, 955ffd83dbSDimitry Andric const TargetTransformInfo *TTI, 960b57cec5SDimitry Andric OptimizationRemarkEmitter *ORE, 970b57cec5SDimitry Andric Loop **EpilogueLoop = nullptr); 980b57cec5SDimitry Andric 990b57cec5SDimitry Andric bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, 1005ffd83dbSDimitry Andric DependenceInfo &DI, LoopInfo &LI); 1010b57cec5SDimitry Andric 1020b57cec5SDimitry Andric void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, 1030b57cec5SDimitry Andric ScalarEvolution *SE, DominatorTree *DT, 1045ffd83dbSDimitry Andric AssumptionCache *AC, 1055ffd83dbSDimitry Andric const TargetTransformInfo *TTI); 1060b57cec5SDimitry Andric 1070b57cec5SDimitry Andric MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); 1080b57cec5SDimitry Andric 1090b57cec5SDimitry Andric TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences( 1100b57cec5SDimitry Andric Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, 111349cc55cSDimitry Andric BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, 112349cc55cSDimitry Andric llvm::OptimizationRemarkEmitter &ORE, int OptLevel, 113bdd1243dSDimitry Andric std::optional<unsigned> UserThreshold, std::optional<unsigned> UserCount, 114bdd1243dSDimitry Andric std::optional<bool> UserAllowPartial, std::optional<bool> UserRuntime, 115bdd1243dSDimitry Andric std::optional<bool> UserUpperBound, 116bdd1243dSDimitry Andric std::optional<unsigned> UserFullUnrollMaxCount); 1175ffd83dbSDimitry Andric 1185f757f3fSDimitry Andric /// Produce an estimate of the unrolled cost of the specified loop. This 1195f757f3fSDimitry Andric /// is used to a) produce a cost estimate for partial unrolling and b) to 1205f757f3fSDimitry Andric /// cheaply estimate cost for full unrolling when we don't want to symbolically 1215f757f3fSDimitry Andric /// evaluate all iterations. 1225f757f3fSDimitry Andric class UnrollCostEstimator { 1235f757f3fSDimitry Andric InstructionCost LoopSize; 1245f757f3fSDimitry Andric bool NotDuplicatable; 1255f757f3fSDimitry Andric 1265f757f3fSDimitry Andric public: 1275f757f3fSDimitry Andric unsigned NumInlineCandidates; 1285f757f3fSDimitry Andric bool Convergent; 1295f757f3fSDimitry Andric 1305f757f3fSDimitry Andric UnrollCostEstimator(const Loop *L, const TargetTransformInfo &TTI, 1315f757f3fSDimitry Andric const SmallPtrSetImpl<const Value *> &EphValues, 1325f757f3fSDimitry Andric unsigned BEInsns); 1335f757f3fSDimitry Andric 1345f757f3fSDimitry Andric /// Whether it is legal to unroll this loop. canUnroll()1355f757f3fSDimitry Andric bool canUnroll() const { return LoopSize.isValid() && !NotDuplicatable; } 1365f757f3fSDimitry Andric getRolledLoopSize()1375f757f3fSDimitry Andric uint64_t getRolledLoopSize() const { return *LoopSize.getValue(); } 1385f757f3fSDimitry Andric 1395f757f3fSDimitry Andric /// Returns loop size estimation for unrolled loop, given the unrolling 1405f757f3fSDimitry Andric /// configuration specified by UP. 1415f757f3fSDimitry Andric uint64_t 1425f757f3fSDimitry Andric getUnrolledLoopSize(const TargetTransformInfo::UnrollingPreferences &UP, 1435f757f3fSDimitry Andric unsigned CountOverwrite = 0) const; 1445f757f3fSDimitry Andric }; 1455f757f3fSDimitry Andric 1465f757f3fSDimitry Andric bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI, 1475f757f3fSDimitry Andric DominatorTree &DT, LoopInfo *LI, AssumptionCache *AC, 1485f757f3fSDimitry Andric ScalarEvolution &SE, 1495f757f3fSDimitry Andric const SmallPtrSetImpl<const Value *> &EphValues, 1505f757f3fSDimitry Andric OptimizationRemarkEmitter *ORE, unsigned TripCount, 1515f757f3fSDimitry Andric unsigned MaxTripCount, bool MaxOrZero, 1525f757f3fSDimitry Andric unsigned TripMultiple, const UnrollCostEstimator &UCE, 1535f757f3fSDimitry Andric TargetTransformInfo::UnrollingPreferences &UP, 1545f757f3fSDimitry Andric TargetTransformInfo::PeelingPreferences &PP, 1555f757f3fSDimitry Andric bool &UseUpperBound); 1560b57cec5SDimitry Andric 1570b57cec5SDimitry Andric } // end namespace llvm 1580b57cec5SDimitry Andric 1590b57cec5SDimitry Andric #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H 160