This is an archive of the discontinued LLVM Phabricator instance.

[LoopUtils] Updated deleteDeadLoop() to handle loop nest.
ClosedPublic

Authored by Whitney on Dec 2 2019, 9:41 PM.

Diff Detail

Event Timeline

Whitney created this revision.Dec 2 2019, 9:41 PM
Whitney updated this revision to Diff 231824.Dec 2 2019, 10:12 PM

Removed unnecessary includes.

The deleteDeadLoop function when called on the outer loop will effectively remove the subloops from the CFG too (make them unreachable). Maybe we should change deleteDeadLoop to also take the subloops into account when updating the analysis passed to it. Then we shouldn't need a separate function to delete loop nests.

Whitney added a comment.EditedDec 4 2019, 10:50 AM

Didn't notice Bardia already posted something similar.

Actually we can do a small modification in deleteDeadLoop to have it works for loop nest, by changing the last line from LI->erase(L); to erasing all loops in L. Would that way be more preferable?

What does everyone think? Is deleteDeadLoop() intensionally work for innermost loops? Is adding deleteDeadLoopNest() or modifying deleteDeadLoop() to work for loops with any depth preferred?

I slightly tend towards @bmahjour's suggestion, for convenience of the user.

Since deleteDeadLoop also deletes all its interior already, what is missing to be correct for nested loops as well? Even SCEV->forgetLoop seems to considered nested loops.

what is missing to be correct for nested loops as well?

The only think I can see missing is LI->erase(L), which relink the subloops of L to the parent of L, or change them to top level loops if L has no parent.

Whitney updated this revision to Diff 233101.Dec 10 2019, 7:41 AM
Whitney retitled this revision from [LoopUtils] Add an utility to delete dead loop nest. to [LoopUtils] Updated deleteDeadLoop() to handle loop nest. .
Whitney edited the summary of this revision. (Show Details)
Meinersbur added inline comments.Dec 10 2019, 9:30 AM
llvm/lib/Transforms/Utils/LoopUtils.cpp
676–687

[remark] Assigning a lambda to a std::function introduces a lot of overhead. However, auto doesn't work for calling itself recursively. https://laptrinhx.com/recursive-lambdas-713741980/ has a nice technique though.

677

[serious] LoopInfo::erase is designed to modify the parent's subloop list. At least, it will remove Subloop from L's subloop list, hence invalidating the iterator we are currently iterating over.

681

[suggestion] Could you add a comment such as "Recursively remove all subloops. Calling LoopInfo::erase only on the dead loop only moves its subloops to the dead loop's parent".

LoopInfo::erase does a loot of work to move the association of the subloop blocks to the parent. Since we know that the loop is dead, I wonder whether it is worth introducing a variant that just removes the dead loop from its parent's child list.

llvm/unittests/Transforms/Utils/LoopUtilsTest.cpp
28 ↗(On Diff #233101)

[style] No almost always auto

Whitney updated this revision to Diff 233161.Dec 10 2019, 11:32 AM

Use removeChildLoop() and removeLoop() instead of erase().

Whitney marked 3 inline comments as done.Dec 10 2019, 11:33 AM
Whitney updated this revision to Diff 233162.Dec 10 2019, 11:38 AM

Change use of auto.

Whitney marked an inline comment as done.Dec 10 2019, 11:38 AM
This revision is now accepted and ready to land.Dec 16 2019, 12:36 PM
This revision was automatically updated to reflect the committed changes.
Whitney reopened this revision.Dec 17 2019, 7:22 PM

To address memory leak.

This revision is now accepted and ready to land.Dec 17 2019, 7:22 PM
Whitney updated this revision to Diff 234444.Dec 17 2019, 7:23 PM

Need to destroy the loop after removing from LI.

This revision was automatically updated to reflect the committed changes.