Lines Matching refs:Loop
1 //===- LoopInterchange.cpp - Loop interchange pass------------------------===//
10 // This Pass handles loop interchange transform.
46 #define DEBUG_TYPE "loop-interchange"
50 typedef SmallVector<Loop *, 8> LoopVector;
58 // Maximum loop depth supported.
75 Loop *L, DependenceAnalysis *DA) {
86 for (Loop::block_iterator BB = L->block_begin(), BE = L->block_end();
171 << " dependencies inside loop\n");
185 // A loop is moved from index 'from' to an index 'to'. Update the Dependence
242 // If OuterLoopId represents outermost loop then interchanging will make the
280 static void populateWorklist(Loop &L, SmallVector<LoopVector, 8> &V) {
284 Loop *CurrentLoop = &L;
285 const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
287 // The current loop has multiple subloops in it hence it is not tightly
302 static PHINode *getInductionVariable(Loop *L, ScalarEvolution *SE) {
330 /// LoopInterchangeLegality checks if it is legal to interchange the loop.
333 LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
341 /// Check if the loop structure is understood. We do not handle triangular
350 bool tightlyNested(Loop *Outer, Loop *Inner);
352 bool areAllUsesReductions(Instruction *Ins, Loop *L);
354 bool findInductionAndReductions(Loop *L,
357 Loop *OuterLoop;
358 Loop *InnerLoop;
369 /// loop.
372 LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE)
375 /// Check if the loop interchange is profitable.
382 Loop *OuterLoop;
383 Loop *InnerLoop;
389 /// LoopInterchangeTransform interchanges the loop.
392 LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
402 void restructureLoops(Loop *InnerLoop, Loop *OuterLoop);
403 void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
417 Loop *OuterLoop;
418 Loop *InnerLoop;
459 // Build up a worklist of loop pairs to analyze.
462 for (Loop *L : *LI)
476 Loop *L = *I;
487 DEBUG(dbgs() << "Loop Doesn't have unique exit block\n");
495 // TODO: Add a better heuristic to select the loop to be interchanged based
496 // on the dependence matrix. Currently we select the innermost loop.
505 DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
509 DEBUG(dbgs() << "Not vaild loop candidate for interchange\n");
512 Loop *OuterMostLoop = *(LoopList.begin());
533 // Since we currently do not handle LCSSA PHI's any failure in loop
537 // Get the Outermost loop exit.
545 DEBUG(dbgs() << "PHI Nodes in loop nest exit is not handled for now "
546 "since on failure all loops branch to loop nest exit.\n");
551 // Move the selected loop outwards to the best possible position.
576 DEBUG(dbgs() << "Processing Innder Loop Id = " << InnerLoopId
578 Loop *InnerLoop = LoopList[InnerLoopId];
579 Loop *OuterLoop = LoopList[OuterLoopId];
603 bool LoopInterchangeLegality::areAllUsesReductions(Instruction *Ins, Loop *L) {
640 bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
647 // A perfectly nested loop will not have any branch in between the outer and
661 DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch \n");
663 // and outer loop latch doesn't contain any unsafe instructions.
669 // We have a perfect loop nest.
700 Loop *L, SmallVector<PHINode *, 8> &Inductions,
724 // Reduction lcssa phi will have only 1 incoming block that from loop latch.
730 // Incoming value for lcssa phi's in outer loop exit can only be inner loop
782 // Outer loop cannot have reduction because then loops will not be tightly
792 DEBUG(dbgs() << "Loop structure not understood by pass\n");
806 // TODO: Current limitation: Since we split the inner loop latch at the point
828 // Since we split the inner loop latch on this induction variable. Make sure
838 // safe to split this loop latch.
844 // The loop latch ended and we didn't find the induction variable return as
870 // 3) If OuterLoop Preheader is same as Header of the previous loop.
957 // If the inner loop is loop independent or doesn't carry any dependency it is
967 // If outer loop has dependence and inner loop is loop independent then it is
978 // 1) Construct dependency matrix and move the one with no loop carried dep
991 // we can move this loop outside to improve parallelism.
997 void LoopInterchangeTransform::removeChildLoop(Loop *OuterLoop,
998 Loop *InnerLoop) {
999 for (Loop::iterator I = OuterLoop->begin(), E = OuterLoop->end(); I != E;
1006 llvm_unreachable("Couldn't find loop");
1009 void LoopInterchangeTransform::restructureLoops(Loop *InnerLoop,
1010 Loop *OuterLoop) {
1011 Loop *OuterLoopParent = OuterLoop->getParentLoop();
1013 // Remove the loop from its parent loop.
1036 DEBUG(dbgs() << "Calling Split Inner Loop\n");
1039 DEBUG(dbgs() << "Failed to find the point to split loop latch \n");
1085 // Split the inner loop header out. Here make sure that the reduction PHI's
1094 if (Loop *L = LI->getLoopFor(InnerLoopHeader))
1157 // Adjust the loop preheader
1195 // Adjust Loop Preheader and headers
1218 // -------------Adjust loop latches-----------
1231 // the value and remove this PHI node from inner loop.
1269 // inside the outer loop.
1276 // These instructions should now be executed inside the loop.
1279 // These instructions were not executed previously in the loop so move them to
1280 // the older inner loop preheader.
1286 // Adjust all branches in the inner and outer loop.
1294 INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange",
1304 INITIALIZE_PASS_END(LoopInterchange, "loop-interchange",
