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" 21 #include "llvm/Analysis/TargetTransformInfo.h" 22 #include "llvm/Transforms/Utils/ValueMapper.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 36 using NewLoopsMap = SmallDenseMap<const Loop *, Loop *, 4>; 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. 50 PartiallyUnrolled, 51 52 /// The loop was fully unrolled into straight-line code. We no longer have 53 /// any back-edges. 54 FullyUnrolled 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, 63 DominatorTree *DT, AssumptionCache *AC, 64 OptimizationRemarkEmitter *ORE, bool PreserveLCSSA); 65 66 bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, 67 bool AllowExpensiveTripCount, 68 bool UseEpilogRemainder, bool UnrollRemainder, 69 LoopInfo *LI, 70 ScalarEvolution *SE, DominatorTree *DT, 71 AssumptionCache *AC, 72 bool PreserveLCSSA); 73 74 void computePeelCount(Loop *L, unsigned LoopSize, 75 TargetTransformInfo::UnrollingPreferences &UP, 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, 86 DominatorTree *DT, AssumptionCache *AC, 87 OptimizationRemarkEmitter *ORE); 88 89 bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, 90 DependenceInfo &DI); 91 92 bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI, 93 DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, 94 const SmallPtrSetImpl<const Value *> &EphValues, 95 OptimizationRemarkEmitter *ORE, unsigned &TripCount, 96 unsigned MaxTripCount, unsigned &TripMultiple, 97 unsigned LoopSize, 98 TargetTransformInfo::UnrollingPreferences &UP, 99 bool &UseUpperBound); 100 101 BasicBlock *foldBlockIntoPredecessor(BasicBlock *BB, LoopInfo *LI, 102 ScalarEvolution *SE, DominatorTree *DT); 103 104 void remapInstruction(Instruction *I, ValueToValueMapTy &VMap); 105 106 void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, 107 ScalarEvolution *SE, DominatorTree *DT, 108 AssumptionCache *AC); 109 110 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); 111 112 TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences( 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 127