LLVM  13.0.0git
UnrollLoop.h
Go to the documentation of this file.
1 //===- llvm/Transforms/Utils/UnrollLoop.h - Unrolling utilities -*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines some loop unrolling utilities. It does not define any
10 // actual pass or policy, but provides a single function to perform loop
11 // unrolling.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
16 #define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
17 
18 #include "llvm/ADT/DenseMap.h"
20 
21 namespace llvm {
22 
23 class AssumptionCache;
24 class BasicBlock;
25 class BlockFrequencyInfo;
26 class DependenceInfo;
27 class DominatorTree;
28 class Loop;
29 class LoopInfo;
30 class MDNode;
31 class ProfileSummaryInfo;
32 class OptimizationRemarkEmitter;
33 class ScalarEvolution;
34 class StringRef;
35 class Value;
36 
38 
39 /// @{
40 /// Metadata attribute names
41 const char *const LLVMLoopUnrollFollowupAll = "llvm.loop.unroll.followup_all";
42 const char *const LLVMLoopUnrollFollowupUnrolled =
43  "llvm.loop.unroll.followup_unrolled";
45  "llvm.loop.unroll.followup_remainder";
46 /// @}
47 
48 const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
49  BasicBlock *ClonedBB, LoopInfo *LI,
50  NewLoopsMap &NewLoops);
51 
52 /// Represents the result of a \c UnrollLoop invocation.
53 enum class LoopUnrollResult {
54  /// The loop was not modified.
55  Unmodified,
56 
57  /// The loop was partially unrolled -- we still have a loop, but with a
58  /// smaller trip count. We may also have emitted epilogue loop if the loop
59  /// had a non-constant trip count.
61 
62  /// The loop was fully unrolled into straight-line code. We no longer have
63  /// any back-edges.
65 };
66 
68  unsigned Count;
69  unsigned TripCount;
70  bool Force;
75  unsigned TripMultiple;
76  unsigned PeelCount;
79 };
80 
83  AssumptionCache *AC,
85  OptimizationRemarkEmitter *ORE, bool PreserveLCSSA,
86  Loop **RemainderLoop = nullptr);
87 
89  Loop *L, unsigned Count, bool AllowExpensiveTripCount,
90  bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV,
92  const TargetTransformInfo *TTI, bool PreserveLCSSA,
93  Loop **ResultLoop = nullptr);
94 
95 LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
96  unsigned TripMultiple, bool UnrollRemainder,
97  LoopInfo *LI, ScalarEvolution *SE,
99  const TargetTransformInfo *TTI,
101  Loop **EpilogueLoop = nullptr);
102 
104  DependenceInfo &DI, LoopInfo &LI);
105 
107  DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
108  const SmallPtrSetImpl<const Value *> &EphValues,
109  OptimizationRemarkEmitter *ORE, unsigned &TripCount,
110  unsigned MaxTripCount, bool MaxOrZero,
111  unsigned &TripMultiple, unsigned LoopSize,
114  bool &UseUpperBound);
115 
116 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
118  AssumptionCache *AC,
119  const TargetTransformInfo *TTI);
120 
122 
125  BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, int OptLevel,
126  Optional<unsigned> UserThreshold, Optional<unsigned> UserCount,
127  Optional<bool> UserAllowPartial, Optional<bool> UserRuntime,
128  Optional<bool> UserUpperBound, Optional<unsigned> UserFullUnrollMaxCount);
129 
130 unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
131  bool &NotDuplicatable, bool &Convergent,
132  const TargetTransformInfo &TTI,
133  const SmallPtrSetImpl<const Value *> &EphValues,
134  unsigned BEInsns);
135 
136 } // end namespace llvm
137 
138 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
llvm
Definition: AllocatorList.h:23
llvm::addClonedBlockToLoopInfo
const Loop * addClonedBlockToLoopInfo(BasicBlock *OriginalBB, BasicBlock *ClonedBB, LoopInfo *LI, NewLoopsMap &NewLoops)
Adds ClonedBB to LoopInfo, creates a new loop for ClonedBB if necessary and adds a mapping from the o...
Definition: LoopUnroll.cpp:137
llvm::UnrollLoopOptions::AllowRuntime
bool AllowRuntime
Definition: UnrollLoop.h:71
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::UnrollLoopOptions::AllowExpensiveTripCount
bool AllowExpensiveTripCount
Definition: UnrollLoop.h:72
llvm::UnrollAndJamLoop
LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, unsigned TripMultiple, bool UnrollRemainder, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, Loop **EpilogueLoop=nullptr)
Definition: LoopUnrollAndJam.cpp:225
llvm::LLVMLoopUnrollFollowupRemainder
const char *const LLVMLoopUnrollFollowupRemainder
Definition: UnrollLoop.h:44
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
llvm::UnrollLoopOptions::Force
bool Force
Definition: UnrollLoop.h:70
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
DenseMap.h
llvm::TargetTransformInfo::PeelingPreferences
Definition: TargetTransformInfo.h:529
llvm::ApproximateLoopSize
unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls, bool &NotDuplicatable, bool &Convergent, const TargetTransformInfo &TTI, const SmallPtrSetImpl< const Value * > &EphValues, unsigned BEInsns)
ApproximateLoopSize - Approximate the size of the loop.
Definition: LoopUnrollPass.cpp:654
llvm::Optional< unsigned >
llvm::MCID::Convergent
@ Convergent
Definition: MCInstrDesc.h:182
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
llvm::GetUnrollMetadata
MDNode * GetUnrollMetadata(MDNode *LoopID, StringRef Name)
Given an llvm.loop loop id metadata node, returns the loop hint metadata node with the given name (fo...
Definition: LoopUnroll.cpp:951
llvm::LLVMLoopUnrollFollowupUnrolled
const char *const LLVMLoopUnrollFollowupUnrolled
Definition: UnrollLoop.h:42
llvm::simplifyLoopAfterUnroll
void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI)
Perform some cleanup and simplifications on loops after unrolling.
Definition: LoopUnroll.cpp:205
llvm::UnrollLoopOptions::PreserveOnlyFirst
bool PreserveOnlyFirst
Definition: UnrollLoop.h:74
llvm::LoopUnrollResult::FullyUnrolled
@ FullyUnrolled
The loop was fully unrolled into straight-line code.
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::UnrollLoopOptions::TripMultiple
unsigned TripMultiple
Definition: UnrollLoop.h:75
llvm::LLVMLoopUnrollFollowupAll
const char *const LLVMLoopUnrollFollowupAll
Definition: UnrollLoop.h:41
llvm::DependenceInfo
DependenceInfo - This class is the main dependence-analysis driver.
Definition: DependenceAnalysis.h:272
llvm::UnrollLoop
LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const llvm::TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, Loop **RemainderLoop=nullptr)
Unroll the given loop by Count.
Definition: LoopUnroll.cpp:278
llvm::UnrollLoopOptions::TripCount
unsigned TripCount
Definition: UnrollLoop.h:69
llvm::TargetTransformInfo::UnrollingPreferences
Parameters that control the generic loop unrolling transformation.
Definition: TargetTransformInfo.h:423
llvm::gatherUnrollingPreferences
TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, int OptLevel, Optional< unsigned > UserThreshold, Optional< unsigned > UserCount, Optional< bool > UserAllowPartial, Optional< bool > UserRuntime, Optional< bool > UserUpperBound, Optional< unsigned > UserFullUnrollMaxCount)
Gather the various unrolling parameters based on the defaults, compiler flags, TTI overrides and user...
Definition: LoopUnrollPass.cpp:185
llvm::LoopUnrollResult::PartiallyUnrolled
@ PartiallyUnrolled
The loop was partially unrolled – we still have a loop, but with a smaller trip count.
llvm::LoopUnrollResult
LoopUnrollResult
Represents the result of a UnrollLoop invocation.
Definition: UnrollLoop.h:53
llvm::UnrollLoopOptions::ForgetAllSCEV
bool ForgetAllSCEV
Definition: UnrollLoop.h:78
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:64
llvm::MDNode
Metadata node.
Definition: Metadata.h:897
llvm::UnrollLoopOptions::PreserveCondBr
bool PreserveCondBr
Definition: UnrollLoop.h:73
llvm::UnrollRuntimeLoopRemainder
bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, bool ForgetAllSCEV, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, bool PreserveLCSSA, Loop **ResultLoop=nullptr)
Insert code in the prolog/epilog code when unrolling a loop with a run-time trip-count.
Definition: LoopUnrollRuntime.cpp:582
llvm::LoopInfo
Definition: LoopInfo.h:1080
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:418
llvm::isSafeToUnrollAndJam
bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, DependenceInfo &DI, LoopInfo &LI)
Definition: LoopUnrollAndJam.cpp:865
llvm::computeUnrollCount
bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, const SmallPtrSetImpl< const Value * > &EphValues, OptimizationRemarkEmitter *ORE, unsigned &TripCount, unsigned MaxTripCount, bool MaxOrZero, unsigned &TripMultiple, unsigned LoopSize, TargetTransformInfo::UnrollingPreferences &UP, TargetTransformInfo::PeelingPreferences &PP, bool &UseUpperBound)
Definition: LoopUnrollPass.cpp:762
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
llvm::UnrollLoopOptions::Count
unsigned Count
Definition: UnrollLoop.h:68
llvm::UnrollLoopOptions::UnrollRemainder
bool UnrollRemainder
Definition: UnrollLoop.h:77
llvm::UnrollLoopOptions::PeelCount
unsigned PeelCount
Definition: UnrollLoop.h:76
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
TargetTransformInfo.h
llvm::SmallPtrSetImpl< const Value * >
llvm::LoopUnrollResult::Unmodified
@ Unmodified
The loop was not modified.
llvm::UnrollLoopOptions
Definition: UnrollLoop.h:67