Lines Matching refs:Loop
1 //===-- LoopUnroll.cpp - Loop unroller pass -------------------------------===//
10 // This pass implements a simple loop unroller. It works best when loops have
39 #define DEBUG_TYPE "loop-unroll"
43 cl::desc("The baseline cost threshold for loop unrolling"));
58 cl::desc("Don't allow loop unrolling to simulate more than this number of"
69 "-unroll-threshold loop size is reached."));
107 /// that the loop unroll should be performed regardless of how much
134 bool runOnLoop(Loop *L, LPPassManager &) override;
136 /// This transformation requires natural loop information & requires that
137 /// loop preheaders be inserted into the CFG...
151 // FIXME: Loop unroll requires LCSSA. And LCSSA requires dom info.
152 // If loop unroll does not preserve dom info then LCSSA pass on next
153 // loop will receive invalid dom info.
154 // For now, recreate dom info, if loop is unrolled.
161 void getUnrollingPreferences(Loop *L, const TargetTransformInfo &TTI,
183 selectUnrollCount(const Loop *L, unsigned TripCount, bool PragmaFullUnroll,
192 void selectThresholds(const Loop *L, bool UsePragmaThreshold,
220 // If the loop has an unrolling pragma, we want to be more
231 bool canUnrollCompletely(Loop *L, unsigned Threshold,
239 INITIALIZE_PASS_BEGIN(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
247 INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
260 // could get from complete loop unrolling. It comes from the fact that some
269 // If we completely unroll the loop, we would get:
310 /// While we walk the loop instructions, we build up and maintain a mapping
508 /// \brief Figure out if the loop is worth full unrolling.
510 /// Complete loop unrolling can make some loads constant, and we need to know
512 /// estimates this optimization. It computes cost of unrolled loop
513 /// (UnrolledCost) and dynamic cost of the original loop (RolledDynamicCost). By
515 /// to be executed (i.e. if we have a branch in the loop and we know that at the
519 /// the analysis failed (no benefits expected from the unrolling, or the loop is
522 analyzeLoopUnrollCost(const Loop *L, unsigned TripCount, DominatorTree &DT,
540 // The estimated cost of the unrolled form of the loop. We try to estimate
550 // Ensure that we don't violate the loop structure invariants relied on by
552 assert(L->isLoopSimplifyForm() && "Must put loop into normal form first.");
558 // Simulate execution of each iteration of the loop counting instructions,
561 // we literally have to go through all loop's iterations.
572 // The loop header PHI nodes must have exactly two input: one from the
573 // loop preheader and one from the loop latch.
596 // Note that we *must not* cache the size, this loop grows the worklist.
606 // Visit the instruction to analyze its loop cost after unrolling,
613 << " would be simplified if loop is unrolled.\n");
618 // loop form.
687 /// ApproximateLoopSize - Approximate the size of the loop.
688 static unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
696 for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
707 // that each loop has at least three instructions (likely a conditional
708 // branch, a comparison feeding that branch, and some kind of loop increment
715 // Returns the loop hint metadata node with the given name (for example,
716 // "llvm.loop.unroll.count"). If no such metadata node exists, then nullptr is
718 static MDNode *GetUnrollMetadataForLoop(const Loop *L, StringRef Name) {
724 // Returns true if the loop has an unroll(full) pragma.
725 static bool HasUnrollFullPragma(const Loop *L) {
726 return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.full");
729 // Returns true if the loop has an unroll(enable) pragma. This metadata is used
730 // for both "#pragma unroll" and "#pragma clang loop unroll(enable)" directives.
731 static bool HasUnrollEnablePragma(const Loop *L) {
732 return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.enable");
735 // Returns true if the loop has an unroll(disable) pragma.
736 static bool HasUnrollDisablePragma(const Loop *L) {
737 return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.disable");
740 // Returns true if the loop has an runtime unroll(disable) pragma.
741 static bool HasRuntimeUnrollDisablePragma(const Loop *L) {
742 return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.runtime.disable");
745 // If loop has an unroll_count pragma return the (necessarily
747 static unsigned UnrollCountPragmaValue(const Loop *L) {
748 MDNode *MD = GetUnrollMetadataForLoop(L, "llvm.loop.unroll.count");
761 // indicate the loop has already been unrolled. This prevents a loop
762 // from being unrolled more than is directed by a pragma if the loop
764 static void SetLoopAlreadyUnrolled(Loop *L) {
768 // First remove any existing loop unrolling metadata.
777 IsUnrollMetadata = S && S->getString().startswith("llvm.loop.unroll.");
786 DisableOperands.push_back(MDString::get(Context, "llvm.loop.unroll.disable"));
791 // Set operand 0 to refer to the loop id itself.
796 bool LoopUnroll::canUnrollCompletely(Loop *L, unsigned Threshold,
819 // dynamic cost of the loop, we use a higher threshold to allow more
850 const Loop *L, unsigned TripCount, bool PragmaFullUnroll,
889 bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &) {
904 DEBUG(dbgs() << "Loop Unroll: F[" << Header->getParent()->getName()
905 << "] Loop %" << Header->getName() << "\n");
942 DEBUG(dbgs() << " Loop Size = " << LoopSize << "\n");
946 // the loop body (which is why 2 is subtracted).
949 DEBUG(dbgs() << " Not unrolling loop which contains non-duplicatable"
954 DEBUG(dbgs() << " Not unrolling loop with inlinable calls.\n");
979 // If the loop is really small, we don't need to run an expensive analysis.
984 // The loop isn't that small, but we still can fully unroll it if that
986 // To check that, run additional analysis on the loop.
1006 // Don't unroll a runtime trip count loop with unroll full pragma.
1026 DEBUG(dbgs() << " will not try to unroll loop with runtime trip count "
1043 // If loop has an unroll count pragma mark loop as unrolled to prevent
1047 // Emit optimization remarks if we are unable to unroll the loop
1055 "Unable to unroll loop the number of times directed by "
1060 "Unable to fully unroll loop as directed by unroll(full) pragma "
1061 "because loop has a runtime trip count.");
1065 "Unable to unroll loop as directed by unroll(enable) pragma because "
1071 "Unable to fully unroll loop as directed by unroll pragma because "
1078 // of 1 makes sense because loop control can be eliminated.
1082 // Unroll the loop.
