LLVM  7.0.0svn
UnrollLoop.h
Go to the documentation of this file.
1 //===- llvm/Transforms/Utils/UnrollLoop.h - Unrolling utilities -*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines some loop unrolling utilities. It does not define any
11 // actual pass or policy, but provides a single function to perform loop
12 // unrolling.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
17 #define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
18 
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/StringRef.h"
23 
24 namespace llvm {
25 
26 class AssumptionCache;
27 class BasicBlock;
28 class DependenceInfo;
29 class DominatorTree;
30 class Loop;
31 class LoopInfo;
32 class MDNode;
33 class OptimizationRemarkEmitter;
34 class ScalarEvolution;
35 
37 
38 const Loop* addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
39  BasicBlock *ClonedBB, LoopInfo *LI,
40  NewLoopsMap &NewLoops);
41 
42 /// Represents the result of a \c UnrollLoop invocation.
43 enum class LoopUnrollResult {
44  /// The loop was not modified.
45  Unmodified,
46 
47  /// The loop was partially unrolled -- we still have a loop, but with a
48  /// smaller trip count. We may also have emitted epilogue loop if the loop
49  /// had a non-constant trip count.
51 
52  /// The loop was fully unrolled into straight-line code. We no longer have
53  /// any back-edges.
55 };
56 
57 LoopUnrollResult UnrollLoop(Loop *L, unsigned Count, unsigned TripCount,
58  bool Force, bool AllowRuntime,
59  bool AllowExpensiveTripCount, bool PreserveCondBr,
60  bool PreserveOnlyFirst, unsigned TripMultiple,
61  unsigned PeelCount, bool UnrollRemainder,
62  LoopInfo *LI, ScalarEvolution *SE,
64  OptimizationRemarkEmitter *ORE, bool PreserveLCSSA);
65 
66 bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
67  bool AllowExpensiveTripCount,
68  bool UseEpilogRemainder, bool UnrollRemainder,
69  LoopInfo *LI,
71  AssumptionCache *AC,
72  bool PreserveLCSSA);
73 
74 void computePeelCount(Loop *L, unsigned LoopSize,
76  unsigned &TripCount, ScalarEvolution &SE);
77 
78 bool canPeel(Loop *L);
79 
80 bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE,
81  DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA);
82 
83 LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
84  unsigned TripMultiple, bool UnrollRemainder,
85  LoopInfo *LI, ScalarEvolution *SE,
88 
90  DependenceInfo &DI);
91 
92 bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI,
94  const SmallPtrSetImpl<const Value *> &EphValues,
95  OptimizationRemarkEmitter *ORE, unsigned &TripCount,
96  unsigned MaxTripCount, unsigned &TripMultiple,
97  unsigned LoopSize,
99  bool &UseUpperBound);
100 
102  ScalarEvolution *SE, DominatorTree *DT);
103 
105 
106 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
108  AssumptionCache *AC);
109 
111 
113  Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, int OptLevel,
114  Optional<unsigned> UserThreshold, Optional<unsigned> UserCount,
115  Optional<bool> UserAllowPartial, Optional<bool> UserRuntime,
116  Optional<bool> UserUpperBound, Optional<bool> UserAllowPeeling);
117 
118 unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
119  bool &NotDuplicatable, bool &Convergent,
120  const TargetTransformInfo &TTI,
121  const SmallPtrSetImpl<const Value *> &EphValues,
122  unsigned BEInsns);
123 
124 } // end namespace llvm
125 
126 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Various leaf nodes.
Definition: ISDOpcodes.h:60
The main scalar evolution driver.
A cache of @llvm.assume calls within a function.
BasicBlock * foldBlockIntoPredecessor(BasicBlock *BB, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT)
Folds a basic block into its predecessor if it only has one predecessor, and that predecessor only ha...
Definition: LoopUnroll.cpp:100
Metadata node.
Definition: Metadata.h:862
bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, const SmallPtrSetImpl< const Value *> &EphValues, OptimizationRemarkEmitter *ORE, unsigned &TripCount, unsigned MaxTripCount, unsigned &TripMultiple, unsigned LoopSize, TargetTransformInfo::UnrollingPreferences &UP, bool &UseUpperBound)
DependenceInfo - This class is the main dependence-analysis driver.
void computePeelCount(Loop *L, unsigned LoopSize, TargetTransformInfo::UnrollingPreferences &UP, unsigned &TripCount, ScalarEvolution &SE)
LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, unsigned TripMultiple, bool UnrollRemainder, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, OptimizationRemarkEmitter *ORE)
bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, DependenceInfo &DI)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
void remapInstruction(Instruction *I, ValueToValueMapTy &VMap)
Convert the instruction operands from referencing the current values into those specified by VMap...
Definition: LoopUnroll.cpp:66
The loop was fully unrolled into straight-line code.
TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, int OptLevel, Optional< unsigned > UserThreshold, Optional< unsigned > UserCount, Optional< bool > UserAllowPartial, Optional< bool > UserRuntime, Optional< bool > UserUpperBound, Optional< bool > UserAllowPeeling)
Gather the various unrolling parameters based on the defaults, compiler flags, TTI overrides and user...
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA)
Peel off the first PeelCount iterations of loop L.
The loop was partially unrolled – we still have a loop, but with a smaller trip count.
bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA)
Insert code in the prolog/epilog code when unrolling a loop with a run-time trip-count.
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.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
bool canPeel(Loop *L)
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:190
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:887
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
Parameters that control the generic loop unrolling transformation.
#define I(x, y, z)
Definition: MD5.cpp:58
The loop was not modified.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
This pass exposes codegen information to IR-level passes.
LoopUnrollResult UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool Force, bool AllowRuntime, bool AllowExpensiveTripCount, bool PreserveCondBr, bool PreserveOnlyFirst, unsigned TripMultiple, unsigned PeelCount, bool UnrollRemainder, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA)
Unroll the given loop by Count.
Definition: LoopUnroll.cpp:333
The optimization diagnostic interface.
LoopUnrollResult
Represents the result of a UnrollLoop invocation.
Definition: UnrollLoop.h:43
void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC)
Perform some cleanup and simplifications on loops after unrolling.
Definition: LoopUnroll.cpp:258