[LoopSimplify][NFC] Replace depth-first order process as depth_first accessor.

[reames]

llvm/lib/Transforms/Utils/LoopSimplify.cpp

731

This looks wrong. The original loop was pushing elements in inverse depth first order (i.e. from the root down) so that it could walk backwards through that order to get dfs. You seem to be visiting each item in dfs, and adding them to worklist, and then still visiting them in inverse order.

[StephenFan]

llvm/lib/Transforms/Utils/LoopSimplify.cpp

731

Thanks! Indeed, I was wrong. I found that the inverse_depth_first iterator accessor might be suitable.

[StephenFan]

llvm/lib/Transforms/Utils/LoopSimplify.cpp

731

After digging into the implementation detail of depth_first, I feel like you may have misunderstood what depth_first would do. I found that depth_first would return nodes from the root down. So this patch looks correct.

[fhahn]

llvm/lib/Transforms/Utils/LoopSimplify.cpp

731

You should be able to verify that the contents of the worklist stays the same by computing it both ways and then comparing them.

[StephenFan]

llvm/lib/Transforms/Utils/LoopSimplify.cpp

731

I compared them and found the order in worklist is indeed different. The original process is actually a breadth-first iteration, and then visit them from back to front in the following while loop. Interestingly, no test is a failure despite the different iteration order.

I drew a picture to show these two different orders.

llvm/lib/Transforms/Utils/LoopSimplify.cpp

if (PreserveLCSSA) {
     assert(LI && "LI not available.");
     assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
            "Requested to preserve LCSSA, but it's already broken.");
   }
 #endif
 
   // Worklist maintains our depth-first queue of loops in this nest to process.
   SmallVector<Loop *, 4> Worklist;
-  Worklist.push_back(L);
-
-  // Walk the worklist from front to back, pushing newly found sub loops onto
-  // the back. This will let us process loops from back to front in depth-first
-  // order. We can use this simple process because loops form a tree.
-  for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
-    Loop *L2 = Worklist[Idx];
-    Worklist.append(L2->begin(), L2->end());
-  }
+  for_each(depth_first(L),
+           [&Worklist](Loop *SubLoop) { Worklist.push_back(SubLoop); });
 
   while (!Worklist.empty())
     Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, DT, LI, SE,
                                AC, MSSAU, PreserveLCSSA);
 
   return Changed;
 }