Lines Matching refs:Loop
1 //===-- LoopIdiomRecognize.cpp - Loop idiom recognition -------------------===//
11 // non-loop form. In cases that this kicks in, it can be a significant
18 // Future loop memory idioms to recognize:
27 // would be good to enhance isel to emit a loop for ctpop in this case.
30 // the loop. This would handle things like:
61 #define DEBUG_TYPE "loop-idiom"
63 STATISTIC(NumMemSet, "Number of memset's formed from loop stores");
64 STATISTIC(NumMemCpy, "Number of memcpy's formed from loop load+stores");
69 Loop *CurLoop;
84 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
86 /// This transformation requires natural loop information & requires that
87 /// loop preheaders be inserted into the CFG.
113 /// \name Countable Loop Idiom Handling
134 /// \name Noncountable Loop Idiom Handling
149 INITIALIZE_PASS_BEGIN(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms",
162 INITIALIZE_PASS_END(LoopIdiomRecognize, "loop-idiom", "Recognize loop idioms",
186 bool LoopIdiomRecognize::runOnLoop(Loop *L, LPPassManager &LPM) {
191 // If the loop could not be converted to canonical form, it must have an
196 // Disable loop idiom recognition if the function's name is a common idiom.
219 "runOnCountableLoop() called on a loop without a predictable"
222 // If this loop executes exactly one time, then it should be peeled, not
231 DEBUG(dbgs() << "loop-idiom Scanning: F["
232 << CurLoop->getHeader()->getParent()->getName() << "] Loop %"
236 // Scan all the blocks in the loop that are not in subloops.
314 // loop, which indicates a strided store. If we have something else, it's a
344 /// runOnLoopBlock - Process the specified block, which lives in a counted loop
346 /// loop and not in any subloops.
351 // executed in the loop. For a block to be unconditionally executed, it has
352 // to dominate all the exit blocks of the loop. Verify this now.
391 // know that every byte is touched in the loop.
423 // loop, which indicates a strided store. If we have something else, it's a
435 // know that every byte is touched in the loop.
448 /// mayLoopAccessLocation - Return true if the specified loop might access the
449 /// specified pointer location, which is a loop-strided access. The 'Access'
451 static bool mayLoopAccessLocation(Value *Ptr, ModRefInfo Access, Loop *L,
455 // Get the location that may be stored across the loop. Since the access is
460 // If the loop iterates a fixed number of times, we can refine the access size
471 for (Loop::block_iterator BI = L->block_begin(), E = L->block_end(); BI != E;
494 /// transform this into a memset or memset_pattern in the loop preheader, do so.
511 // Verify that the stored value is loop invariant. If not, we can't
527 // The trip count of the loop and the base pointer of the addrec SCEV is
528 // guaranteed to be loop invariant, which means that it should dominate the
532 SCEVExpander Expander(*SE, *DL, "loop-idiom");
543 // this into a memset in the loop preheader now if we want. However, this
544 // would be unsafe to do if there is anything else in the loop that may read
608 /// If the stored value is a strided load in the same loop with the same stride
624 // loop, which indicates a strided load. If we have something else, it's a
635 // The trip count of the loop and the base pointer of the addrec SCEV is
636 // guaranteed to be loop invariant, which means that it should dominate the
640 SCEVExpander Expander(*SE, *DL, "loop-idiom");
651 // this into a memcpy in the loop preheader now if we want. However, this
652 // would be unsafe to do if there is anything else in the loop that may read
675 // mutated by the loop.
725 /// the loop entry. If the branch matches the behavior, the variable involved
727 /// precondition and postcondition of the loop are in desirable form.
748 /// Return true iff the idiom is detected in the loop.
758 /// goto loop-exit // the precondition of the loop
770 /// loop-exit:
772 static bool detectPopcountIdiom(Loop *CurLoop, BasicBlock *PreCondBB,
776 // "if (a!=0) goto loop-entry".
787 // step 1: Check if the loop-back branch is in desirable form.
849 // Check if the result of the instruction is live of the loop.
870 // "if (x != 0) goto loop-head ; else goto somewhere-we-don't-care;"
885 /// Recognizes a population count idiom in a non-countable loop.
895 // non-compact loop. Therefore, recognizing popcount idiom only makes sense
896 // in a compact loop.
898 // Give up if the loop has multiple blocks or multiple backedges.
904 // The loop is too big, bail out.
957 // Assuming before transformation, the loop is following:
972 // TripCnt is exactly the number of iterations the loop has
984 // Step 2: Replace the precondition from "if (x == 0) goto loop-exit" to
985 // "if (NewCount == 0) loop-exit". Without this change, the intrinsic
1004 // loop in question, which enable us to to convert the loop from noncountable
1005 // loop into a countable one. The benefit is twofold:
1007 // - If the loop only counts population, the entire loop becomes dead after
1008 // the transformation. It is a lot easier to prove a countable loop dead
1009 // than to prove a noncountable one. (In some C dialects, an infinite loop
1011 // to prove a noncountable loop finite before safely delete it.)
1013 // - If the loop also performs something else, it remains alive.
1016 // to a noncountable loop.
1018 // After this step, this loop (conceptually) would look like following:
1047 // the loop are replaced with the NewCount -- the value returned from
1052 // loop. The loop would otherwise not be deleted even if it becomes empty.
